SIAG/LA Prize Winners Speed Up the QR Algorithm
November 1, 2003
Recipients of the 2003 SIAM Activity Group on Linear Algebra Prize (from left) Roy Mathias, Karen Braman, and Ralph Byers accept the congratulations of SIAG/LA chair Nicholas Higham. In their prize-winning work, according to the prize committee, the researchers made significant improvements to "one of the best established numerical algorithms"---the QR algorithm for solving the nonsymmetric eigenvalue problem.
Nicholas J. Higham
Karen Braman and Ralph Byers, both of the University of Kansas, and Roy Mathias of the College of William & Mary received the 2003 SIAM Activity Group on Linear Algebra Prize at the SIAM Conference on Applied Linear Algebra, held at the College of William & Mary, Williamsburg, Virginia, July 15-19, 2003. The researchers were recognized for their paper "The Multishift QR Algorithm. Part II: Aggressive Early Deflation."[1]
"This elegant paper on solution of large dense eigenvalue problems blends theory and computational experiments to significantly improve one of the best established numerical algorithms," the prize committee wrote in the citation. The members of the committee were Ludwig Elsner (University of Bremen), Anne Greenbaum (University of Washington, Seattle), Bo Kagstrom (Ume� University), Nick Trefethen (University of Oxford), and chair Steve Vavasis (Cornell University).
The QR algorithm for solving the nonsymmetric eigenvalue problem is one of the jewels in the crown of matrix computations. Nominated by Jack Dongarra and Francis Sullivan [2] as one of the "10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century," the QR algorithm has allowed routine solution of the eigenvalue problem since its invention in the early 1960s. As Beresford Parlett has pointed out [3], the eminence of the QR algorithm stems from the fact that it is a "genuinely new contribution to the field of numerical analysis and not just a refinement of ideas given by Newton, Gauss, Hadamard, or Schur." (See "Very Early Days of Matrix Computations" for Parlett's survey of much earlier developments in numerical analysis.)
Anyone who computes eigenvalues by typing "eig(A)" in MATLAB is invoking the QR algorithm, or more precisely the LAPACK implementation, and for matrices up to 300-by-300 a fast modern workstation will return the result within less than a second. Dense eigenvalue problems of much larger sizes arise in various applications, and for dimensions up to 10,000 or so the QR algorithm is still the method of choice for computing all the eigenvalues. Unfortunately, because the number of floating-point operations is proportional to the cube of the dimension, execution times for matrices at the upper end of this range are measured in hours. But thanks to the recent work of Braman, Byers, and Mathias, execution times for the QR algorithm on these larger matrices are set to decrease substantially.
Since the QR algorithm was first developed, it has been understood that deflation is essential to its success. Deflation is the process of splitting the problem into smaller pieces during QR iterations on the upper Hessenberg matrix. (For efficiency, a full matrix is reduced to Hessenberg form before the QR iteration is carried out.) To date, deflation has been done by zeroing tiny elements on the subdiagonal.
The key idea in this new work is to introduce carefully chosen perturbations to reveal deflations that are not yet evident on the subdiagonal. Braman, Byers, and Mathias have developed clever analysis and algorithmics to understand this idea and make it practical. Important to their success are the strategic expenditure of computational effort to look for early deflations and careful exploitation of modern computer architectures in the implementation. Their well-designed numerical experiments present convincing evidence of the improvements that aggressive early deflation can bring. In extreme cases, the cost of the QR algorithm on a 10,000-by-10,000 matrix already in Hessenberg form is reduced by two orders of magnitude.
The three prize-winners gave a joint presentation of their work at the conference. Organized by a committee co-chaired by Roy Mathias and Hugo Woerdeman (College of William & Mary), and in cooperation with the International Linear Algebra Society, the conference was the eighth in a successful series of meetings that began in Raleigh in 1982. The next SIAM Conference on Applied Linear Algebra will take place in 2006 in Germany in collaboration with Gesellschaft f�r Angewandte Mathematik und Mechanik (GAMM).
References
[1] K. Braman, R. Byers, and R. Mathias, The multishift QR algorithm. Part II: Aggressive early deflation, SIAM J. Matrix Anal. Appl., 23-4 (2002), 948-973.
[2] J. Dongarra and F. Sullivan, Introduction to the top 10 algorithms, Comput. Sci. Eng., 2-1 (2000), 22-23.
[3] B.N. Parlett, The QR algorithm, Comput. Sci. Eng., 2-1 (2000), 38-42.
Nicholas J. Higham, the Richardson Professor of Applied Mathematics at the University of Manchester, chairs the SIAM Activity Group on Linear Algebra.
