The approximate Dirichlet Domain Decomposition method. Part II: Applications to 2nd-order Elliptic B.V.P.s

In the first part of this article series, we had derived Domain Decomposition (DD) preconditioners containing three block matrices which must be specified for specific applications. In the present paper, we consider finite element equations arising from the DD discretization of plane, symmetric, 2nd-order, elliptic b.v.p.s and specify the matrices involved in the preconditioner via multigrid and hierarchical techniques. The resulting DD-PCCG methods are asymptotically almost optimal with respect to the operation count and well suited for parallel computations on MIMD computers with local memory and message passing. The numerical experiments performed on a transputer hypercube confirm the efficiency of the DD preconditioners proposed.     

Digital connectedness: An algebraic approach

Let E be the incidence matrix of a graph G having m nodes; then the number of connected components of G is equal to m ? r, where r is the rank of E. In particular, if G represents an adjacency relation between points in a digital picture (or higher-dimensional array), this shows that the connected components of points can be counted by computing the rank of E. Two proofs of this result are given, one based on results from algebraic topology and the other based on a self-contained graph-theoretic argument. The former proof can be generalized to yield a method of counting holes.     

Transformations of structures: An algebraic approach

This paper introduces a new mathematical approach to transformations of structures, where the concept of structure is extremely general. Many structures and transformations that arise in biology as well as computer science are special cases of our concepts. A structure may be changed by finding an occurrence of a pattern and replacing it by another pattern as specified by a rule. To prove theorems about long sequences of applications of complicated rules, we need precise and tractable mathematical definitions of rules and how to apply them. This paper presents such definitions and three fundamental theorems, together with brief remarks on applications to control flow analysis, record handling, and evaluation of recursively defined functions. Unlike some previous efforts toward a rigorous theory of transformations of structures, this paper uses ideas and results from abstract algebra to minimize the need for elaborate constructions.A condensation of an earlier version of this paper was presented as [9] at the 7th Symposium on Mathematical Foundations of Computer Science, September 1978, Zakopane, Poland. Work by Ehrig was partially supported by IBM Germany and IBM World Trade Corp. Work by Rosen and Maggiolo-Schettini was partially supported by the Laboratorio di Cibernetica del C.N.R.     

Parallel Hermite interpolation: An algebraic approach

Givenn+1 distinct points and arbitrary order derivative information at these points, a parallel algorithm to compute the coefficients of the corresponding Hermite interpolating polynomial inO (logn) parallel arithmetic operations usingO (n ²) processors is presented. The algorithm relies on a novel closed formula that yields the expansion of the generalized divided differences in terms of the given function and derivative values. We show that each one of the coefficients in this expansion and the required linear combinations can be evaluated efficiently. The particular cases where up to first and second order derivative information is available are treated in detail. The proof of the general case, where arbitrarily high order derivative information is available, involves algebraic arguments that make use of the theory of symmetric, functions.     

An algebraic approach to shape-from-image problems

This paper presents a new method for recovering three-dimensional shapes of polyhedral objects from their single-view images. The problem of recovery is formulated in a constrained optimization problem, in which the constraints reflect the assumption that the scene is composed of polyhedral objects, and the objective function to be minimized is a weighted sum of quadric errors of surface information such as shading and texture. For practical purpose it is decomposed into the two more tractable problems: a linear programming problem and an unconstrained optimization problem. In the present method the global constraints placed by the polyhedron assumption are represented in terms of linear algebra, whereas similar constraints have usually been represented in terms of a gradient space. Moreover, superstrictness of the constraints can be circumvented by a new concept ‘position-free incidence structure’. For this reason the present method has several advantages: it can recover the polyhedral shape even if image data are incorrect due to vertex-position errors, it can deal with perspective projection as well as orthographic projection, the number of variables in the optimization problem is very small (three or a little greater than three), and any kinds of surface information can be incorporated in a unifying manner.     

An algebraic approach to supervisory control

Supervisory control problems are formulated in terms of a process model where the mechanism of control is expressed in terms of an algebraic operator with the plant and supervision processes as its arguments. The solution subspaces for supervisory processes restrict the observation and the control capability of supervision. The main result corresponds to decentralized marked supervision under partial observations, and specific cases are derived from this result in a unified, algebraic way. The result and its derivation demonstrate the relative simplicity of the algebraic process formulation.     

An algebraic approach to feature interactions

The various approaches proposed to provide communication between CAD systems and process planning systems share the major problem that, due to geometric interactions among features, there may be several equally valid sets of manufacturable features describing the same part, and different sets of features may differ in their manufacturability. Thus, to produce a good process plan-or, in some cases, any plan at ll-it may be necessary to interpret the part as a different set of features than the one initially obtained from the CAD model. This is addressed using an algebra of features. Given a set of features describing a machinable part, other equally valid interpretations of the part can be produced by performing operations in the algebra. This will enable automated process planning systems to examine these interpretations in order to see which one is most appropriate for use in manufacturing. The feature algebra has been implemented for a restricted domain and integrated with the Protosolid solid modeling system and the EFHA process planning system     

Stability and nonsingular stable precompensation: An algebraic approach

The module theoretic framework in linear time invariant system theory is extended to include stability considerations as well. The resulting setup is then applied to an investigation of nonsingular, causal, and stable precompensation. The main issues are resolved through the introduction of two sets of integer invariants-thestability indices and thepole indices. The stability indices characterize the dynamical properties of all the stable systems that can be obtained from a specified system through the application of nonsingular, causal, and stable precompensation. The pole indices characterize the dynamical properties of all the nonsingular, causal, and stable precompensators that stabilize a specified system.     

An information retrieval approach for approximate queries

With the growing availability of online information systems, a need for user interfaces that are flexible and easy to use has arisen. For such type of systems, an interface that allows the formulation of approximate queries can be of great utility since these allow the user to quickly explore the database contents even when he is unaware of the exact values of the database instances. Our work focuses on this problem, presenting a new model for ranking approximate answers and a new algorithm to compute the semantic similarity between attribute values, based on information retrieval techniques. To demonstrate the utility and usefulness of the approach, we perform a series of usability tests. The results suggest that our approach allows the retrieval of more relevant answers with less effort by the user.     

An algebraic approach to iterative learning control

In this paper discrete-time iterative learning control (ILC) systems are analysed from an algebraic point of view. The algebraic analysis shows that a linear-time invariant single-input–single-output model can always represented equivalently as a static multivariable plant due to the finiteness of the time-axis. Furthermore, in this framework the ILC synthesis problem becomes a tracking problem of a multi-channel step-function. The internal model principle states that for asymptotic tracking (i.e. convergent learning) it is required that an ILC algorithm has to contain an integrator along the iteration axis, but at the same time the resulting closed-loop system should be stable. The question of stability can then be answered by analysing the closed-loop poles along the iteration axis using standard results from multivariable polynomial systems theory. This convergence theory suggests that time-varying ILC control laws should be typically used instead of time-invariant control laws in order to guarantee good transient tracking behaviour. Based on this suggestion a new adaptive ILC algorithm is derived, which results in monotonic convergence for an arbitrary linear discrete-time plant. This adaptive algorithm also has important implications in terms of future research work—as a concrete example it demonstrates that ILC algorithms containing adaptive and time-varying components can result in enhanced convergence properties when compared to fixed parameter ILC algorithms. Hence it can be expected that further research on adaptive learning mechanisms will provide a new useful source of high-performance ILC algorithms.     

An approximate microaggregation approach for microdata protection

Microdata protection is a hot topic in the field of Statistical Disclosure Control, which has gained special interest after the disclosure of 658,000 queries by the America Online (AOL) search engine in August 2006. Many algorithms, methods and properties have been proposed to deal with microdata disclosure. One of the emerging concepts in microdata protection is k-anonymity, introduced by Samarati and Sweeney. k-Anonymity provides a simple and efficient approach to protect private individual information and is gaining increasing popularity. k-Anonymity requires that every record in the microdata table released be indistinguishably related to no fewer than k respondents.In this paper, we apply the concept of entropy to propose a distance metric to evaluate the amount of mutual information among records in microdata, and propose a method of constructing dependency tree to find the key attributes, which we then use to process approximate microaggregation. Further, we adopt this new microaggregation technique to study k-anonymity problem, and an efficient algorithm is developed. Experimental results show that the proposed microaggregation technique is efficient and effective in the terms of running time and information loss.     

Verification of mobile ad hoc networks: An algebraic approach

We introduced Computed Network Process Theory to reason about protocols for mobile ad hoc networks (MANETs). Here we explore the applicability of our framework in two regards: model checking and equational reasoning. The operational semantics of our framework is based on constrained labeled transition systems (CLTSs), in which each transition label is parameterized with the set of topologies for which this transition is enabled. We illustrate how through model checking on CLTSs one can analyze mobility scenarios of MANET protocols. Furthermore, we show how by equational theory one can reason about MANETs consisting of a finite but unbounded set of nodes, in which all nodes deploy the same protocol. Model checking and equational reasoning together provide us with an appropriate framework to prove the correctness of MANETs. We demonstrate the applicability of our framework by a case study on a simple routing protocol.     

An algebraic method for processing colored images

An 8-valued commutative ring is developed to process colored images. Algebraic operators are defined to perform a number of operations such as the extraction of the primary colors and contours of different colors.     

The matrix partial realization problem: an algebraic approach

This paper introduces a new approach to the multivariable partial realization problem. It formulates the problem in algebraic terminology, which sheds new light on the nature of the problem and our existing knowledge of it. The structure of the state space is analysed in terms of polynomial models. The main idea is analysis of the algebraic structure of the kernels of truncated Hankel maps. The elements of such kernels are directly related to the partial realization problem, in the sense that the columns of the denominator matrix of a partial realization are elements of such kernels. The numerator matrix is determined by an appropriate denominator matrix