Pole swapping methods for the eigenvalue problem - Rational QR algorithms

Title slide

Abstract

Francis and Kublanovskaya independently introduced the implicit QR method, a bulge chasing algorithm, for computing all eigenvalues of a matrix in the 1960s. Their method has been the algorithm of choice to compute the Schur decomposition of small to medium sized problems and has been named as one of the top 10 algorithms of the twentieth century. In this work we generalize bulge chasing algorithms to pole swapping algorithms and show that this generalization has the benefit of an improved convergence rate. Where bulge chasing can be interpreted as subspace iteration accelerated by polynomials, pole swapping implicitly performs subspace iteration driven by rational functions. Numerical experiments show the competitiveness of our algorithms both in terms of accuracy and speed in comparison to LAPACK implementations, both for the standard and generalized eigenvalue problem.

Date
Sep 6, 2019 9:30 AM
Event
Berkeley Lab Seminar
Location
Lawrence Berkeley National Laboratory
1 Cyclotron Road, Berkeley, CA 94720
Daan Camps
Daan Camps
Researcher in Advanced Technologies Group

My research interests include quantum algorithms, numerical linear algebra, tensor factorization methods and machine learning. I’m particularly interested in studying the interface between HPC and quantum computing.

Related