Matrix Computations and Semiseparable Matrices: Eigenvalue and Singular Value Methods

The general properties and mathematical structures of semiseparable matrices were presented in volume 1 of Matrix Computations and Semiseparable Matrices. In volume 2, Raf Vandebril, Marc Van Barel, and Nicola Mastronardi discuss the theory of structured eigenvalue and singular value computations for semiseparable matrices. These matrices have hidden properties that allow the development of efficient methods and algorithms to accurately compute the matrix eigenvalues. This thorough analysis of semiseparable matrices explains their theoretical underpinnings and contains a wealth of information on implementing them in practice. Many of the routines featured are coded in Matlab and can be downloaded from the Web for further exploration.

Table of Contents:
Preface Notations 1. Introduction to semiseparable matrices 1.1. Definition of semiseparable matrices 1.2. Some properties 1.2.1. Relations under inversion 1.2.2. Generator representable semiseparable matrices 1.3. The representations 1.3.1. The generator representation 1.3.2. The Givens-vector representation 1.4. Conclusions I. The reduction of matrices 2. Algorithms for reducing matrices 2.1. Introduction 2.1.1. Equivalence transformations 2.1.2. Orthogonal transformations 2.2. Orthogonal similarity transformations of symmetric matrices 2.2.1. To tridiagonal form 2.2.2. To semiseparable form 2.2.3. To semiseparable plus diagonal form 2.3. Orthogonal similarity transformation of (unsymmetric) matrices 2.3.1. To Hessenberg form 2.3.2. To Hessenberg-like form 2.3.3. To Hessenberg-like plus diagonal form 2.4. Orthogonal transformations of matrices 2.4.1. To upper (lower) bidiagonal form 2.4.2. To upper (lower) triangular semiseparable form 2.4.3. Relation with the reduction to semiseparable form 2.5. Transformations from sparse to structured rank form 2.5.1. From tridiagonal to semiseparable (plus diagonal) 2.5.2. From bidiagonal to upper triangular semiseparable 2.6. From structured rank to sparse form 2.6.1. From semiseparable (plus diagonal) to tridiagonal 2.6.2. From semiseparable to bidiagonal 2.7. Conclusions 3. Convergence properties of the reduction algorithms 3.1. The Arnoldi(Lanczos)-Ritz values 3.1.1. Ritz values and Arnoldi(Lanczos)-Ritz values 3.1.2. The reduction to semiseparable form 3.1.3. Necessary conditions to obtain the Ritz values 3.1.4. Sufficient conditions to obtain the Ritz values 3.1.5. The case of invariant subspaces 3.1.6. Some general remarks 3.1.7. The different reduction algorithms revisited 3.2. Subspace iteration inside the reduction algorithms 3.2.1. The reduction to semiseparable form 3.2.2. The reduction to semiseparable plus diagonal form 3.2.3. Nested multishift iteration 3.2.4. The different reduction algorithms revisited 3.3. Interaction of the convergence behaviors 3.3.1. The reduction to semiseparable form 3.3.2. The reduction to semiseparable plus diagonal form 3.3.3. Convergence speed of the nested multishift iteration 3.3.4. The other reduction algorithms 3.4. Conclusions 4. Implementation of the algorithms and numerical experiments 4.1. Working with Givens transformations 4.1.1. Graphical schemes 4.1.2. Interaction of Givens transformations 4.1.3. Updating the representation 4.1.4. The reduction algorithm revisited 4.2. Implementation details 4.2.1. Reduction to symmetric semiseparable form 4.2.2. Reduction to semiseparable plus diagonal form 4.2.3. Reduction to Hessenberg-like 4.2.4. Reduction to upper triangular semiseparable form 4.2.5. Computational complexities of the algorithms 4.3. Numerical experiments 4.3.1. The reduction to semiseparable form 4.3.2. The reduction to semiseparable plus diagonal form 4.4. Conclusions II. QR-algorithms (eigenvalue problems) 5. Introduction: Traditional Sparse QR-algorithms 5.1. On the QR-algorithm 5.1.1. The QR-factorization 5.1.2. The QR-algorithm 5.2. A QR-algorithm for sparse matrices 5.2.1. The QR-factorization 5.2.2. Maintaining the Hessenberg structure 5.3. An implicit QR-method for sparse matrices 5.3.1. An implicit QR-algorithm 5.3.2. Bulge chasing 5.3.3. The implicit Q-theorem 5.4. On computing the singular values 5.5. Conclusions 6. Theoretical results for structured rank QR-algorithms 6.1. Preserving the structure under a QR-step 6.1.1. The QR-factorization 6.1.2. A QR-step maintains the rank structure 6.2. An implicit Q-theorem 6.2.1. Unreduced Hessenberg-like matrices 6.2.2. The reduction to unreduced Hessenberg-like form 6.2.3. The reduction to unreduced Hessenberg-like forms 6.3. On Hessenberg-like plus diagonal matrices 6.4. Conclusions 7. Implicit QR-methods for semiseparable matrices 7.1. An implicit QR-algorithm for symmetric semiseparable matrices 7.1.1. Unreduced symmetric semiseparable matrices 7.1.2. The shift u 7.1.3. An implicit QR-step 7.1.4. Proof of the correctness of the implicit approach 7.2. A QR-algorithm for semiseparable plus diagonal 7.3. An implicit QR-algorithm for Hessenberg-like matrices 7.3.1. The shift u 7.3.2. An implicit QR-step on the Hessenberg-like matrix 7.3.3. Chasing the disturbance 7.3.4. Proof of correctness 7.4. An implicit QR-algorithm for computing the singular values 7.4.1. Unreduced upper triangular semiseparable matrices 7.4.2. An implicit QR-step 7.4.3. Chasing the bulge 7.4.4. Proof of correctness 7.5. Conclusions 8. Implementation and numerical experiments 8.1. Working with Givens transformations 8.1.1. Interaction of Givens transformations 8.1.2. Graphical interpretation of a QR-step 8.1.3. A QR-step for semiseparable plus diagonal matrices 8.2. Implementation of the QR-algorithm for semiseparable matrices 8.2.1. The QR-algorithm without shift 8.2.2. The reduction to unreduced form 8.2.3. The QR-algorithm with shift 8.2.4. Deflation after a step of the QR-algorithm 8.3. Computing the eigenvectors 8.3.1. Computing all the eigenvectors 8.3.2. Selected eigenvectors 8.3.3. Preventing the loss of orthogonality 8.3.4. The eigenvectors of an arbitrary symmetric matrix 8.4. Numerical experiments 8.4.1. On the symmetric eigenvalue solver 8.4.2. Experiments for the singular value decomposition 8.5. Conclusions 9. More on QR-related algorithms 9.1. Complex arithmetic and Givens transformations 9.2. Variations of the QR-algorithm 9.2.1. The QR-factorization and its variants 9.2.2. Flexibility in the QR-algorithm 9.2.3. The QR-algorithm and its variants 9.3. The QR-method for quasiseparable matrices 9.3.1. Definition and properties 9.3.2. The QR-factorization and the QR-algorithm 9.3.3. The implicit method 9.4. The multishift QR-algorithm 9.4.1. The multishift setting 9.4.2. An efficient transformation from v to ße1 9.4.3. The chasing method 9.4.4. The real Hessenberg-like case 9.5. A QH-algorithm 9.5.1. More on the QH-factorization 9.5.2. Convergence and preservation of the structure 9.5.3. An implicit QH-iteration 9.5.4. The QR-iteration is a disguised QH-iteration 9.5.5. Numerical experiments 9.6. Computing zeros of polynomials 9.6.1. Connection to eigenproblems 9.6.2. Unitary Hessenberg matrices 9.6.3. Unitary plus rank 1 matrices 9.6.4. Other methods 9.7. References to related subjects 9.7.1. Rational Krylov methods 9.7.2. Sturm sequences 9.7.3. Other references 9.8. Conclusions III. Some generalizations and miscellaneous topics 10. Divide-and-conquer algorithms for the eigendecomposition 10.1. Arrowhead and diagonal plus rank 1 matrices 10.1.1. Symmetric arrowhead matrices 10.1.2. Computing the eigenvectors 10.1.3. Rank 1 modification of a diagonal matrix 10.2. Divide-and-conquer algorithms for tridiagonal matrices 10.2.1. Transformation into a similar arrowhead matrix 10.2.2. Transformation into a diagonal plus rank 1 10.3. Divide-and-conquer methods for quasiseparable matrices 10.3.1. A first divide-and-conquer algorithm 10.3.2. A straightforward divide-and-conquer algorithm 10.3.3. A one-way divide-and-conquer algorithm 10.3.4. A two-way divide-and-conquer algorithm 10.4. Computational complexity and numerical experiments 10.5. Conclusions 11. A Lanczos-type algorithm and rank revealing 11.1. Lanczos semiseparabilization 11.1.1. Lanczos reduction to tridiagonal form 11.1.2. Lanczos reduction to semiseparable form 11.2. Rank-revealing properties of the orthogonal similarity reduction 11.2.1. Symmetric rank-revealing factorization 11.2.2. Rank-revealing via the semiseparable reduction 11.2.3. Numerical experiments 11.3. Conclusions IV. Orthogonal (rational) functions (Inverse eigenvalue problems) 12. Orthogonal polynomials and discrete least squares 12.1. Recurrence relation and Hessenberg matrix 12.2. Discrete inner product 12.3. Inverse eigenvalue problem 12.4. Polynomial least squares approximation 12.5. Updating algorithm 12.6. Special Cases 12.7. Conclusions 13. Orthonormal polynomial vectors 13.1. Vector approximants 13.2. Equal degrees 13.2.1. The optimization problem 13.2.2. The algorithm 13.2.3. Summary 13.3. Arbitrary degrees 13.3.1. The problem 13.3.2. The algorithm 13.3.3. Orthogonal vector polynomials 13.3.4. Solution of the general approximation problem 13.4. The singular case 13.5. Conclusions 14. Orthogonal rational functions 14.1. The computation of orthonormal rational functions 14.1.1. The functional problem 14.1.2. The inverse eigenvalue problem 14.1.3. Recurrence relation for the columns of Q 14.1.4. Recurrence relation for the orthonormal functions 14.2. Solving the inverse eigenvalue problem 14.3. Special configurations of points zi 14.3.1. Special case: all points zi are real 14.3.2. Special case: all points zi lie on the unit circle 14.3.3. Special case: all points zi lie on a generic circle 14.4. Conclusions 15. Concluding remarks & software 15.1. Software 15.2. Conclusions Bibliography Author/ Editor Index Subject Index