Matrix Computations and Semiseparable Matrices

Raf Vandebril is a researcher in the Department of Computer Science at Katholieke Universiteit Leuven, Belgium. Marc Van Barel is a professor of computer science at Katholieke Universiteit Leuven, Belgium. Nicola Mastronardi is a researcher at the M. Picone Institute for Applied Mathematics, Bari, Italy.

• PrefaceNotation1. Introduction to semiseparable matrices1.1. Definition of semiseparablematrices1.2. Some properties1.2.1. Relations under inversion1.2.2. Generator representable semiseparable matrices1.3. The representations1.3.1. The generator representation1.3.2. The Givens-vector representation1.4. ConclusionsI. The reduction of matrices2. Algorithms for reducing matrices2.1. Introduction2.1.1. Equivalence transformations2.1.2. Orthogonal transformations2.2. Orthogonal similarity transformations of symmetric matrices2.2.1. To tridiagonal form2.2.2. To semiseparable form2.2.3. To semiseparable plus diagonal form2.3. Orthogonal similarity transformation of (unsymmetric) matrices2.3.1. To Hessenberg form2.3.2. To Hessenberg-like form2.3.3. To Hessenberg-like plus diagonal form2.4. Orthogonal transformations of matrices2.4.1. To upper (lower) bidiagonal form2.4.2. To upper (lower) triangular semiseparable form2.4.3. Relation with the reduction to semiseparable form2.5. Transformations from sparse to structured rank form2.5.1. From tridiagonal to semiseparable (plus diagonal)2.5.2. From bidiagonal to upper triangular semiseparable2.6. From structured rank to sparse form2.6.1. From semiseparable (plus diagonal) to tridiagonal2.6.2. From semiseparable to bidiagonal2.7. Conclusions3. Convergence properties of the reduction algorithms3.1. The Arnoldi(Lanczos)-Ritz values3.1.1. Ritz values and Arnoldi(Lanczos)-Ritz values3.1.2. The reduction to semiseparable form3.1.3. Necessary conditions to obtain the Ritz values3.1.4. Sufficient conditions to obtain the Ritz values3.1.5. The case of invariant subspaces3.1.6. Some general remarks3.1.7. The different reduction algorithms revisited3.2. Subspace iteration inside the reduction algorithms3.2.1. The reduction to semiseparable form3.2.2. The reduction to semiseparable plus diagonal form3.2.3. Nested multishift iteration3.2.4. The different reduction algorithms revisited3.3. Interaction of the convergence behaviors3.3.1. The reduction to semiseparable form3.3.2. The reduction to semiseparable plus diagonal form3.3.3. Convergence speed of the nested multishift iteration3.3.4. The other reduction algorithms3.4. Conclusions4. Implementation of the algorithms and numerical experiments4.1. Working with Givens transformations4.1.1. Graphical schemes4.1.2. Interaction of Givens transformations4.1.3. Updating the representation4.1.4. The reduction algorithm revisited4.2. Implementation details4.2.1. Reduction to symmetric semiseparable form4.2.2. Reduction to semiseparable plus diagonal form4.2.3. Reduction to Hessenberg-like4.2.4. Reduction to upper triangular semiseparable form4.2.5. Computational complexities of the algorithms4.3. Numerical experiments4.3.1. The reduction to semiseparable form4.3.2. The reduction to semiseparable plus diagonal form4.4. ConclusionsII. QR-algorithms (eigenvalue problems)5. Introduction: traditional sparse QR-algorithms5.1. On the QR-algorithm5.1.1. The QR-factorization5.1.2. The QR-algorithm5.2. A QR-algorithmfor sparsematrices5.2.1. The QR-factorization5.2.2. Maintaining the Hessenberg structure5.3. An implicit QR-method for sparsematrices5.3.1. An implicit QR-algorithm5.3.2. Bulge chasing5.3.3. The implicit Q-theorem5.4. On computing the singular values5.5. Conclusion6. Theoretical results for structured rank QR-algorithms6.1. Preserving the structure under a QR-step6.1.1. The QR-factorization6.1.2. A QR-step maintains the rank structure6.2. An implicit Q-theorem6.2.1. Unreduced Hessenberg-like matrices6.2.2. The reduction to unreduced Hessenberg-like form6.2.3. An implicit Q-theorem for Hessenberg-like matrices6.3. On Hessenberg-like plus diagonal matrices6.4. Conclusions7. Implicit QR-methods for semiseparable matrices7.1. An implicit QR-algorithm for symmetric semiseparable matrices7.1.1. Unreduced symmetric semiseparable matrices7.1.2. The shift 7.1.3. An implicit QR-step7.1.4. Proof of the correctness of the implicit approach7.2. A QR-algorithm for semiseparable plus diagonal7.3. An implicit QR-algorithm for Hessenberg-like matrices7.3.1. The shift 7.3.2. An implicit QR-step on the Hessenberg-like matrix7.3.3. Chasing the disturbance7.3.4. Proof of correctness7.4. An implicit QR-algorithm for computing the singular values7.4.1. Unreduced upper triangular semiseparable matrices7.4.2. An implicit QR-step7.4.3. Chasing the bulge7.4.4. Proof of correctness7.5. Conclusions8. Implementation and numerical experiments8.1. Working with Givens transformations8.1.1. Interaction of Givens transformations8.1.2. Graphical interpretation of a QR-step8.1.3. A QR-step for semiseparable plus diagonal matrices8.2. Implementation of the QR-algorithm for semiseparable matrices8.2.1. The QR-algorithm without shift8.2.2. The reduction to unreduced form8.2.3. The QR-algorithmwith shift8.2.4. Deflation after a step of the QR-algorithm8.3. Computing the eigenvectors8.3.1. Computing all the eigenvectors8.3.2. Selected eigenvectors8.3.3. Preventing the loss of orthogonality8.3.4. The eigenvectors of an arbitrary symmetric matrix8.4. Numerical experiments8.4.1. On the symmetric eigenvalue solver8.4.2. Experiments for the singular value decomposition8.5. Conclusions9. More on QR-related algorithms9.1. Complex arithmetic and Givens transformations9.2. Variations of the QR-algorithm9.2.1. The QR-factorization and its variants9.2.2. Flexibility in the QR-algorithm9.2.3. The QR-algorithm and its variants9.3. The QR-method for quasiseparable matrices9.3.1. Definition and properties9.3.2. The QR-factorization and the QR-algorithm9.3.3. The implicit method9.4. The multishift QR-algorithm9.4.1. The multishift setting9.4.2. An efficient transformation from v to ße19.4.3. The chasing method9.4.4. The real Hessenberg-like case9.5. A QH-algorithm9.5.1. More on the QH-factorization9.5.2. Convergence and preservation of the structure9.5.3. An implicit QH-iteration9.5.4. The QR-iteration is a disguised QH-iteration9.5.5. Numerical experiments9.6. Computing zeros of polynomials9.6.1. Connection to eigen problems9.6.2. Unitary Hessenberg matrices9.6.3. Unitary plus rank 1 matrices9.6.4. Other methods9.7. References to related subjects9.7.1. Rational Krylov methods9.7.2. Sturm sequences9.7.3. Other references9.8. ConclusionsIII. Some generalizations and miscellaneous topics10. Divide-and-conquer algorithms for the eigen decomposition10.1. Arrowhead and diagonal plus rank 1 matrices10.1.1. Symmetric arrowhead matrices10.1.2. Computing the eigen vectors10.1.3. Rank 1 modification of a diagonal matrix10.2. Divide-and-conquer algorithms for tridiagonal matrices10.2.1. Transformation into a similar arrowhead matrix10.2.2. Transformation into a diagonal plus rank 110.3. Divide-and-conquer methods for quasiseparable matrices10.3.1. A first divide-and-conquer algorithm10.3.2. A straightforward divide-and-conquer algorithm10.3.3. A one-way divide-and-conquer algorithm10.3.4. A two-way divide-and-conquer algorithm10.4. Computational complexity and numerical experiments10.5. Conclusions11. A Lanczos-type algorithm and rank revealing11.1. Lanczos semiseparabilization11.1.1. Lanczos reduction to tridiagonal form11.1.2. Lanczos reduction to semiseparable form11.2. Rank-revealing properties of the orthogonal similarity reduction11.2.1. Symmetric rank-revealing factorization11.2.2. Rank-revealing via the semiseparable reduction11.2.3. Numerical experiments11.3. ConclusionsIV. Orthogonal (rational) functions (Inverse eigenvalue problems)12. Orthogonal polynomials and discrete least squares12.1. Recurrence relation and Hessenberg matrix12.2. Discrete inner product12.3. Inverse eigenvalue problem12.4. Polynomial least squares approximation12.5. Updating algorithm12.6. Special cases12.7. Conclusions13. Orthonormal polynomial vectors13.1. Vector approximants13.2. Equal degrees13.2.1. The optimization problem13.2.2. The algorithm13.2.3. Summary13.3. Arbitrary degrees13.3.1. The problem13.3.2. The algorithm13.3.3. Orthogonal vector polynomials13.3.4. Solution of the general approximation problem13.2. The singular case13.5. Conclusions14. Orthogonal rational functions14.1. The computation of orthonormal rational functions14.1.1. The functional problem14.1.2. The inverse eigenvalue problem14.1.3. Recurrence relation for the columns of Q14.1.4. Recurrence relation for the orthonormal functions14.2. Solving the inverse eigenvalue problem14.3. Special configurations of points zi14.3.1. Special case: all points zi are real14.3.2. Special case: all points zi lie on the unit circle14.3.3. Special case: all points zi lie on a generic circle14.4. Conclusions15. Concluding remarks & software15.1. Software15.2. ConclusionsBibliographyAuthor/ Editor IndexSubject Index

In particular, the relation with algorithms of historical interest will make the book interesting for its readers. -- Dietrich Braess Zentralblatt MATH 2009 An indispensable tool for scholars and research workers in mathematics and the mathematical sciences. Mathematical Reviews 2009