Use of the singular value decomposition to increase execution and storage efficiency of the Manteuffel algorithm for the solution of nonsymmetric linear systems /

Bibliography: p. 17-18.

Decomposition of graphs into trees /

"UILU-ENG 77 1715."

Lexicographic decomposition of chains and the concept of a planar chain

In an earlier paper [Journal of Mathematical Economics, 37 (2002) 17-38], we proved that if a preference relation on a commodity space is non-representable by a real-valued function then that chain is necessarily a long chain, a planar chain, an Aronszajn-like chain or a Souslin chain. In this paper, we study the class of planar chains, the simplest example of which is the Debreu chain (R-2, <(l)). (C) 2002 Elsevier Science B.V. All rights reserved.

Spin spaces and positive decomposition of linear maps on ordered Banach spaces

Spin factors and generalizations are used to revisit positive generation of B(E, F), where E and F are ordered Banach spaces. Interior points of B(E, F)+ are discussed and in many cases it is seen that positive generation of B(E, F) is controlled by spin structure in F when F is a JBW-algebra.

Black-box decomposition approach for computational hemodynamics: One-dimensional models

Increasing efforts exist in integrating different levels of detail in models of the cardiovascular system. For instance, one-dimensional representations are employed to model the systemic circulation. In this context, effective and black-box-type decomposition strategies for one-dimensional networks are needed, so as to: (i) employ domain decomposition strategies for large systemic models (1D-1D coupling) and (ii) provide the conceptual basis for dimensionally-heterogeneous representations (1D-3D coupling, among various possibilities). The strategy proposed in this article works for both of these two scenarios, though the several applications shown to illustrate its performance focus on the 1D-1D coupling case. A one-dimensional network is decomposed in such a way that each coupling point connects two (and not more) of the sub-networks. At each of the M connection points two unknowns are defined: the flow rate and pressure. These 2M unknowns are determined by 2M equations, since each sub-network provides one (non-linear) equation per coupling point. It is shown how to build the 2M x 2M non-linear system with arbitrary and independent choice of boundary conditions for each of the sub-networks. The idea is then to solve this non-linear system until convergence, which guarantees strong coupling of the complete network. In other words, if the non-linear solver converges at each time step, the solution coincides with what would be obtained by monolithically modeling the whole network. The decomposition thus imposes no stability restriction on the choice of the time step size. Effective iterative strategies for the non-linear system that preserve the black-box character of the decomposition are then explored. Several variants of matrix-free Broyden`s and Newton-GMRES algorithms are assessed as numerical solvers by comparing their performance on sub-critical wave propagation problems which range from academic test cases to realistic cardiovascular applications. A specific variant of Broyden`s algorithm is identified and recommended on the basis of its computer cost and reliability. (C) 2010 Elsevier B.V. All rights reserved.

Towards a maximal extension of Pelczynski`s decomposition method in Banach spaces

l Suppose that X, Y. A and B are Banach spaces such that X is isomorphic to Y E) A and Y is isomorphic to X circle plus B. Are X and Y necessarily isomorphic? In this generality. the answer is no, as proved by W.T. Cowers in 1996. In the present paper, we provide a very simple necessary and sufficient condition on the 10-tuples (k, l, m, n. p, q, r, s, u, v) in N with p+q+u >= 3, r+s+v >= 3, uv >= 1, (p,q)$(0,0), (r,s)not equal(0,0) and u=1 or v=1 or (p. q) = (1, 0) or (r, s) = (0, 1), which guarantees that X is isomorphic to Y whenever these Banach spaces satisfy X(u) similar to X(p)circle plus Y(q), Y(u) similar to X(r)circle plus Y(s), and A(k) circle plus B(l) similar to A(m) circle plus B(n). Namely, delta = +/- 1 or lozenge not equal 0, gcd(lozenge, delta (p + q - u)) divides p + q - u and gcd(lozenge, delta(r + s - v)) divides r + s - v, where 3 = k - I - in + n is the characteristic number of the 4-tuple (k, l, m, n) and lozenge = (p - u)(s - v) - rq is the discriminant of the 6-tuple (p, q, r, s, U, v). We conjecture that this result is in some sense a maximal extension of the classical Pelczynski`s decomposition method in Banach spaces: the case (1, 0. 1, 0, 2. 0, 0, 2. 1. 1). (C) 2009 Elsevier Inc. All rights reserved.

Generalizations of Pelczynski`s decomposition method for Banach spaces containing a complemented copy of their squares

Suppose that X and Y are Banach spaces isomorphic to complemented subspaces of each other. In 1996, W. T. Gowers solved the Schroeder- Bernstein Problem for Banach spaces by showing that X is not necessarily isomorphic to Y. However, if X-2 is complemented in X with supplement A and Y-2 is complemented in Y with supplement B, that is, { X similar to X-2 circle plus A Y similar to Y-2 circle plus B, then the classical Pelczynski`s decomposition method for Banach spaces shows that X is isomorphic to Y whenever we can assume that A = B = {0}. But unfortunately, this is not always possible. In this paper, we show that it is possible to find all finite relations of isomorphism between A and B which guarantee that X is isomorphic to Y. In order to do this, we say that a quadruple (p, q, r, s) in N is a P-Quadruple for Banach spaces if X is isomorphic to Y whenever the supplements A and B satisfy A(p) circle plus B-q similar to A(r) circle plus B-s . Then we prove that (p, q, r, s) is a P-Quadruple for Banach spaces if and only if p - r = s - q = +/- 1.

The sigma-isotypic decomposition and the sigma-index of reversible-equivariant systems

This work is concerned with dynamical systems in presence of symmetries and reversing symmetries. We describe a construction process of subspaces that are invariant by linear Gamma-reversible-equivariant mappings, where Gamma is the compact Lie group of all the symmetries and reversing symmetries of such systems. These subspaces are the sigma-isotypic components, first introduced by Lamb and Roberts in (1999) [10] and that correspond to the isotypic components for purely equivariant systems. In addition, by representation theory methods derived from the topological structure of the group Gamma, two algebraic formulae are established for the computation of the sigma-index of a closed subgroup of Gamma. The results obtained here are to be applied to general reversible-equivariant systems, but are of particular interest for the more subtle of the two possible cases, namely the non-self-dual case. Some examples are presented. (C) 2011 Elsevier BM. All rights reserved.

HIGH PERFORMANCE, LOW COST SUBSPACE DECOMPOSITION AND POLYNOMIAL ROOTING FOR REAL TIME DIRECTION OF ARRIVAL ESTIMATION: ANALYSIS AND IMPLEMENTATION

This thesis develops high performance real-time signal processing modules for direction of arrival (DOA) estimation for localization systems. It proposes highly parallel algorithms for performing subspace decomposition and polynomial rooting, which are otherwise traditionally implemented using sequential algorithms. The proposed algorithms address the emerging need for real-time localization for a wide range of applications. As the antenna array size increases, the complexity of signal processing algorithms increases, making it increasingly difficult to satisfy the real-time constraints. This thesis addresses real-time implementation by proposing parallel algorithms, that maintain considerable improvement over traditional algorithms, especially for systems with larger number of antenna array elements. Singular value decomposition (SVD) and polynomial rooting are two computationally complex steps and act as the bottleneck to achieving real-time performance. The proposed algorithms are suitable for implementation on field programmable gated arrays (FPGAs), single instruction multiple data (SIMD) hardware or application specific integrated chips (ASICs), which offer large number of processing elements that can be exploited for parallel processing. The designs proposed in this thesis are modular, easily expandable and easy to implement. Firstly, this thesis proposes a fast converging SVD algorithm. The proposed method reduces the number of iterations it takes to converge to correct singular values, thus achieving closer to real-time performance. A general algorithm and a modular system design are provided making it easy for designers to replicate and extend the design to larger matrix sizes. Moreover, the method is highly parallel, which can be exploited in various hardware platforms mentioned earlier. A fixed point implementation of proposed SVD algorithm is presented. The FPGA design is pipelined to the maximum extent to increase the maximum achievable frequency of operation. The system was developed with the objective of achieving high throughput. Various modern cores available in FPGAs were used to maximize the performance and details of these modules are presented in detail. Finally, a parallel polynomial rooting technique based on Newton’s method applicable exclusively to root-MUSIC polynomials is proposed. Unique characteristics of root-MUSIC polynomial’s complex dynamics were exploited to derive this polynomial rooting method. The technique exhibits parallelism and converges to the desired root within fixed number of iterations, making this suitable for polynomial rooting of large degree polynomials. We believe this is the first time that complex dynamics of root-MUSIC polynomial were analyzed to propose an algorithm. In all, the thesis addresses two major bottlenecks in a direction of arrival estimation system, by providing simple, high throughput, parallel algorithms.

On decomposition of sub-linearised polynomials

We give a detailed exposition of the theory of decompositions of linearised polynomials, using a well-known connection with skew-polynomial rings with zero derivative. It is known that there is a one-to-one correspondence between decompositions of linearised polynomials and sub-linearised polynomials. This correspondence leads to a formula for the number of indecomposable sub-linearised polynomials of given degree over a finite field. We also show how to extend existing factorisation algorithms over skew-polynomial rings to decompose sub-linearised polynomials without asymptotic cost.

Decomposition of complete graphs into 5-cubes

Necessary conditions for the complete graph on n vertices to have a decomposition into 5-cubes are that 5 divides it - 1 and 80 divides it (it - 1)/2. These are known to be sufficient when n is odd. We prove them also sufficient for it even, thus completing the spectrum problem for the 5-cube and lending further weight to a long-standing conjecture of Kotzig. (c) 2005 Wiley Periodicals, Inc.

On Hamilton cycle decomposition of 6-regular circulant graphs

The circulant graph Sn, where S ⊆ Zn \ {0}, has vertex set Zn and edge set {{x, x + s}|x ∈ Zn, s ∈ S}. It is shown that there is a Hamilton cycle decomposition of every 6-regular circulant graph Sn in which S has an element of order n.