Refining estimates of invariant and deflating subspaces for large and sparse matrices and pencils

We consider the refinement of estimates of invariant (or deflating) subspaces for a large and sparse real matrix (or pencil) in $\mathbb {R}^{n \times n}$ , through some (generalized) nonsymmetric algebraic Riccati equations or their associated (generalized) Sylvester equations via Newton’s method. The crux of the method is the inversion of some well-conditioned unstructured matrices via the efficient and stable inversion of the associated structured but near-singular matrices. All computations have complexity proportional to $n$ , under appropriate assumptions, as illustrated by several numerical examples.     

A reduction technique for discrete generalized algebraic and difference Riccati equations

This paper proposes a reduction technique for the generalized Riccati difference equation arising in optimal control and optimal filtering. This technique relies on a study on the generalized discrete algebraic Riccati equation. In particular, an analysis on the eigenstructure of the corresponding extended symplectic pencil enables to identify a subspace in which all the solutions of the generalized discrete algebraic Riccati equation are coincident. This subspace is the key to derive a decomposition technique for the generalized Riccati difference equation. This decomposition isolates a “nilpotent” part, which converges to a steady-state solution in a finite number of steps, from another part that can be computed by iterating a reduced-order generalized Riccati difference equation.     

Circular trichotomy of the spectrum of regular matrix pencils

We introduce a method for approximating the right and left deflating subspaces of a regular matrix pencil corresponding to the eigenvalues inside, on and outside the unit circle. The method extends the iteration used in the context of spectral dichotomy, where the assumption on the absence of eigenvalues on the unit circle is removed. It constructs two matrix sequences whose null spaces and the null space of their sum lead to approximations of the deflating subspaces corresponding to the eigenvalues of modulus less than or equal to 1, equal to 1 and larger than or equal to 1. An orthogonalization process is then used to extract the desired delating subspaces. The resulting algorithm is an inverse free, easy to implement, and sufficiently fast. The derived convergence estimates reveal the key parameters, which determine the rate of convergence. The method is tested on several numerical examples.     

The double deflating technique for irreducible singular M-matrix algebraic Riccati equations in the critical case

As is known, Alternating-Directional Doubling Algorithm (ADDA) is quadratically convergent for computing the minimal nonnegative solution of an irreducible singular M-matrix algebraic Riccati equation (MARE) in the noncritical case or a nonsingular MARE, but ADDA is only linearly convergent in the critical case. The drawback can be overcome by deflating techniques for an irreducible singular MARE so that the speed of quadratic convergence is still preserved in the critical case and accelerated in the noncritical case. In this paper, we proposed an improved deflating technique to accelerate further the convergence speed – the double deflating technique for an irreducible singular MARE in the critical case. We proved that ADDA is quadratically convergent instead of linearly when it is applied to the deflated algebraic Riccati equation (ARE) obtained by a double deflating technique. We also showed that the double deflating technique is better than the deflating technique from the perspective of dimension of the deflated ARE. Numerical experiments are provided to illustrate that our double deflating technique is effective.     

An Arithmetic for Matrix Pencils: Theory and New Algorithms

This paper introduces arithmetic-like operations on matrix pencils. The pencil-arithmetic operations extend elementary formulas for sums and products of rational numbers and include the algebra of linear transformations as a special case. These operations give an unusual perspective on a variety of pencil related computations. We derive generalizations of monodromy matrices and the matrix exponential. A new algorithm for computing a pencil-arithmetic generalization of the matrix sign function does not use matrix inverses and gives an empirically forward numerically stable algorithm for extracting deflating subspaces.Some of this work was completed at the University of Kansas. Partial support received by Deutsche Forschungsgemeinschaft, grant BE 2174/4-1.This material is based upon work partially supported by the DFG Research Center “Mathematics for Key Technologies” (MATHEON) in Berlin, the University of Kansas General Research Fund allocation 2301062-003 and by the National Science Foundation under awards 0098150, 0112375 and 9977352.     

An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems

Summary. We discuss an inverse-free, highly parallel, spectral divide and conquer algorithm. It can compute either an invariant subspace of a nonsymmetric matrix , or a pair of left and right deflating subspaces of a regular matrix pencil . This algorithm is based on earlier ones of Bulgakov, Godunov and Malyshev, but improves on them in several ways. This algorithm only uses easily parallelizable linear algebra building blocks: matrix multiplication and QR decomposition, but not matrix inversion. Similar parallel algorithms for the nonsymmetric eigenproblem use the matrix sign function, which requires matrix inversion and is faster but can be less stable than the new algorithm. Received September 20, 1994 / Revised version received February 5, 1996     

Spectral factorization of non-symmetric polynomial matrices

The topic of the paper is spectral factorization of rectangular and possibly non-full-rank polynomial matrices. To each polynomial matrix we associate a matrix pencil by direct assignment of the coefficients. The associated matrix pencil has its finite generalized eigenvalues equal to the zeros of the polynomial matrix. The matrix dimensions of the pencil we obtain by solving an integer linear programming (ILP) minimization problem. Then by extracting a deflating subspace of the pencil we come to the required spectral factorization. We apply the algorithm to most general-case of inner–outer factorization, regardless continuous or discrete time case, and to finding the greatest common divisor of polynomial matrices.     

Spectral division methods for block generalized Schur decompositions

We provide a different perspective of the spectral division methods for block generalized Schur decompositions of matrix pairs. The new approach exposes more algebraic structures of the successive matrix pairs in the spectral division iterations and reveals some potential computational difficulties. We present modified algorithms to reduce the arithmetic cost by nearly 50%, remove inconsistency in spectral subspace extraction from different sides (left and right), and improve the accuracy of subspaces. In application problems that only require a single-sided deflating subspace, our algorithms can be used to obtain a posteriori estimates on the backward accuracy of the computed subspaces with little extra cost.

     

Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

A fast algorithm for solving systems of linear equations with banded Toeplitz matrices is studied. An important step in the algorithm is a novel method for the spectral factorization of the generating function associated with the Toeplitz matrix. The spectral factorization is extracted from the right deflating subspaces corresponding to the eigenvalues inside and outside the open unit disk of a companion matrix pencil constructed from the coefficients of the generating function. The factorization is followed by the Woodbury inversion formula and solution of several banded triangular systems. Stability of the algorithm is discussed and its performance is demonstrated by numerical experiments. Copyright © 2012 John Wiley & Sons, Ltd.     

计算对称带状矩阵广义特征值问题的并行分治多分法

1 引 言 本文研究了广义特征值问题 Ax=λBx (1)的并行计算。其中,A,B均为半带宽为r的n阶实对称带状矩阵且其中之一是正定的.本文总假设B是正定的.     

RICE CONDITION NUMBERS OF CERTAIN CHARACTERISTIC SUBSPACES

This paper proposes the Rice condition numbers for invariant subspace, singular sub-spaces of a matrix and deflating subspaces of a regular matrix pair. The first-order perturbation estimations for these subspaces are derived by applying perturbation expansions of orthogonal projection operators.     

A MODIFIED INVERSE ITERATION FOR A LARGE SPARSE SPD GENERALIZED EIGENPROBLEM

In this paper, an algorithm based on a shifted inverse power iteration for computing generalized eigenvalues with corresponding eigenvectors of a large scale sparse symmetric positive definite matrix pencil is presented. It converges globally with a cubic asymptotic convergence rate, preserves sparsity of the original matrices and is fully parallelizable. The algebraic multilevel itera-tion method (AMLI) is used to improve the efficiency when symmetric positive definite linear equa-tions need to be solved.     

On Some Spectral Characteristics of Multiparameter Polynomial Matrices

Definitions of certain spectral characteristics of polynomial matrices (such as the analytical (algebraic) and geometric multiplicities of a point of the spectrum, deflating subspaces, matrix solvents, and block eigenvalues and eigenvectors) are generalized to the multiparameter case, and properties of these characteristics are analyzed. Bibliogrhaphy: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 166–173.     

Verified Computation of Eigenpairs in the Generalized Eigenvalue Problem for Nonsquare Matrix Pencils

Consider an optimization problem arising from the generalized eigenvalue problem Ax=λBx,where A,B∈Cm×n and m>n.Ito et al.showed that the optimization problem can be solved by utilizing right singular vectors of C:=[B,A].In this paper,we focus on computing intervals containing the solution.When some singular values of C are multiple or nearly multiple,we can enclose bases of corresponding invariant subspaces of CHC,where CH denotes the conjugate transpose of C,but cannot enclose the corresponding right singular vectors.The purpose of this paper is to prove that the solution can be obtained even when we utilize the bases instead of the right singular vectors.Based on the proved result,we propose an algorithm for computing the intervals.Numerical results show property of the algorithm.     

A Cache-Aware Implementation of the Spectral Divide-and-Conquer Approach for the Non-Symmetric Generalized Eigenvalue Problem

We propose a new implementation of the sign function based spectral divide-and-conquer method for the generalized non-symmetric eigenvalue problem. The basic idea is to use the generalized matrix sign function to split the spectrum and the corresponding deflating subspaces and to build a recursive scheme on top of this. The method focuses on an extensive usage of scalable level 3 BLAS operations in order to achieve a good performance on modern computer architectures which makes it computationally superior to current implementations of the classical QZ algorithm. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Wave Field Decomposition in Anisotropic Fluids: A Spectral Theory Approach

An extension of directional wave field decomposition in acoustics from heterogenous isotropic media to generic heterogenous anisotropic media is established. We make a connection between the Dirichlet-to-Neumann map for a level plane, the solution to an algebraic Riccati operator equation, and a projector defined via a Dunford–Taylor type integral over the resolvent of a nonnormal, noncompact matrix operator with continuous spectrum.In the course of the analysis, the spectrum of the Laplace transformed acoustic system's matrix is analyzed and shown to separate into two nontrivial parts. The existence of a projector is established and using a generalized eigenvector procedure, we find the solution to the associated algebraic Riccati operator equation. The solution generates the decomposition of the wave field and is expressed in terms of the elements of a Dunford–Taylor type integral over the resolvent.     

Perturbation analysis of singular subspaces and deflating subspaces

Summary. Perturbation expansions for singular subspaces of a matrix and for deflating subspaces of a regular matrix pair are derived by using a technique previously described by the author. The perturbation expansions are then used to derive Fr\'echet derivatives, condition numbers, and th-order perturbation bounds for the subspaces. Vaccaro's result on second-order perturbation expansions for a special class of singular subspaces can be obtained from a general result of this paper. Besides, new perturbation bounds for singular subspaces and deflating subspaces are derived by applying a general theorem on solution of a system of nonlinear equations. The results of this paper reveal an important fact: Each singular subspace and each deflating subspace have individual perturbation bounds and individual condition numbers. Received July 26, 1994     

Computing eigenspaces with specified eigenvalues of a regular matrix pair (A,B) and condition estimation: theory,algorithms and software

Theory, algorithms and LAPACK-style software for computing a pair of deflating subspaces with specified eigenvalues of a regular matrix pair (A, B) and error bounds for computed quantities (eigenvalues and eigenspaces) are presented. Thereordering of specified eigenvalues is performed with a direct orthogonal transformation method with guaranteed numerical stability. Each swap of two adjacent diagonal blocks in the real generalized Schur form, where at least one of them corresponds to a complex conjugate pair of eigenvalues, involves solving a generalized Sylvester equation and the construction of two orthogonal transformation matrices from certain eigenspaces associated with the diagonal blocks. The swapping of two 1×1 blocks is performed using orthogonal (unitary) Givens rotations. Theerror bounds are based on estimates of condition numbers for eigenvalues and eigenspaces. The software computes reciprocal values of a condition number for an individual eigenvalue (or a cluster of eigenvalues), a condition number for an eigenvector (or eigenspace), and spectral projectors onto a selected cluster. By computing reciprocal values we avoid overflow. Changes in eigenvectors and eigenspaces are measured by their change in angle. The condition numbers yield bothasymptotic andglobal error bounds. The asymptotic bounds are only accurate for small perturbations (E, F) of (A, B), while the global bounds work for all (E, F.) up to a certain bound, whose size is determined by the conditioning of the problem. It is also shown how these upper bounds can be estimated. Fortran 77software that implements our algorithms for reordering eigenvalues, computing (left and right) deflating subspaces with specified eigenvalues and condition number estimation are presented. Computational experiments that illustrate the accuracy, efficiency and reliability of our software are also described.     

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves

The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user‐defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix–vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.