The design and implementation of the MRRR algorithm

ABSTRACT

In the 1990's, Dhillon and Parlett devised the algorithm of multiple relatively robust representations (MRRR) for computing numerically orthogonal eigenvectors of a symmetric tridiagonal matrix T with O(n²) cost. While previous publications related to MRRR focused on theoretical aspects of the algorithm, a documentation of software issues has been missing. In this article, we discuss the design and implementation of the new MRRR version STEGR that will be included in the next LAPACK release. By giving an algorithmic description of MRRR and identifying governing parameters, we hope to make STEGR more easily accessible and suitable for future performance tuning. Furthermore, this should help users understand design choices and tradeoffs when using the code.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: ANSI/IEEE 1985. IEEE Standard for Binary Floating Point Arithmetic. Std 754-1985 ed. ANSI/IEEE, New York.
• 3: Antonelli, D. and Vömel, C. 2005. LAPACK working note 168: PDSYEVR. ScaLAPACK's parallel MRRR algorithm for the symmetric eigenvalue problem. Tech. Rep. UCBCSD-05-1399, University of California, Berkeley.
• 4: Jesse Barlow , James Demmel, Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM Journal on Numerical Analysis, v.27 n.3, p.762-791, June 1990 [doi>10.1137/0727045]
• 5: Paolo Bientinesi , Inderjit S. Dhillon , Robert A. van de Geijn, A Parallel Eigensolver for Dense Symmetric Matrices Based on Multiple Relatively Robust Representations, SIAM Journal on Scientific Computing, v.27 n.1, p.43-66, 2005 [doi>10.1137/030601107]
• 6: An updated set of basic linear algebra subprograms (BLAS), ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.135-151, June 2002 [doi>10.1145/567806.567807]
• 7: Bunch, J., Nielsen, P., and Sorensen, D. 1978. Rank-One modification of the symmetric eigenproblem. Numer. Math. 31, 31--48.
• 8: Choi, J., Demmel, J., Dhillon, I., Dongarra, J., Ostrouchov, S., Petitet, A., Stanley, K., Walker, D., and Whaley, R. C. 1996. ScaLAPACK: A portable linear algebra library for distributed memory computers---Design issues and performance. Comput. Phys. Commun. 97, 1--15.
• 9: J. Choi , J. Dongarra , S. Ostrouchov , A. Petitet , D. Walker, A Proposal for a Set of Parallel Basic Linear Algebra Subprograms, University of Tennessee, Knoxville, TN, 1995
• 10: Cuppen, J. J. M. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. 36, 177--195.
• 11: Davis, C. and Kahan, W. 1970. The rotation of eigenvectors by a perturbation. III. SIAM J. Numer. Anal. 7, 1, 1--47.
• 12: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 13: Demmel, J. W., Dhillon, I. S., Marques, O. A., Parlett, B. N., and Vömel, C. 2005. Performance and accuracy of the symmetric eigensolvers in LAPACK. University of California, Berkeley. In preparation.
• 14: Demmel, J. W., Dhillon, I. S., and Ren, H. 1995. On the correctness of some bisection-like parallel eigenvalue algorithms in floating point arithmetic. Electron. Trans. Num. Anal. 3, 116--140.
• 15: James Demmel , W. Kahan, Accurate singular values of bidiagonal matrices, SIAM Journal on Scientific and Statistical Computing, v.11 n.5, p.873-912, September 1990 [doi>10.1137/0911052]
• 16: J. W. Demmel , Xiaoye Li, Faster Numerical Algorithms Via Exception Handling, IEEE Transactions on Computers, v.43 n.8, p.983-992, August 1994 [doi>10.1109/12.295860]
• 17: Inderjit Singh Dhillon, A new O (N(2)) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, University of California at Berkeley, Berkeley, CA, 1998
• 18: Dhillon, I. S. and Parlett, B. N. 2004b. Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. Linear Algebra Appl. 387, 1--28.
• 19: Inderjit S. Dhillon , Beresford N. Parlett, Orthogonal Eigenvectors and Relative Gaps, SIAM Journal on Matrix Analysis and Applications, v.25 n.3, p.858-899, 2003 [doi>10.1137/S0895479800370111]
• 20: Inderjit S. Dhillon , Beresford N. Parlett , Christof Vömel, Glued Matrices and the MRRR Algorithm, SIAM Journal on Scientific Computing, v.27 n.2, p.496-510, 2005 [doi>10.1137/040620746]
• 21: Jack J. Dongarra , R. C Whaley, LAPACK Working Note 94: A User''s Guide to the BLACS v1.0, University of Tennessee, Knoxville, TN, 1995
• 22: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 23: Jack J. Dongarra , Lain S. Duff , Danny C. Sorensen , Henk A. Vander Vorst, Numerical Linear Algebra for High Performance Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998
• 24: Jack J. Dongarra , Robert A. Geijn, LAPACK Working Note 37: Two Dimensional Basic Linear Algebra Communication Subprograms, University of Tennessee, Knoxville, TN, 1991
• 25: Fernando, K. V. and Parlett, B. N. 1994. Accurate singular values and differential qd algorithms. Numeri. Math. 67, 191--229.
• 26: Ming Gu , Stanley C. Eisenstat, A Divide-and-Conquer Algorithm for the Symmetric TridiagonalEigenproblem, SIAM Journal on Matrix Analysis and Applications, v.16 n.1, p.172-191, Jan. 1995 [doi>10.1137/S0895479892241287]
• 27: Ilse C. F. Ipsen, Computing an Eigenvector with Inverse Iteration, SIAM Review, v.39 n.2, p.254-291, June 1997 [doi>10.1137/S0036144596300773]
• 28: Marques, O. A., Parlett, B. N., and Vömel, C. 2005. LAPACK working note 167: Subset computations with the MRRR algorithm. Tech. Rep. UCBCSD-05-1392, University of California, Berkeley, Calfornia, USA.
• 29: Marques, O. A., Riedy, E. J., and Vömel, C. 2005. Lapack working note 172: Benefits of IEEE-754 features in modern symmetric tridiagonal eigensolvers. Tech. Rep. UCBCSD-05-1414, University of California, Berkeley, California, USA.
• 30: Michael L. Overton, Numerical computing with IEEE floating point arithmetic, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 31: Parlett, B. N. 1995. Acta Numerica. Cambridge University Press, Cambridge, UK. 459--491.
• 32: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 33: Beresford N. Parlett, For tridiagonals T replace T with LDLt, Journal of Computational and Applied Mathematics, v.123 n.1-2, p.117-130, Nov. 2000 [doi>10.1016/S0377-0427(00)00394-0]
• 34: Parlett, B. N. 2003. Perturbation of eigenpairs of factored symmetric tridiagonal matrices. Found. Comput. Math. 3, 2, 207--223.
• 35: Beresford N. Parlett, A Bidiagonal Matrix Determines Its Hyperbolic SVD to Varied Relative Accuracy, SIAM Journal on Matrix Analysis and Applications, v.26 n.4, p.1022-1057, 2005 [doi>10.1137/S0895479803424980]
• 36: Parlett, B. N. and Dhillon, I. S. 1997. Fernando's solution to Wilkinson's problem: An application of double factorization. Linear Algebra Appl. 267, 247--279.
• 37: Parlett, B. N. and Dhillon, I. S. 2000a. Relatively robust representations of symmetric tridiagonals. Linear Algebra Appl. 309, 1--3, 121--151.
• 38: Parlett, B. N. and Marques, O. 2000. An implementation of the dqds algorithm (positive case). Linear Algebra and Appl. 309, 217--259.
• 39: Rutishauser, H. 1954. Der quotienten-differenzen-algorithmus. Z. Angew. Math. Phys. 5, 233--251.
• 40: Rutishauser, H. 1976. Vorlesungen über Numerische Mathematik. Birkhäuser, Basel.
• 41: Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
• 42: Robert A. van de Geijn , Philip Alpatou , Greg Baker , Carter Edwards , John Gunnels , Greg Morrow , James Overfelt, Using PLAPACK: parallel linear algebra package, MIT Press, Cambridge, MA, 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

Keywords:
LAPACK, Multiple relatively robust representations, design, eigenvalues, eigenvectors, implementation, numerical software, symmetric matrix