Lee, Dongjin; Hoshi, Takeo; Sogabe, Tomohiro; Miyatake, Yuto; Zhang, Shao-Liang Solution of the \(k\)-th eigenvalue problem in large-scale electronic structure calculations. (English) Zbl 1415.65088 J. Comput. Phys. 371, 618-632 (2018). Summary: We consider computing the \(k\)-th eigenvalue and its corresponding eigenvector of a generalized Hermitian eigenvalue problem of \(n \times n\) large sparse matrices. In electronic structure calculations, several properties of materials, such as those of optoelectronic device materials, are governed by the eigenpair with a material-specific index \(k\). We present a three-stage algorithm for computing the \(k\)-th eigenpair with validation of its index. In the first stage of the algorithm, we propose an efficient way of finding an interval containing the \(k\)-th eigenvalue \((1 \ll k \ll n)\) with a non-standard application of the Lanczos method. In the second stage, spectral bisection for large-scale problems is realized using a sparse direct linear solver to narrow down the interval of the \(k\)-th eigenvalue. In the third stage, we switch to a modified shift-and-invert Lanczos method to reduce bisection iterations and compute the \(k\)-th eigenpair with validation. Numerical results with problem sizes up to 1.5 million are reported, and the results demonstrate the accuracy and efficiency of the three-stage algorithm. Cited in 4 Documents MSC: 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F50 Computational methods for sparse matrices 65Z05 Applications to the sciences Keywords:generalized eigenvalue problem; electronic structure calculations; spectral bisection; Lanczos method; sparse direct linear solver Software:MUMPS; FEAST; ScaLAPACK; JDQZ; LAPACK; k-ep; JDQR; ELPA; lobpcg.m PDFBibTeX XMLCite \textit{D. Lee} et al., J. Comput. Phys. 371, 618--632 (2018; Zbl 1415.65088) Full Text: DOI arXiv References: [1] Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Natl. Bur. Stand., 45, 4, 255-282 (1950) [2] Knyazev, A. V., Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23, 2, 517-541 (2001) · Zbl 0992.65028 [3] Ericsson, T.; Ruhe, A., The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comput., 35, 152, 1251-1268 (1980) · Zbl 0468.65021 [4] Sleijpen, G. L.G.; van der Vorst, H. A., A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17, 2, 401-425 (1996) · Zbl 0860.65023 [5] Sakurai, T.; Sugiura, H., A projection method for generalized eigenvalue problems using numerical integration, J. Comput. Appl. Math., 159, 1, 119-128 (2003) · Zbl 1037.65040 [6] Polizzi, E., Density-matrix-based algorithm for solving eigenvalue problems, Phys. Rev. B, 79, Article 115112 pp. (2009) [7] Li, R.; Xi, Y.; Vecharynski, E.; Yang, C.; Saad, Y., A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems, SIAM J. Sci. Comput., 38, 4, A2512-A2534 (2016) · Zbl 1348.65071 [8] Hoshi, T.; Yamamoto, S.; Fujiwara, T.; Sogabe, T.; Zhang, S.-L., An order-\(N\) electronic structure theory with generalized eigenvalue equations and its application to a ten-million-atom system, J. Phys. Condens. Matter, 24, 16, Article 165502 pp. (2012) [9] Marek, A.; Blum, V.; Johanni, R.; Havu, V.; Lang, B.; Auckenthaler, T.; Heinecke, A.; Bungartz, H.-J.; Lederer, H., The ELPA library: scalable parallel eigenvalue solutions for electronic structure theory and computational science, J. Phys. Condens. Matter, 26, 21, Article 213201 pp. (2014) [10] Blackford, L. S.; Choi, J.; Cleary, A.; D’Azevedo, E.; Demmel, J.; Dhillon, I.; Dongarra, J.; Hammarling, S.; Henry, G.; Petitet, A.; Stanley, K.; Walker, D.; Whaley, R. C., ScaLAPACK Users’ Guide (1997), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 0886.65022 [11] Imamura, T.; Yamada, S.; Machida, M., Development of a high-performance eigensolver on a peta-scale next-generation supercomputer system, Prog. Nucl. Sci. Technol., 2, 643-650 (2011) [12] Imachi, H.; Hoshi, T., Hybrid numerical solvers for massively parallel eigenvalue computations and their benchmark with electronic structure calculations, J. Inf. Process., 24, 1, 164-172 (2016) [13] Hoshi, T.; Imachi, H.; Kumahata, K.; Terai, M.; Miyamoto, K.; Minami, K.; Shoji, F., Extremely scalable algorithm for \(10^8\)-atom quantum material simulation on the full system of the K computer, (Proceedings of the 7th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (2016)), 33-40 [14] Bowler, D. R.; Miyazaki, T., \(O(N)\) methods in electronic structure calculations, Rep. Prog. Phys., 75, 3, Article 036503 pp. (2012) [15] Lee, D.; Miyata, T.; Sogabe, T.; Hoshi, T.; Zhang, S.-L., An interior eigenvalue problem from electronic structure calculations, Jpn. J. Ind. Appl. Math., 30, 3, 625-633 (2013) · Zbl 1291.65126 [16] Givens, W., Numerical Computation of the Characteristic Values of a Real Symmetric Matrix (1954), Oak Ridge National Laboratory, Tech. Rep. ORNL-1574 · Zbl 0055.35005 [17] Bunch, J. R.; Kaufman, L., Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comput., 31, 137, 163-179 (1977) · Zbl 0355.65023 [18] Peters, G.; Wilkinson, J. H., Eigenvalues of \(A x = \lambda B x\) with band symmetric \(A\) and \(B\), Comput. J., 12, 4, 398-404 (1969) · Zbl 0185.40204 [19] Parlett, B. N., The Symmetric Eigenvalue Problem (1980), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia: Prentice-Hall: Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia: Prentice-Hall Englewood Cliffs, First published by · Zbl 0431.65017 [20] Meurant, G., The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations (2006), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 1110.65029 [21] Bai, Z.; Demmel, J.; Dongarra, J.; Ruhe, A.; van der Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (2000), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 0965.65058 [22] Stewart, G. W., Gershgorin theory for the generalized eigenvalue problem \(A x = \lambda B x\), Math. Comput., 29, 130, 600-606 (1975) · Zbl 0302.65028 [23] Kostić, V.; Cvetković, L. J.; Varga, R. S., Geršgorin-type localizations of generalized eigenvalues, Numer. Linear Algebra Appl., 16, 11-12, 883-898 (2009) · Zbl 1224.65094 [24] Nakatsukasa, Y., Gerschgorin’s theorem for generalized eigenvalue problems in the Euclidean metric, Math. Comput., 80, 276, 2127-2142 (2011) · Zbl 1230.15012 [25] Lintner, M., The eigenvalue problem for the 2D Laplacian in \(H\)-matrix arithmetic and application to the heat and wave equation, Computing, 72, 3-4, 293-323 (2004) · Zbl 1055.65049 [26] Benner, P.; Mach, T., Computing all or some eigenvalues of symmetric \(H_\ell \)-matrices, SIAM J. Sci. Comput., 34, 1, A485-A496 (2012) · Zbl 1387.65034 [27] Xi, Y.; Xia, J.; Chan, R., A fast randomized eigensolver with structured LDL factorization update, SIAM J. Matrix Anal. Appl., 35, 3, 974-996 (2014) · Zbl 1305.65125 [28] Grimes, R. G.; Lewis, J. G.; Simon, H. D., A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. Matrix Anal. Appl., 15, 1, 228-272 (1994) · Zbl 0803.65044 [29] Hoshi, T.; Fujiwara, T., Domain boundary formation in helical multishell gold nanowires, J. Phys. Condens. Matter, 21, 27, Article 272201 pp. (2009) [30] Imachi, H.; Yokoyama, S.; Kaji, T.; Abe, Y.; Tada, T.; Hoshi, T., One-hundred-nm-scale electronic structure and transport calculations of organic polymers on the K computer, AIP Conf. Proc., 1790, Article 020010 pp. (2016) [31] Hoshi, T.; Akiyama, Y.; Tanaka, T.; Ohno, T., Ten-million-atom electronic structure calculations on the K computer with a massively parallel order-\(N\) theory, J. Phys. Soc. Jpn., 82, 2, Article 023710 pp. (2013) [32] Cerdá, J.; Soria, F., Accurate and transferable extended Hückel-type tight-binding parameters, Phys. Rev. B, 61, 7965-7971 (2000) [33] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, L.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Sorensen, D., LAPACK Users’ Guide (1999), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 0934.65030 [34] Cuppen, J. J.M., A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math., 36, 2, 177-195 (1981) · Zbl 0431.65022 [35] Gu, M.; Eisenstat, S. C., A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J. Matrix Anal. Appl., 16, 1, 172-191 (1995) · Zbl 0815.65050 [36] Tisseur, F.; Dongarra, J., A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures, SIAM J. Sci. Comput., 20, 6, 2223-2236 (1999) · Zbl 0939.65058 [37] Amestoy, P. R.; Duff, I. S.; L’Excellent, J.-Y.; Koster, J., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23, 1, 15-41 (2001) · Zbl 0992.65018 [38] Amestoy, P. R.; Guermouche, A.; L’Excellent, J.-Y.; Pralet, S., Hybrid scheduling for the parallel solution of linear systems, Parallel Comput., 32, 2, 136-156 (2006) [39] Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20, 1, 359-392 (1998) · Zbl 0915.68129 [40] Brent, R. P., An algorithm with guaranteed convergence for finding a zero of a function, Comput. J., 14, 4, 422-425 (1971) · Zbl 0231.65046 [41] Hohenberg, P.; Kohn, W., Inhomogeneous electron gas, Phys. Rev., 136, 3B, B864-B871 (1964) [42] Kohn, W.; Sham, L. J., Self-consistent equations including exchange and correlation effects, Phys. Rev., 140, 4A, A1133-A1138 (1965) [43] Kohn, W., Nobel lecture: electronic structure of matter-wave functions and density functionals, Rev. Mod. Phys., 71, 1253-1266 (1999) [44] Martin, R. M., Electronic Structure: Basic Theory and Practical Methods (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1152.74303 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.