Algorithm 880: A testing infrastructure for symmetric tridiagonal eigensolvers

ABSTRACT

LAPACK is often mentioned as a positive example of a software library that encapsulates complex, robust, and widely used numerical algorithms for a wide range of applications. At installation time, the user has the option of running a (limited) number of test cases to verify the integrity of the installation process. On the algorithm developer's side, however, more exhaustive tests are usually performed to study algorithm behavior on a variety of problem settings and also computer architectures. In this process, difficult test cases need to be found that reflect particular challenges of an application or push algorithms to extreme behavior. These tests are then assembled into a comprehensive collection, therefore making it possible for any new or competing algorithm to be stressed in a similar way. This article describes an infrastructure for exhaustively testing the symmetric tridiagonal eigensolvers implemented in LAPACK. It consists of two parts: a selection of carefully chosen test matrices with particular idiosyncrasies and a portable testing framework that allows for easy testing and data processing. The tester facilitates experiments with algorithmic choices, parameter and threshold studies, and performance comparisons on different architectures.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: 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
• 3: ANSI/IEEE 1985. IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 ed. ANSI/IEEE, New York, NY.
• 4: Apra, E. et al. 2005. NWChem, a computational chemistry package for parallel computers, version 4.7. Tech. rep., Pacific Northwest National Laboratory, Richland, WA.
• 5: A. Bai , D. Day , J. D %A , J. Dongarra, A Test Matrix Collection for Non-Hermitian Eigenvalue Problems, University of Tennessee, Knoxville, TN, 1997
• 6: Zhaojun Bai , James Demmel , Jack Dongarra , Axel Ruhe , Henk van der Vorst, Templates for the solution of algebraic eigenvalue problems: a practical guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 7: S. Browne , J. Dongarra , N. Garner , G. Ho , P. Mucci, A Portable Programming Interface for Performance Evaluation on Modern Processors, International Journal of High Performance Computing Applications, v.14 n.3, p.189-204, August 2000 [doi>10.1177/109434200001400303]
• 8: Bunch, J., Nielsen, P., and Sorensen, D. 1978. Rank-one modification of the symmetric eigenproblem. Numer. Math. 31, 31--48.
• 9: Clement, P. A. 1959. A class of triple-diagonal matrices for test purposes. SIAM Rev. 1, 50--52.
• 10: Cuppen, J. J. M. 1981. A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. 36, 177--195.
• 11: Davis, T. A. 1994--2007. University of Florida Sparse Matrix Collection. NA Digest 92, 42; NA Digest 96, 28; NA Digest 97, 23.
• 12: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 13: Demmel, J. W., Marques, O. A., Parlett, B. N., and Vömel, C. 2006. Lapack working note 183: Performance and accuracy of LAPACK's symmetric tridiagonal eigensolvers. Tech. rep., University of California, Berkeley.
• 14: Demmel, J. W. and McKenney, A. 1989. A test matrix generation suite. Tech. rep. Computer Science Department, Courant Institute, New York, NY.
• 15: Inderjit Singh Dhillon, A new O (N(2)) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, University of California at Berkeley, Berkeley, CA, 1998
• 16: Dhillon, I. S. 1998. Current inverse iteration software can fail. BIT 38:4, 685--704.
• 17: Dhillon, I. S., Fann, G., and Parlett, B. N. 1997. Application of a new algorithm for the symmetric eigenproblem to computational quantum chemistry. In Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Philadelphia, PA.
• 18: Dhillon, I. S. and Parlett, B. N. 2004a. 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: Inderjit S. Dhillon , Beresford N. Parlett , Christof Vömel, The design and implementation of the MRRR algorithm, ACM Transactions on Mathematical Software (TOMS), v.32 n.4, p.533-560, December 2006 [doi>10.1145/1186785.1186788]
• 22: Dongarra, J. J., Moore, S., Mucci, P., Seymour, K., Terpstra, D., and You, H. 2007. Performance Application Programming Interface (PAPI). http://icl.cs.utk.edu/papi/.
• 23: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 24: Duff, I. S., Grimes, R. G., and Lewis, J. G. 1992. Users' guide for the Harwell-Boeing sparse matrix collection (Release I). Tech. rep. RAL-TR-92-086, Atlas Centre, Rutherford Appleton Laboratory.
• 25: Duff, I. S., Grimes, R. G., and Lewis, J. G. 1997. The Rutherford-Boeing sparse matrix collection. Tech. rep. RAL-TR-97-031, Atlas Centre, Rutherford Appleton Laboratory: Tech. rep. ISSTECH-97-017 from Boeing Information & Support Services; Report TR/PA/97/36 from CERFACS, Toulouse.
• 26: Walter Gautschi, Algorithm 726: ORTHPOL–a package of routines for generating orthogonal polynomials and Gauss-type quadrature rules, ACM Transactions on Mathematical Software (TOMS), v.20 n.1, p.21-62, March 1994 [doi>10.1145/174603.174605]
• 27: Gautschi, W. 2002. The interplay between classical analysis and (numerical) linear algebra—a tribute to Gene H. Golub. Electr. Trans. Num. Analy. 13, 119--147.
• 28: Gautschi, W. 2004. Orthogonal Polynomials: Computation and Approximation. Oxford University Press, Oxford, UK.
• 29: Walter Gautschi, Orthogonal polynomials (in Matlab), Journal of Computational and Applied Mathematics, v.178 n.1-2, p.215-234, 1 June 2005 [doi>10.1016/j.cam.2004.03.029]
• 30: Godunov, S. K., Antonov, A. G., Kiriljuk, O. P., and Kostin, V. I. 1993. Guaranteed Accuracy in Numerical Linear Algebra. Kluwer Academic, Dordrecht, The Netherlands.
• 31: Golub, G. H. 1973. Some modified matrix eigenvalue problems. SIAM Rev. 15, 318--334.
• 32: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 33: Gragg, W. B. and Harrod, W. J. 1984. The numerically stable reconstruction of Jacobi spectral data. Numer. Math. 44, 317--336.
• 34: Gregory, R. and Karney, D. 1969. A Collection of Matrices for Testing Computational Algorithms. Wiley, New York, NY.
• 35: Ming Gu , Stanley C. Eisenstat, A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1266-1276, Oct. 1994 [doi>10.1137/S089547989223924X]
• 36: 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]
• 37: Per Christian Hansen, Test matrices for regularization methods, SIAM Journal on Scientific Computing, v.16 n.2, p.506-512, March 1995 [doi>10.1137/0916032]
• 38: Nicholas J. Higham, Algorithm 694: a collection of test matrices in MATLAB, ACM Transactions on Mathematical Software (TOMS), v.17 n.3, p.289-305, Sept. 1991 [doi>10.1145/114697.116805]
• 39: IEEE 754 2002. IEEE Standard for Binary Floating Point Arithmetic Revision. grouper.ieee.org/groups/754.
• 40: 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]
• 41: Kendall, R. A., Aprà, E., Bemholdt, D. E., et al. 2000. High Performance Computational Chemistry: An overview of NWChem a distributed parallel application. Comput. Phys. Comm. 128, 260--283.
• 42: Lee, C. R. and Stewart, G. W. 2006. Eigentest: A test matrix generator for large-scale eigenproblems. UMIACS TR-2006-07, CMSC TR-4783, University of Maryland, College Park, MD.
• 43: Osni A. Marques , E. Jason Riedy , Christof Vo¨mel, Benefits of IEEE-754 Features in Modern Symmetric Tridiagonal Eigensolvers, SIAM Journal on Scientific Computing, v.28 n.5, p.1613-1633, September 2006 [doi>10.1137/050641624]
• 44: Anna M. Matsekh, The Godunov-inverse iteration: a fast and accurate solution to the symmetric tridiagonal eigenvalue problem, Applied Numerical Mathematics, v.54 n.2, p.208-221, July 2005 [doi>10.1016/j.apnum.2004.09.024]
• 45: Michael L. Overton, Numerical computing with IEEE floating point arithmetic, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 46: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 47: 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.
• 48: Parlett, B. N. and Dhillon, I. S. 2000. Relatively robust representations of symmetric tridiagonals. Linear Algebra Appl. 309, 1--3, 121--151.
• 49: Parlett, B. N. and Vömel, C. 2007. The spectrum of a glued matrix. Tech. rep. University of California, Berkeley. Submitted.
• 50: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
Eigenvalues, LAPACK, accuracy, design, eigenvectors, implementation, numerical software, performance, symmetric matrix, test matrices, testing