Abstract
Iterative methods such as Lanczos and Jacobi-Davidson are typically used to compute a small number of eigenvalues and eigenvectors of a sparse matrix. However, these methods are not effective in certain large-scale applications, for example, “global tight binding molecular dynamics.” Such applications require all the eigenvectors of a large sparse matrix; the eigenvectors can be computed a few at a time and discarded after a simple update step in the modeling process. We show that by using sparse matrix methods, a direct-iterative hybrid scheme can significantly reduce memory requirements while requiring less computational time than a banded direct scheme. Our method also allows a more scalable parallel formulation for eigenvector computation through spectrum slicing. We discuss our method and provide empirical results for a wide variety of sparse matrix test problems.
This work was supported in part by the National Science Foundation through grants ACI-0102537, EIA-0221916, and DMR-0205232.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. M. Kcnncy, AND D. Sorensen, LAPACK User’s Guide, third edition. SIAM, Philadelphia, 1999.
Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. Van der Vorst, editors. Templates for the Solution of Algebraic Eigenvalue Problems: A practical Guide SIAM, Philadelphia, 2000.
C. H. Bischof, B. Lang and X. Sun, A framework for symmetric band reduction. ACM Transactions on Mathematical Software Vol. 26 no. 4 pp. 581–601, 2000.
L. S. Blackford, J. Choi, A. Cleary, E. D’Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley, ScaLAPACK User’s Guide SIAM, Philadelphia, 1997.
J. L. Barlow, Personal Communication
J. W. Demmel, Applied Numerical Linear Algebra SIAM, Philadelphia, 1997.
I. S. Dhillon, A New O (N2) Algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem. PhD. Thesis, University of California, Berkeley, 1997.
I. S. Duff, A. M. Erisman, and J. K. Raid, Direct Methods for sparse Matrices, Claredon Press, Oxford, 1986.
J. A. George, and J. W.-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall Inc., Englewood Cliffs, NJ, 1981.
G. Golub and C. F. Van Loan, Matrix Computations, third edition, The Johns Hopkins University Press, Baltimore, MD, 1996.
R. G. Grimes, J. G. Lewis, and H. D. Simon, A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems. SIAM J. Matrix Anal. Appl., Vol. 15, No. 1, pp. 228–272, 1994.
M. Gu and S. C. Eisenstat, A Divide-and-Conquer algorithm for the symmetric tridiagonal eigenproblem SIAM J. Matrix Anal. Appl. Vol. 16, No. 1 pp. 172–191 1995.
B. Hendrickson and E. Rothberg, Improving the runtime and quality of nested dissection ordering, tech. rep., Sandia National Laboratories, Albuquerque, NM 87185, 1996.
L. Kaufman, Banded Eigenvalue Solvers on Vector Machines ACM Trans. Math. Software, Vol. 10, No. 1, pp. 73–86, 1984.
G. Karypis and V. Kumar, METIS: Unstructured graph partitioning and sparse matrix ordering system, tech. rep., Department of Computer Science, University of Minnesota, Minneapolis, MN, 1995.
R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods
M. Menon and K.R. Subbaswamy, A Transferable Nonorthogonal Tight-Binding Scheme for Silicon, Phys. Rev. B50, 11577 (1994).
M. Menon, R. Richter, P. Raghavan and K. Teranishi, Large Scale Quantum Mechanical Simulations of Carbon Wires, Superlattices and Microstructures, Vol. 27, No. 5/6, pp. 577–581, 2000.
Matrix Market http://math.nist.gov/MatrixMarket/
E. G.-Y. Ng and P. Raghavan, Performance of greedy ordering heuristics for sparse Cholesky factorization, SIAM J. Matrix Anal. Appl., Vol. 20, No. 4, pp. 902–914, 1999.
B. Parlett., The Symmetric Eigenvalue Problem, Prentice Hall, Engle-wood Cliffs, NJ, (1980).
B. N. Parlett and I. S. Dhillon, Relatively Robust Representations for Symmetric Tridiagonals, Linear Algebra and its Applications, 309, pp. 121–151, 2000.
P. Raghavan, DSCPACK: Domain-Separator Codes for the parallel solution of sparse linear systems Technical Report CSE-02-004, Department of Computer Science and Engineering, The Pennsylvania State University, 2002.
S. L. G. Slejipen and H. A. van der Vorst, A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM J. Matrix Anal. Appl., Vol. 17, pp. 401–425, 1996.
C. Yang, Accelerating the Arnoldi Iteration: Theory and Practice Ph.D Thesis, Department of Computational and Applied Mathematics, Rice University, Houston, Jan. 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Teranishi, K., Raghavan, P., Yang, C. (2003). Time-Memory Trade-Offs Using Sparse Matrix Methods for Large-Scale Eigenvalue Problems. In: Kumar, V., Gavrilova, M.L., Tan, C.J.K., L’Ecuyer, P. (eds) Computational Science and Its Applications — ICCSA 2003. ICCSA 2003. Lecture Notes in Computer Science, vol 2667. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44839-X_88
Download citation
DOI: https://doi.org/10.1007/3-540-44839-X_88
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40155-1
Online ISBN: 978-3-540-44839-6
eBook Packages: Springer Book Archive