×

An a posteriori verification method for generalized real-symmetric eigenvalue problems in large-scale electronic state calculations. (English) Zbl 1439.65046

The physical background of the paper is computational material science. Specifically, the authors want to study the solution of fundamental Schrödinger-type equations for the determination of the energy of electrons and the wave functions in order to characterize the properties of the material.
The numerical solution of the treated linear partial differential equation gives a generalized eigenvalue problem (GEP) \(A x_k = {\lambda}_k B x_k\) under the orthogonality condition \({x_i}^T B {x_j} = 1, \text{ if } i = j, 0 \text{ otherwise}\), where both \(A\) and \(B\) are real symmetric \(n \times n\) matrices, with \(B\) being positive definite, and assuming \({\lambda}_1 \leq {\lambda}_2 \leq \ldots \leq {\lambda}_n\). An eigenvalue represents the energy of an electron in the material and the corresponding eigenvector the wave function.
The derivation of the GEP for the linear Schrödinger equation is presented in the appendix with references to textbooks.
The matrix dimension is approximately proportional to the number of molecules, atoms or electrons in the different materials. Thus, large-scale generalized eigenvalue problems have to be solved using massively parallel supercomputers for industrial applications. The eigenvalues of these problems are mostly densely clustered or almost degenerate with difficulties to distinguish them. The difference of sequential eigenvalues tends to be proportional to \(\frac{1}{n}\). Furthermore, in order to compute efficiently such large-scale calculations, lower-precision arithmetic, such as single-precision or even half-precision arithmetic, are used. Many well-known solvers for the generalized eigenvalue problem are parallelized and show difficulties to overcome the mentioned problems. Thus, the authors develop an a posteriori verification procedure to give an impression of the difference between the approximate solution of a GEP-solver and the exact solution.
In order to verify the algorithm, the authors consider the following four parts of the GEP: (i) the Cholesky decomposition of \(B\), (ii) the reduction to the standard eigenvalue problem (SEP), (iii) the solution of the SEP, (iv) the transformation of the eigenvectors. The steps (I), (ii), and (iv) are referred as reducer, and step (iii) is the SEP solver. The authors point to the standard parallel numerical library ScaLAPACK, developed in the 1990s, that exhibit severe bottlenecks on modern massively parallel supercomputers. The authors present results of the created verification procedure using the corresponding ScaLATACK routines as eigenvalue solver on the K computer, a Japanese flagship supercomputer.
But, they mention that there are also novel solver libraries of ELPA (developed in Europe) and EigenExa (developed in Japan) which should overcome the mentioned bottlenecks of ScaLAPACK. A schematic diagram of hybrid workflows is presented for a future version, which also includes the new SEP-solvers. The a posteriori verification method is based on Wilkinson’s bound for the standard eigenvalue problem, the verification of the error bounds of all computed eigenvalues, Gershgorin’s circle theorem, and a variant of Yamamoto’s theorem. The corresponding code is demonstrated in detail. The verifier procedure uses primarily matrix multiplications. Thus, the computational time of the verification algorithm is moderate in comparison to the solver procedure with the more time-consuming Cholesky decomposition and the tridiagonalization.
The test data stem from the ELSES matrix library, mainly for systems of organic polymers. The largest matrix problem belongs to a nano-composite carbon solid with a matrix dimension of \(n = 430.080\) using 6400 processor nodes. Tables and Figures show that the verification algorithm delivers the intervals that contain the exact eigenvalues and show the computational times and number of used processor nodes.
Future issues are announced for the use of the verification technique if lower-precision arithmetic is applied as an initial guess, in order to compute the large-scale problems efficiently, and refinements in a mixed-precision calculation are needed.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65G20 Algorithms with automatic result verification
65Z05 Applications to the sciences
68Q60 Specification and verification (program logics, model checking, etc.)
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
35J10 Schrödinger operator, Schrödinger equation
74S25 Spectral and related methods applied to problems in solid mechanics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] EigenKernel, https://github.com/eigenkernel/.
[2] Imachi, H.; Hoshi, T., Hybrid numerical solvers for massively parallel eigenvalue computations and their benchmark with electronic structure calculations, J. Inf. Process., 24, 164-172 (2016)
[3] Tanaka, K.; Imachi, H.; Fukumoto, T.; Fukaya, T.; Yamamoto, Y.; Hoshi, T., Eigenkernel - a middleware for parallel generalized eigenvalue solvers to attain high scalability and usability, Japan J. Ind. Appl. Math., 36, 719-742 (2019) · Zbl 1418.65051
[4] Yamamoto, N., A simple method for error bounds of eigenvalues of symmetric matrices, Linear Algebra Appl., 324, 1-3, 227-234 (2001) · Zbl 0981.65042
[5] Miyajima, S.; Ogita, T.; Rump, S. M.; Oishi, S., Fast verification for all eigenpairs in symmetric positive definite generalized eigenvalue problem, Reliab. Comput., 14, 24-45 (2010)
[6] Miyajima, S., Numerical enclosure for each eigenvalue in generalized eigenvalue problem, J. Comput. Appl. Math., 236, 9, 2545-2552 (2012) · Zbl 1248.65039
[7] Yamamoto, T., Error bounds for approximate solutions of systems of equations, Japan J. Appl. Math., 1, 1, 157-171 (1984) · Zbl 0571.65035
[8] J. Dongarra, Issue and solutions for extreme scale computing, in: HPC Asia 2018, Tokyo, Japan, 2018.
[9] Alvermann, A.; Basermann, A.; Bungartz, H.-J.; Carbogno, C.; Ernst, D.; Fehske, H.; Futamura, Y.; Galgon, M.; Hager, G.; Huber, S.; Huckle, T.; Ida; Imakura, A.; Kawai, M.; Köcher, S.; Kreutzer, M.; Kus, P.; Lang, B.; Lederer, H.; Manin, V.; Marek, A.; Nakajima, K.; Nemec, L.; Reuter, K.; Rippl, M.; Röhrig-Zöllner, M.; Sakurai, T.; Scheffler, M.; Scheurer, C.; Shahzad, F.; Brambila, D. S.; Thies, J.; Wellein, G., Benefits from using mixed precision computations in the ELPA-AEO and ESSEX-II eigensolver projects, Japan J. Ind. Appl. Math., 36, 699-717 (2019) · Zbl 1418.65044
[10] Hoshi, T.; Imachi, H.; Kuwata, A.; Kakuda, K.; Fujita, T.; Matsui, H., Numerical aspect of large-scale electronic state calculation for flexible device material, Japan J. Ind. Appl. Math., 36, 685-698 (2019) · Zbl 1418.65048
[11] Bell, R.; Dean, P., Atomic vibrations in vitreous silica, Disc. Faraday Soc., 50, 55-61 (1970)
[12] Fujiwara, T.; Mitsui, T.; Yamamoto, S., Scaling properties of wave functions and transport coefficients in quasicrystals, Phys. Rev. B, 53, R2910-R2913 (1996)
[13] ScaLAPACK, http://www.netlib.org/scalapack/.
[14] 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 · Zbl 0886.65022
[15] ELPA(= eigenvalue solvers for petaflop-applications), https://elpa.mpcdf.mpg.de/.
[16] Marek, A.; Blum, V.; Johanni, R.; Havu, V.; Lang, B.; Auckenthaler, T.; Heinecke, A.; Bungartz, H.; Lederer, H., The ELPA library - scalable parallel eigenvalue solutions for electronic structure theory and computational science, J. Phys. Condens. Matter, 26, 213201 (2014)
[17] EigenExa, http://www.r-ccs.riken.jp/labs/lpnctrt/en/projects/eigenexa/.
[18] Imamura, T.; Hirota, Y.; Fukaya, T.; Yamada, S.; Machida, M., Eigenexa: high performance dense eigensolver, present and future, (8th International Workshop on Parallel Matrix Algorithms and Applications (PMAA14), Lugano, Switzerland (2014))
[19] FHI-AIM(= Fritz Haber Institute ab initio molecular simulations), https://aimsclub.fhi-berlin.mpg.de/.
[20] Blum, V.; Gehrke, R.; Hanke, F.; Havu, P.; Havu, V.; Ren, X.; Reuter, K.; Scheffler, M., Ab initio molecular simulations with numeric atom-centered orbitals, Comput. Phys. Comm., 180, 2175-2196 (2009) · Zbl 1197.81005
[21] Rump, S. M., Fast and parallel interval arithmetic, BIT, 39, 3, 539-560 (1999)
[22] C-XSC - A C++ Class Library for Extended Scientific Computing, ver. 2.5.4, http://www.xsc.de/.
[23] Rump, S. M., INTLAB - interval laboratory, (Csendes, T., Developments in Reliable Computing (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 77-104 · Zbl 0949.65046
[24] Wilkinson, J. H., Rigorous error bounds for computed eigensystem, Comput. J., 4, 230-241 (1961) · Zbl 0109.34504
[25] Lee, D.; Hoshi, T.; Sogabe, T.; Miyatake, Y.; Zhang, S.-L., Solution of the \(k\)-th eigenvalue problem in large-scale electronic structure calculations, J. Comput. Phys., 371, 618-632 (2018) · Zbl 1415.65088
[26] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon Press: Clarendon Press Oxford · Zbl 0258.65037
[27] ELSES(= Extra-Large-Scale Electronic Structure calculation), http://www.elses.jp/.
[28] 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, Article 165502 pp. (2012), 1-5
[29] T. Hoshi, H. Imachi, K. Kumahata, M. Terai, K. Miyamoto, K. Minami, F. Shoji, Extremely scalable algorithm for \(10{}^8\)-atom quantum material simulation on the full system of the K computer, in: Proc. ScalA16 in SC16, pp. 33-40.
[30] ELSES Matrix Library, http://www.elses.jp/matrix/.
[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. Japan, 82, 023710/1-4 (2013)
[32] Ogita, T.; Aishima, K., Iterative refinement for symmetric eigenvalue decomposition, Japan J. Ind. Appl. Math., 35, 3, 1007-1035 (2018) · Zbl 1403.65018
[33] Ogita, T.; Aishima, K., Iterative refinement for symmetric eigenvalue decomposition II: clustered eigenvalues, Japan J. Ind. Appl. Math., 36, 2, 435-459 (2019) · Zbl 1418.65049
[34] Martin, R. M., Electronic Structure - Basic Theory and Practical Methods (2004), Cambridge University Press · Zbl 1152.74303
[35] Atkins, P.; Friedman, R., Molecular Quantum Mechanics (2005), Oxford University Press
[36] Slater, J. C., Atomic shielding constants, Phys. Rev., 36, 57-64 (1930) · JFM 56.1313.02
[37] Lesiuk, M.; Moszynski, R., Reexamination of the calculation of two-center, two-electron integrals over Slater-type orbitals. I. Coulomb and hybrid integrals, Phys. Rev. E, 90, 063318/1-13 (2014)
[38] Nath, K.; Anderson, A. B., Atom-superposition and electron-delocalization tight-binding band theory, Phys. Rev. B, 41, 5652-5660 (1990)
[39] Calzaferri, G.; Rytz, R., The band structure of diamond, J. Phys. Chem., 100, 11122-11124 (1996)
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.