Core-chasing algorithms for the eigenvalue problem.

*(English)*Zbl 1434.65003
Fundamentals of Algorithms 13. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-1-61197-533-8/pbk; 978-1-61197-534-5). ix, 149 p. (2018).

The monograph provides a detailed look at the new version of the Francis’s implicitly shifted QR algorithm, namely, the core-chasing algorithms. The key element of such class of algorithms, the core transformations, by which the QR decomposition of a matrix with a special structure can be achieved with economical storage requirement and computational cost, are defined in the first place.

It is always been known that the Francis’s method is a powerful iterative method for computing eigenvalues and is a bulge-chasing algorithm in its standard form. An iteration of Francis’s algorithm will create a tiny bulge disturbing the Hessenberg form of \(A\), then by a long sequence of elementary reflectors, the bulge will be chased down through the matrix until it is finally pushed off the bottom. However, if the matrix \(A\) is fairly large, cache misses will occur frequently during each iteration of standard Francis’s method, which entails a substantial delay of computing time.

The core-chasing approach behaves much better than the bulge-chasing method. It can efficiently minimize the cache misses and simplify the implementation of Francis’s algorithm in solving the eigenvalue problems with a variety of special structures. Four kinds of special cases, the unitary and unitary-plus-rank-one matrices, the symmetric matrices and symmetric-plus-rank-one matrices, are covered in this book which are treated by the core-chasing procedure with \(O(n)\) storage requirement and \(O(n^{2})\) computational cost. The authors also focus on the generalized and matrix polynomial eigenvalue problems, which can be tackled fast by the afore-mentioned backward stable algorithm.

The core-chasing algorithms are well-designed and efficient strategies to solve eigenvalue problems for matrices with a variety of special structures. The authors present these available methods in an organized fashion and comprehensive treatment. The material covered in this book will be a treasure of theory and practice for eigenvalue problems.

It is always been known that the Francis’s method is a powerful iterative method for computing eigenvalues and is a bulge-chasing algorithm in its standard form. An iteration of Francis’s algorithm will create a tiny bulge disturbing the Hessenberg form of \(A\), then by a long sequence of elementary reflectors, the bulge will be chased down through the matrix until it is finally pushed off the bottom. However, if the matrix \(A\) is fairly large, cache misses will occur frequently during each iteration of standard Francis’s method, which entails a substantial delay of computing time.

The core-chasing approach behaves much better than the bulge-chasing method. It can efficiently minimize the cache misses and simplify the implementation of Francis’s algorithm in solving the eigenvalue problems with a variety of special structures. Four kinds of special cases, the unitary and unitary-plus-rank-one matrices, the symmetric matrices and symmetric-plus-rank-one matrices, are covered in this book which are treated by the core-chasing procedure with \(O(n)\) storage requirement and \(O(n^{2})\) computational cost. The authors also focus on the generalized and matrix polynomial eigenvalue problems, which can be tackled fast by the afore-mentioned backward stable algorithm.

The core-chasing algorithms are well-designed and efficient strategies to solve eigenvalue problems for matrices with a variety of special structures. The authors present these available methods in an organized fashion and comprehensive treatment. The material covered in this book will be a treasure of theory and practice for eigenvalue problems.

Reviewer: Xueyuan Tan (Nanjing)

##### MSC:

65-02 | Research exposition (monographs, survey articles) pertaining to numerical analysis |

65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |

65F18 | Numerical solutions to inverse eigenvalue problems |

65H17 | Numerical solution of nonlinear eigenvalue and eigenvector problems |

15A23 | Factorization of matrices |