From qd to LR, or, how were the qd and LR algorithms discovered?

2010/05/27 by Martin H. Gutknecht, Beresford Ν. Parlett · 1 citation
Computer Science · Mathematics · #Numerical Methods and Algorithms #Matrix Theory and Algorithms #Iterative Methods for Nonlinear Equations #Algorithm #Mathematics #Library science #Computer science

paper · pdf · doi:10.1093/imanum/drq003

openalex publication_date 2010/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

Perhaps, the most astonishing idea in eigenvalue computation is Rutishauser's idea of applying the LR transform to a matrix for generating a sequence of similar matrices that become more and more triangular. The same idea is the foundation of the ubiquitous QR algorithm. It is well known that this idea originated in Rutishauser's qd algorithm, which precedes the LR algorithm and can be understood as applying LR to a tridiagonal matrix. But how did Rutishauser discover qd and when did he find the qd–LR connection? We checked some of the early sources and have come up with an explanation.

Citations

• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• Construction of Gauss-Christoffel quadrature formulas
• Report on the algorithmic language ALGOL 60
• Methods of conjugate gradients for solving linear systems

Cited by

• QR algorithm [wikipedia]

Related

• Differential qd algorithm with shifts for rank-structured matrices
• The QR Transformation A Unitary Analogue to the LR Transformation--Part 1
• A visualisation for conveying the dynamics of iterative eigenvalue algorithms over PSD matrices
• Numerical Linear Algebra: Least Squares, QR and SVD
• Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration