research-article

Adaptive Projection Subspace Dimension for the Thick-Restart Lanczos Method

Authors:

Ichitaro Yamazaki,

Kesheng WuAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 37, Issue 3

Article No.: 27, Pages 1 - 18

https://doi.org/10.1145/1824801.1824805

Published: 01 September 2010 Publication History

Abstract

The Thick-Restart Lanczos (TRLan) method is an effective method for solving large-scale Hermitian eigenvalue problems. The performance of the method strongly depends on the dimension of the projection subspace used at each restart. In this article, we propose an objective function to quantify the effectiveness of the selection of subspace dimension, and then introduce an adaptive scheme to dynamically select the dimension to optimize the performance. We have developed an open-source software package a--TRLan to include this adaptive scheme in the TRLan method. When applied to calculate the electronic structure of quantum dots, a--TRLan runs up to 2.3x faster than a state-of-the-art preconditioned conjugate gradient eigensolver.

References

[1]

}}Calvetti, D., Reichel, L., and Sorensen, D. 1994. An implicitly restarted Lanczos method for large symmetric eigenvalue problems. Electro. Trans. Numer. Anal. 2, 1--21.

[2]

}}Canning, A., Wang, L. W., Williamson, A., and Zunger, A. 2000. Parallel empirical pseudopotential electronic structure calculations for million atom systems. J. Comput. Phys. 160, 1, 29--41.

Digital Library

[3]

}}Crouzeix, M., Philippe, B., and Sadkane, M. 1994. The Davidson method. SIAM J. Sci. Comput. 15, 62--76.

Digital Library

[4]

}}Demmel, J. W. 1997. Applied Numerical Linear Algebra. SIAM, Philadelphia, PA.

Digital Library

[5]

}}Lanczos, C. 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Stand. 45, 255--281.

[6]

}}Lehoucq, R., Sorensen, D., and Yang, C. 1998. ARPACK Users Guide: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM, Philadelphia, PA. Software http://www.caam.rice.edu/software/ARPACK/.

[7]

}}Li, J. and Wang, L. 2004. First principle study of core/shell structure quantum dots. Appl. Phys. Lett. 84, 18, 2648--3650.

[8]

}}Morgan, P. B. 1996. On restarting the Arnoldi method for large nonsymmetric eigenvalule problems. Math. Comput. 65, 215, 1213--1230.

Digital Library

[9]

}}Parlett, B. N. 1998. The Symmetric Eigenvalue Problem. Classics in Applied Mathematics. SIAM, Philadelphia, PA.

Digital Library

[10]

}}Payne, M. C., Teter, M. P., Allan, D. C., Arias, T. A., and Joannopoulos, J. D. 1992. Iterative minimization techniques for ab-initio total energy calculations: Molecular dynamics and conjugate gradients. Rev. Mod. Phys. 64, 1045--1097.

[11]

}}Saad, Y. 1993. Numerical Methods for Large Eigenvalue Problems. Manchester University Press, Manchester, UK.

[12]

}}Schrier, J. and Wang, L. 2006. A systematic first principles study of nanocrystal quantum-dot quantum wells. Phys. Rev. B 73, 245332--7.

[13]

}}Sorensen, D. 1992. Implicit application of polynomial filters in a k-step Arnoldi method. SIAM J. Mat. Anal. Appl. 13, 1, 357--385.

Digital Library

[14]

}}Stathopoulos, A. and McCombs, J. R. 2007. Nearly optimal preconditioned methods for Hermitian eigenproblems under limited memory. Part II: Seeking many eigenvalues. SIAM J. Sci. Comput. 29, 5, 2162--2188.

Digital Library

[15]

}}Stathopoulos, A., Saad, Y., and Wu, K. 1998. Dynamic thick restarting of the Davidson and the implicitly restarted Arnoldi methods. SIAM J. Sci. Comput. 19, 227--245.

Digital Library

[16]

}}Vömel, C., Tomov, S. Z., Marques, O. A., Canning, A., Wang, L., and Dongarra, J. J. 2008. State-of-the-Art eigensolvers for electronic structure calculation of large scale nano-systems. J. Comput. Phys. 227, 15, 7113--7124.

Digital Library

[17]

}}Wang, L., Canning, A., Marques, O., and Voemel, C. 2008. The parallel energy scan (PESCAN) code. http://icl.cs.utk.edu/doe-nano/software/pescan/escan.

[18]

}}Wang, L. and Zunger, A. 1994. Solving Schrodinger’s equation around a desired energy: Application to silicon quantum dots. J. Chem. Phys. 100, 2394--2397.

[19]

}}Wang, L. and Zunger, A. 1996. Pseudopotential theory of nanometer silicon quantum dots application to silicon quantum dots. In Semiconductor Nanocluster, P. Kamat and D. Meisel Eds., ACM, New York, NY, 161--207.

[20]

}}Wu, K. and Simon, H. 2000a. Thick-Restart Lanczos method for large symmetric eigenvalue problems. SIAM J. Mat. Anal. Appl. 22, 602--616.

Digital Library

[21]

}}Wu, K. and Simon, H. 2000b. TRLan user guide. Tech. rep. LBNL-43178, Lawrence Berkeley National Laboratory. Software http://crd.lbl.gov/~kewu/trlan.html.

[22]

}}Yamazaki, I., Wu, K., and Simon, H. 2008. a--TRLan user guide. Tech. rep. LBNL-1288E, Lawrence Berkeley National Laboratory. Software https://codeforge.lbl.gov/projects/trlan/.

Cited By

Delicado PPachón-García C(2024)Multidimensional scaling for big dataAdvances in Data Analysis and Classification10.1007/s11634-024-00591-9Online publication date: 13-Apr-2024
https://doi.org/10.1007/s11634-024-00591-9
Xu CXu WJing K(2023)Fast algorithms for singular value decomposition and the inverse of nearly low-rank matricesNational Science Review10.1093/nsr/nwad08310:6Online publication date: 25-Mar-2023
https://doi.org/10.1093/nsr/nwad083
Lin CHuang QKuo J(2020)Anharmonic coupling behind vibrational spectra of solvated ammonium: lighting up overtone states by Fermi resonance through tuning solvation environmentsPhysical Chemistry Chemical Physics10.1039/D0CP03519JOnline publication date: 2020
https://doi.org/10.1039/D0CP03519J
Show More Cited By

Recommendations

Thick-Restart Lanczos Method for Large Symmetric Eigenvalue Problems

In this paper, we propose a restarted variant of the Lanczos method for symmetric eigenvalue problems named the thick-restart Lanczos method. This new variant is able to retain an arbitrary number of Ritz vectors from the previous iterations with a ...
Thick-Restart Lanczos Method for Electronic Structure Calculations

This paper describes two recent innovations related to the restarted Lanczos method for eigenvalue problems, namely the thick-restart technique and dynamic restarting schemes. Previous restarted versions of the Lanczos method use considerably more ...
A Thick-Restart Lanczos Algorithm with Polynomial Filtering for Hermitian Eigenvalue Problems

Polynomial filtering can provide a highly effective means of computing all eigenvalues of a real symmetric (or complex Hermitian) matrix that are located in a given interval, anywhere in the spectrum. This paper describes a technique for tackling this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 37, Issue 3

September 2010

296 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1824801

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2010

Accepted: 01 February 2010

Revised: 01 October 2009

Received: 01 September 2008

Published in TOMS Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
364
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Delicado PPachón-García C(2024)Multidimensional scaling for big dataAdvances in Data Analysis and Classification10.1007/s11634-024-00591-9Online publication date: 13-Apr-2024
https://doi.org/10.1007/s11634-024-00591-9
Xu CXu WJing K(2023)Fast algorithms for singular value decomposition and the inverse of nearly low-rank matricesNational Science Review10.1093/nsr/nwad08310:6Online publication date: 25-Mar-2023
https://doi.org/10.1093/nsr/nwad083
Lin CHuang QKuo J(2020)Anharmonic coupling behind vibrational spectra of solvated ammonium: lighting up overtone states by Fermi resonance through tuning solvation environmentsPhysical Chemistry Chemical Physics10.1039/D0CP03519JOnline publication date: 2020
https://doi.org/10.1039/D0CP03519J
Ju SHsu H(2019)An Out-of-Core Eigen-Solver with OpenMP Parallel Scheme for Large Spare Damped SystemInternational Journal of Computational Methods10.1142/S0219876219500385(1950038)Online publication date: 21-Apr-2019
https://doi.org/10.1142/S0219876219500385
Li RXi YErlandson LSaad Y(2019)The Eigenvalues Slicing Library (EVSL): Algorithms, Implementation, and SoftwareSIAM Journal on Scientific Computing10.1137/18M117093541:4(C393-C415)Online publication date: 13-Aug-2019
https://doi.org/10.1137/18M1170935
Spencer JBlunt NChoi SEtrych JFilip MFoulkes WFranklin RHandley WMalone FNeufeld VDi Remigio RRogers TScott CShepherd JVigor WWeston JXu RThom A(2019)The HANDE-QMC Project: Open-Source Stochastic Quantum Chemistry from the Ground State UpJournal of Chemical Theory and Computation10.1021/acs.jctc.8b0121715:3(1728-1742)Online publication date: 25-Jan-2019
https://doi.org/10.1021/acs.jctc.8b01217
Yin JXu LWang HXie PHuang SLiu HYang ZLi B(2019)Accurate and fast three-dimensional free vibration analysis of large complex structures using the finite element methodComputers & Structures10.1016/j.compstruc.2019.06.002221(142-156)Online publication date: Sep-2019
https://doi.org/10.1016/j.compstruc.2019.06.002
Aishima K(2019)Global convergence of the restarted Lanczos and Jacobi---Davidson methods for symmetric eigenvalue problemsNumerische Mathematik10.1007/s00211-015-0699-4131:3(405-423)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1007/s00211-015-0699-4
Huang QNishigori TKatada MFujii AKuo J(2018) Fermi resonance in solvated H 3 O + : a counter-intuitive trend confirmed via a joint experimental and theoretical investigation Physical Chemistry Chemical Physics10.1039/C8CP02151A20:20(13836-13844)Online publication date: 2018
https://doi.org/10.1039/C8CP02151A
Jiang WWu G(2018)A thick-restarted block Arnoldi algorithm with modified Ritz vectors for large eigenproblemsComputers & Mathematics with Applications10.1016/j.camwa.2010.05.03460:3(873-889)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/j.camwa.2010.05.034
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents