Matrix Computations and Semiseparable Matrices: Eigenvalue and Singular Value Methods

Part III Some generalizations and miscellaneous topics

Part III Some generalizations and miscellaneous topics 363 This page intentionally left blank 365 In the first two parts of this book the standard algorithms for computing the eigendecomposition of matrices were discussed. Reduction algorithms to structured rank matrices were discussed, as well as the accompanying QR-methods. In this part we will discuss some topics that are slightly more general than the ones from the first two parts. We will discuss an iterative method for reducing the matrices to structured rank form, a rank-revealing method will be presented and finally we will discuss a divide-and-conquer method for computing the eigendecomposition of quasiseparable matrices. Chapter 10 discusses divide-and-conquer methods for computing the eigendecomposition . Important for the development of these methods are the interlacing properties of eigenvalues for arrowhead and diagonal plus rank one matrices. This property is first studied in Section 10.1. Section 10.2 proposes two methods for computing the eigendecomposition of tridiagonal matrices. One method is based on the use of arrowhead matrices whereas the other method makes use of diagonal plus rank one matrices. Section 10.3 discusses four different divide-and-conquer methods for computing eigenvalues and eigenvectors of quasiseparable matrices. Finally also numerical experiments are provided. Chapter 11 discusses two topics. Firstly, in Section 11.1, an iterative method for reducing matrices to semiseparable form is presented. The classical Lanczos method for tridiagonal matrices is discussed first, followed by the algorithm for transforming matrices to semiseparable form. Section 11.2 discusses some details to exploit the convergence properties of the reduction algorithms. It is shown how to adapt the reduction method to be able to use it as a rank-revealing factorization. ✎ This part contains extra material that is not essential anymore for further understanding of the book. Nevertheless, Chapter 10, discussing the divideand -conquer methods is very interesting as it provides a fast and accurate method for computing the eigendecomposition of quasiseparable matrices. In Chapter 11, Section 11.1.2 contains the iterative Lanczos-like version for reducing a matrix to semiseparable form. This page intentionally left blank ...