Efficient reduction of banded Hermitian positive definite generalized eigenvalue problems to banded standard eigenvalue problems. (English) Zbl 1455.65055

The author proposes an algorithm for the reduction of the banded positive definite generalized eigenvalue problem \(Ax = Bx\lambda\) to an equivalent standard eigenvalue problem, such that the banded structure is preserved. The given method combines ideas of an algorithm proposed by C. R. Crawford in [Commun. ACM 16, 41–44 (1973; Zbl 0247.65025)] and LAPACK’s reduction routines _{SY,HE}GST and retains their respective advantages. In addition, it includes two algorithmic parameters (block size, \(n_b\), and width of blocked orthogonal transformations, \(w\)) that can be adjusted to optimize performance. A heuristic for automatically determining suitable values for these parameters was also presented. Numerical experiments confirm the efficiency of the new method.


65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65-04 Software, source code, etc. for problems pertaining to numerical analysis


Zbl 0247.65025
Full Text: DOI


[1] E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov, and D. Sorensen, {\it LAPACK Users’ Guide}, 2nd ed., SIAM, Philadelphia, 1995. · Zbl 0843.65018
[2] K.-J. Bathe and E. L. Wilson, {\it Solution methods for eigenvalue problems in structural mechanics}, Internat. J. Numer. Methods Engng., 6 (1973), pp. 213-226. · Zbl 0252.73062
[3] C. Bischof and C. Van Loan, {\it The WY representation for products of Householder matrices}, SIAM J. Sci. Stat. Comput., 8 (1987), pp. s2-s13. · Zbl 0628.65033
[4] C. H. Bischof, B. Lang, and X. Sun, {\it Algorithm 807: The SBR Toolbox–Software for successive band reduction}, ACM Trans. Math. Software, 26 (2000), pp. 602-616. · Zbl 1365.65104
[5] C. H. Bischof, B. Lang, and X. Sun, {\it A framework for symmetric band reduction}, ACM Trans. Math. Software, 26 (2000), pp. 581-601. · Zbl 1365.65103
[6] C. R. Crawford, {\it Reduction of a band-symmetric generalized eigenvalue problem}, Comm. ACM, 16 (1973), pp. 41-44. · Zbl 0247.65025
[7] K. Dackland and B. K\aagström, {\it Blocked algorithms and software for reduction of a regular matrix pair to generalized Schur form}, ACM Trans. Math. Software, 25 (1999), pp. 425-454. · Zbl 0962.65041
[8] J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart, {\it LINPACK Users’ Guide}, SIAM, Philadelphia, 1979.
[9] J. J. Dongarra, J. Du Croz, S. Hammarling, and I. Duff, {\it Algorithm \(679\)—A set of level 3 basic linear algebra subprograms: Model implementation and test programs}, ACM Trans. Math. Software, 16 (1990), pp. 18-28. · Zbl 0900.65116
[10] J. J. Dongarra, J. Du Croz, S. Hammarling, and I. Duff, {\it A set of level 3 basic linear algebra subprograms}, ACM Trans. Math. Software, 16 (1990), pp. 1-17. · Zbl 0900.65115
[11] J. J. Dongarra, I. S. Duff, D. C. Sorensen, and H. A. van der Vorst, {\it Numerical Linear Algebra for High-Performance Computers}, Software, Environments, and Tools, SIAM, Philadelphia, 1998. · Zbl 0914.65014
[12] V. Fock, {\it Näherungsmethode zur Lösung des quantenmechanischen Mehrkörperproblems}, Z. Phys., 61 (1930), pp. 126-148. · JFM 56.1313.08
[13] L. Kaufman, {\it Banded eigenvalue solvers on vector machines}, ACM Trans. Math. Software, 10 (1984), pp. 73-86. · Zbl 0573.65024
[14] L. Kaufman, {\it Band reduction algorithms revisited}, ACM Trans. Math. Software, 26 (2000), pp. 551-567.
[15] W. Kohn and L. J. Sham, {\it Self-consistent equations including exchange and correlation effects}, Phys. Rev. (2), 140 (1965), pp. A1133-A1138.
[16] B. Lang, {\it Effiziente Orthogonaltransformationen bei der Eigen- und Singulärwertberechnung}, Habilitationsschrift, Fachbereich Mathematik, Bergische Universität GH Wuppertal, Germany, 1997 (in German). · Zbl 0885.65040
[17] B. Lang, {\it Efficient eigenvalue and singular value computations on shared memory machines}, Parallel Comput., 25 (1999), pp. 845-860. · Zbl 0945.65036
[18] A. Marek, V. Blum, R. Johanni, V. Havu, B. Lang, T. Auckenthaler, A. Heinecke, H.-J. Bungartz, and H. Lederer, {\it The ELPA library: Scalable parallel eigenvalue solutions for electronic structure theory and computational science}, J. Phys., 26 (2014), 213201.
[19] M. Rippl, {\it Efficient Transformation of the General Eigenproblem with Symmetric Banded Matrices to a Banded Standard Eigenproblem}, PASC17, Platform for Advanced Scientific Computing (PASC) Conference, 2017, Lugano, Switzerland.
[20] C. C. J. Roothaan, {\it Modern developments in molecular orbital theory}, Rev. Modern Phys., 23 (1951), pp. 69-89. · Zbl 0045.28502
[21] R. Schreiber and C. Van Loan, {\it A storage-efficient \({WY}\) representation for products of Householder transformations}, SIAM J. Sci. Stat. Comput., 10 (1989), pp. 53-57. · Zbl 0664.65025
[22] J. H. Wilkinson, {\it Some recent advances in numerical linear algebra}, in Proceedings of the IMA Conference on The State of the Art in Numerical Analysis, York, D. Jacobs, ed., Academic Press, London, 1977, pp. 3-53.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.