3,794 research outputs found
Principal pivot transforms of quasidefinite matrices and semidefinite lagrangian subspaces
No full textLagrangian subspaces are linear subspaces that appear naturally in control theory applications, and especially in the context of algebraic Riccati equations. In this paper, a class of semidefinite Lagrangian subspaces is introduced and it is shown that these subspaces can be represented by a subset I ⊆ 1, 2,..., n and a Hermitian matrix X ∈ Cn×n with the property that the submatrix XII is negative semidefinite and the submatrix XIcIc is positive semidefinite. A matrix X with these definiteness properties is called I-semidefinite and it is a generalization of a quasidefinite matrix. Under mild hypotheses which hold true in most applications, the Lagrangian subspace associated to the stabilizing solution of an algebraic Riccati equation is semidefinite, and in addition it is shown that there is a bijection between Hamiltonian and symplectic pencils and semidefinite Lagrangian subspaces; hence, this structure is ubiquitous in control theory. The (symmetric) principal pivot transform (PPT) is a map used by Mehrmann and Poloni [V. Mehrmann and F. Poloni. Doubling algorithms with permuted Lagrangian graph bases. SIAM J. Matrix Anal. Appl., 33:780–805, 2012. to convert between two different pairs (I,X) and (J,X ′) representing the same Lagrangian subspace. For a semidefinite Lagrangian subspace, it is proven that the symmetric PPT of an I-semidefinite matrix X is a J -semidefinite matrix X ′, and an implementation of the transformation X → X ′ that both makes use of the definiteness properties of X and guarantees the definiteness of the submatrices of X ′ in finite arithmetic is derived. The resulting formulas are used to obtain a semidefiniteness-preserving version of an optimization algorithm introduced by Mehrmann and Poloni to compute a pair (Iopt,Xopt) with Mopt = maxi,j |(Xopt)ij | as small as possible. Using semidefiniteness allows one to obtain a stronger inequality on M with respect to the general case
Algorithms for quadratic matrix and vector equations
No full textThis book is devoted to studying algorithms for the solution of a class of quadratic matrix and vector equations. These equations appear, in different forms, in several practical applications, especially in applied probability and control theory. The equations are first presented using a novel unifying approach; then, specific numerical methods are presented for the cases most relevant for applications, and new algorithms and theoretical results developed by the author are presented. The book focuses on “matrix multiplication-rich” iterations such as cyclic reduction and the structured doubling algorithm (SDA) and contains a variety of new research results which, as of today, are only available in articles or preprints
Permuted graph matrices and their applications
No full textA permuted graph matrix is a matrix V ∈ C(m+n)×m such that every row of the m × m identity matrix Im appears at least once as a row of V. Permuted graph matrices can be used in some contexts in place of orthogonal matrices, for instance when giving a basis for a subspace μ ⊆ cm+nor to normalize matrix pencils in a suitable sense. In these applications the permuted graph matrix can be chosen with bounded entries, which is useful for stability reasons; several algorithms can be formulated with numerical advantage with permuted graph matrices.We present the basic theory and review some applications from optimization or in control theory. © Springer International Publishing Switzerland 2015
CONSTRUCTING MATRIX GEOMETRIC MEANS
No full textIn this paper, we analyze the process of “assembling” new matrix geometric means from existing ones, through function composition or limit processes. We show that for n = 4 a new matrix mean exists which is simpler to compute than the existing ones. Moreover, we show that for n > 4 the existing proving strategies cannot provide a mean computationally simpler than the existing ones
A subspace shift technique for nonsymmetric algebraic Riccati equations associated with an M-matrix
No full textThe worst situation in computing the minimal nonnegative solution
of a nonsymmetric algebraic Riccati equation associated with an M-matrix occurs when the corresponding linearizing matrix has two very small eigenvalues, one with positive and one with negative real part. When both these eigenvalues are exactly zero, the problem is called critical or null recurrent. While in this case the problem is ill-conditioned and the convergence of the algorithms based on matrix iterations is slow, there exist some techniques to remove the singularity and transform the problem to a well-behaved one. Ill-conditioning and slow convergence appear also in close-to-critical problems, but when none of the eigenvalues is exactly zero the techniques used for the critical case cannot be applied. In this paper, we introduce a new method to accelerate the convergence properties of the iterations also in close-to-critical cases, by working on theinvariant subspace associated with the problematic eigenvalues as a whole. We present numerical experiments which confirm the efficiency of the new method
Perron-based algorithms for the multilinear PageRank
No full textWe consider the multilinear PageRank problem, studied in a 2015 paper by Gleich, Lim and Yu, which is a system of quadratic equations with stochasticity and nonnegativity constraints. We use the theory of quadratic vector equations to prove several properties of its solutions and suggest new numerical algorithms. In particular, we prove the existence of a certain minimal solution, which does not always coincide with the stochastic one that is required by the problem. We use an interpretation of the solution as a Perron eigenvector to devise new fixed-point algorithms for its computation and pair them with a continuation strategy based on a perturbative approach. The resulting numerical method is more reliable than the existing alternatives, being able to solve a larger number of problem
Quadratic vector equations
No full textWe study in a unified fashion several quadratic vector and matrix equations with nonnegativity hypotheses, by seeing them as special cases of the general problem Mx=a+b(x,x), where a and the unknown x are componentwise nonnegative vectors, M is a nonsingular M-matrix, and b is a bilinear map from pairs of nonnegative vectors to nonnegative vectors. Specific cases of this equation have been studied extensively in the past by several authors, and include unilateral matrix equations from queuing problems (Bini, Latouche, and Meini, 2005 [7]), nonsymmetric algebraic Riccati equations (Guo and Laub, 2000 [14]), and quadratic matrix equations encountered in neutron transport theory (Lu, 2005 [23,24]). We present a unified approach which treats the common aspects of their theoretical properties and basic iterative solution algorithms. This has interesting consequences: in some cases, we are able to derive in full generality theorems and proofs appeared in literature only for special cases of the problem; this broader view highlights the role of hypotheses such as the strict positivity of the minimal solution. In an example, we adapt an algorithm derived for one equation of the class to another, with computational advantage with respect to the existing methods. We discuss possible research lines, including the relationship among Newton-type methods and the cyclic reduction algorithm for unilateral quadratic equations. © 2011 Elsevier Inc. All rights reserved
A note on the O(n)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices
No full text
- …
