Anasazi software for the numerical solution of large-scale eigenvalue problems

ABSTRACT

Anasazi is a package within the Trilinos software project that provides a framework for the iterative, numerical solution of large-scale eigenvalue problems. Anasazi is written in ANSI C++ and exploits modern software paradigms to enable the research and development of eigensolver algorithms. Furthermore, Anasazi provides implementations for some of the most recent eigensolver methods. The purpose of our article is to describe the design and development of the Anasazi framework. A performance comparison of Anasazi and the popular FORTRAN 77 code ARPACK is given.

REFERENCES

• 1: P.-A. Absil , C. G. Baker , K. A. Gallivan, Trust-Region Methods on Riemannian Manifolds, Foundations of Computational Mathematics, v.7 n.3, p.303-330, July 2007 [doi>10.1007/s10208-005-0179-9]
• 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: Arbenz, P., Hetmaniuk, U., Lehoucq, R., and Tuminaro, R. 2005. A comparison of eigensolvers for large-scale 3D modal analysis using AMG-preconditioned iterative methods. Int. J. Numer. Meth. Engng. 64, 204--236.
• 4: Baker, C. G., Hetmaniuk, U., Lehoucq, R. B., and Thornquist, H. K. Anasazi: Block eigensolver package documentation. http://trilinos.sandia.gov/trilinos/packages/anasazi/index.html.
• 5: Balay, S., Buschelman, K., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., and Zhang, H. 2001. PETSc Web page. http://www.mcs.anl.gov/petsc.
• 6: Bartlett, R., Boggs, P., Coffey, T., Heroux, M., Hoekstra, R., Howle, V., Long, K., Pawlowski, R., Phipps, E., Spotz, B., Thornquist, H., and Williams, A. Thyra: Interfaces for abstract numerical algorithms. http://trilinos.sandia.gov/trilinos/packages/thyra/.
• 7: Bartlett, R. A. 2004. Teuchos::RCP Beginner's Guide. Tech. rep. SAND2004-3268. Sandia National Laboratories, Albugusberg.
• 8: Manoj Bhardwaj , Kendall Pierson , Garth Reese , Tim Walsh , David Day , Ken Alvin , James Peery , Charbel Farhat , Michel Lesoinne, Salinas: a scalable software for high-performance structural and solid mechanics simulations, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-19, November 16, 2002, Baltimore, Maryland
• 9: 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]
• 10: Daniel, J., Gragg, W. B., Kaufman, L., and Stewart, G. W. 1976. Reorthogonalization and stable algorithms for updating the Gram--Schmidt QR factorization. Math. Computat. 30, 772--795.
• 11: Detlefs, D. 1992. Garbage collection and run-time typing as a C++ library. In Proceedings: USENIX C++ Technical Conference, USENIX, Ed. USENIX, pub-USENIX:adr, 37--56.
• 12: Embree, M. and Lehoucq, R. B. 2007. Dynamical systems and non-Hermitian iterative eigensolvers. SIAM J. Numer. Anal. 47, 1445--1473, DOI 10.1137/07070187x.
• 13: Hernández, V., Román, J., Tomás, A., and Vidal, V. 2005. A survey of software for sparse eigenvalue problems. Tech. rep. SLEPc Technical Report STR-6. Universidad Politecnica de Valencia, Valencia, Spain. http://www.grycap.upv.es/slepc.
• 14: Hernández, V., Román, J., Tomás, A., and Vidal, V. 2006. SLEPc users manual: Scalable library for eigenvalue problem computations. Tech. rep. DISC-II/24/02. Universidad Politecnica de Valencia, Valencia, Spain. http://www.grycap.upv.es/slepc.
• 15: Heroux, M., Hoekstra, R., Sexton, P., Spotz, B., Willenbring, J., and Williams, A. Epetra: Linear algebra services package. http://trilinos.sandia.gov/trilinos/packages/epetra/.
• 16: Heroux, M. A., Baker, C. G., Bartlett, R. A., Kampschoff, K., Long, K. R., Sexton, P. M., and Thornquist, H. K. Teuchos: The Trilinos tools library. http://trilinos.sandia.gov/trilinos/packages/teuchos/.
• 17: Michael A. Heroux , Roscoe A. Bartlett , Vicki E. Howle , Robert J. Hoekstra , Jonathan J. Hu , Tamara G. Kolda , Richard B. Lehoucq , Kevin R. Long , Roger P. Pawlowski , Eric T. Phipps , Andrew G. Salinger , Heidi K. Thornquist , Ray S. Tuminaro , James M. Willenbring , Alan Williams , Kendall S. Stanley, An overview of the Trilinos project, ACM Transactions on Mathematical Software (TOMS), v.31 n.3, p.397-423, September 2005 [doi>10.1145/1089014.1089021]
• 18: U. Hetmaniuk , R. Lehoucq, Basis selection in LOBPCG, Journal of Computational Physics, v.218 n.1, p.324-332, 10 October 2006 [doi>10.1016/j.jcp.2006.02.007]
• 19: Andrew V. Knyazev, Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method, SIAM Journal on Scientific Computing, v.23 n.2, p.517-541, 2001 [doi>10.1137/S1064827500366124]
• 20: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 21: Lehoucq, R. B., Sorensen, D. C., and Yang, C. 1998. ARPACK Users' Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM, Philadelphia.
• 22: Meyers, N. C. 1995. Traits: A new and useful template technique. C++ Rep. 7, 32--35.
• 23: Ronald B Morgan , David S Scott, Generalizations of Davidson's method for computing eigenvalues of sparse symmetric matrices, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.817-825, July 1986 [doi>10.1137/0907054]
• 24: David R. Musser , Alexander A. Stepanov, Algorithm-oriented generic libraries, Software—Practice & Experience, v.24 n.7, p.623-642, July 1994 [doi>10.1002/spe.4380240703]
• 25: Saad, Y. 1992. Numerical Methods for Large Eigenvalue Problems. John Wiley and Sons, New York.
• 26: Sala, M., Heroux, M. A., and Day, D. M. 2004. Trilinos tutorial. Tech. rep. SAND2004-2189. Sandia National Laboratories, Albuquerque.
• 27: Salinger, A. G., Burroughs, E. A., Pawlowski, R. P., Phipps, E. T., and Romero, L. A. 2005. Bifurcation tracking algorithms and software for large-scale applications. Int. J. Bifurcat. Chaos 15, 1015--1032.
• 28: Gerard L. G. Sleijpen , Henk A. Van der, A Jacobi--Davidson Iteration Method for Linear EigenvalueProblems, SIAM Journal on Matrix Analysis and Applications, v.17 n.2, p.401-425, April 1996 [doi>10.1137/S0895479894270427]
• 29: Sorensen, D. 2002. Numerical Methods for Large Eigenvalue Problems. Acta Numerica, vol. 11. Cambridge University Press, Cambridge, 519--584.
• 30: D. C. Sorensen, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.357-385, Jan. 1992 [doi>10.1137/0613025]
• 31: Stathopoulos, A. and McCombs, J. R. 2006. PRIMME home page. http://www.cs.wm.edu/~andreas/software/.
• 32: Andreas Stathopoulos , Kesheng Wu, A Block Orthogonalization Procedure with Constant Synchronization Requirements, SIAM Journal on Scientific Computing, v.23 n.6, p.2165-2182, 2002 [doi>10.1137/S1064827500370883]
• 33: G. W. Stewart, A Krylov--Schur Algorithm for Large Eigenproblems, SIAM Journal on Matrix Analysis and Applications, v.23 n.3, p.601-614, 2001 [doi>10.1137/S0895479800371529]
• 34: Stewart, G. W. 2001b. Matrix Systems: Eigensystems. vol. II. SIAM, Philadelphia.
• 35: van der Vorst, H. A. 2002. Computational methods for large eigenvalue problems. In P. Ciarlet and J. Lions, Eds. Handbook of Numerical Analysis, vol. VIII. North-Holland (Elsevier), Amsterdam, The Netherlands, 3--179.
• 36: David Vandevoorde , Nicolai M. Josuttis, C++ Templates, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 37: Veldhuizen, T. 1996. Using C++ trait classes for scientific computing. http://oonumerics.org/blitz/traits.html.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Design, Performance, Reliability, Theory

Keywords:
Eigenvalue problems, generic programming, large-scale scientific computing, numerical algorithms, object-oriented programming