Eigenvalue computations are ubiquitous in science and engineering. John Francis's implicitly shifted QR algorithm has been the method of choice for small to medium sized eigenvalue problems since its invention in 1959. This book presents a new view of this classical algorithm. While Francis's original procedure chases bulges, the new version chases core transformations, which allows the development of fast algorithms for eigenvalue problems with a variety of special structures. This also leads to a fast and backward stable algorithm for computing the roots of a polynomial by solving the companion matrix eigenvalue problem. The authors received a SIAM Outstanding Paper prize for this work. This book will be of interest to researchers in numerical linear algebra and their students. "For the past 50 years the workhorse algorithm for solving eigenvalue problems has been Francis's implictly shifted QR algorithm. We present here a new formulation of Francis's algorithm that operates on the QR factors of a matrix A rather than A itself. This is not in any existing book. A popular way to compute the roots of a polynomial is to form the companion matrix and compute its eigenvalues (which are exactly the roots of the polynomial). This is what Matlab's roots command does. Our new formulation leads to a better algorithm for solving the companion eigenvalue problem (which is unitary-plus-rank-one). Our algorithm is faster than all of the competing algorithms. We can prove it is backward stable, and it is stable in a stronger sense than the algorithm that Matlab uses. Thus our algorithm is faster and more accurate than Matlab's. In the final chapter we present a generalization of Francis's algorithm that we published (in a SIAM journal) a few years ago. This applies to all classes of eigenvalue problems, structured or not. This is not in any book. Our monograph presents a unified treatment of several classes of eigenvalue problems. We listed them above, but here they are again: unitary, unitary-plus-rank-one (companion matrices and pencils), symmetric, symmetic-plus-rank-one, matrix polynomials. We also provide new insights into matrix eigenvalue problems with no special structure. These are the results of our research of the past few years. This is hot off the press. Most of this material has appeared in our publications, but none of it is in any book. In recent conference presentations we have mentioned that we are working on a book. Informal feedback suggests there is significant interest in this book among researchers in numerical linear algebra"-- Provided by publisher 1.9781611975345.fm 1.9781611975345.ch1 1.9781611975345.ch2 1.9781611975345.ch3 1.9781611975345.ch4 1.9781611975345.ch5 1.9781611975345.ch6 1.9781611975345.bm
