Fast computation of spectral projectors of banded matrices. (English) Zbl 1373.65023


65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
Full Text: DOI arXiv


[1] N. I. Akhiezer, Elements of the Theory of Elliptic Functions, Transl. Math. Monogr. 79, American Mathematical Society, Providence, RI, 1990. · Zbl 0694.33001
[2] P. Arbenz, Divide and conquer algorithms for the bandsymmetric eigenvalue problem, Parallel Comput., 18 (1992), pp. 1105–1128. · Zbl 0761.65025
[3] T. Auckenthaler, V. Blum, H.-J. Bungartz, T. Huckle, R. Johanni, L. Krämer, B. Lang, H. Lederer, and P. R. Willems, Parallel solution of partial symmetric eigenvalue problems from electronic structure calculations, Parallel Comput., 37 (2011), pp. 783–794.
[4] T. Auckenthaler, H.-J. Bungartz, T. Huckle, L. Krämer, B. Lang, and P. Willems, Developing algorithms and software for the parallel solution of the symmetric eigenvalue problem, J. Comput. Sci., 2 (2011), pp. 272–278.
[5] J. Ballani and D. Kressner, Matrices with hierarchical low-rank structures, in Exploiting Hidden Structure in Matrix Computations: Algorithms and Applications, Lecture Notes in Math. 2173, Fond. CIME/CIME Found. Subser., Springer, Cham, 2016, pp. 161–209. · Zbl 1361.65023
[6] U. Baur and P. Benner, Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic, Computing, 78 (2006), pp. 211–234. · Zbl 1111.65039
[7] M. Bebendorf, Hierarchical Matrices. A Means to Efficiently Solve Elliptic Boundary Value Problems, Lect. Notes Comput. Sci. Eng. 63, Springer-Verlag, Berlin, 2008. · Zbl 1151.65090
[8] B. Beckermann and A. Townsend, On the Singular Values of Matrices with Displacement Structure, preprint, , 2016. · Zbl 1386.15024
[9] P. Benner, S. Börm, T. Mach, and K. Reimer, Computing the eigenvalues of symmetric \(\mathcal{H}^2\)-matrices by slicing the spectrum, Comput. Vis. Sci., 16 (2013), pp. 271–282. · Zbl 1376.65044
[10] P. Benner and T. Mach, On the QR decomposition of \(\mathcal{H}\)-matrices, Computing, 88 (2010), pp. 111–129. · Zbl 1211.65049
[11] P. Benner and T. Mach, Computing all or some eigenvalues of symmetric \(\mathcal{H}_{ℓ}\)-matrices, SIAM J. Sci. Comput., 34 (2012), pp. A485–A496, . · Zbl 1387.65034
[12] M. Benzi, P. Boito, and N. Razouk, Decay properties of spectral projectors with applications to electronic structure, SIAM Rev., 55 (2013), pp. 3–64, . · Zbl 1377.65155
[13] G. Beylkin, N. Coult, and M. J. Mohlenkamp, Fast spectral projection algorithms for density-matrix computations, J. Comput. Phys., 152 (1999), pp. 32–54. · Zbl 0945.65049
[14] P. Bientinesi, F. D. Igual, D. Kressner, M. Petschow, and E. S. Quintana-Ortí, Condensed forms for the symmetric eigenvalue problem on multi-threaded architectures, Concurr. Comput. Pract. Exper., 23 (2011), pp. 694–707.
[15] C. H. Bischof, B. Lang, and X. Sun, A framework for symmetric band reduction, ACM Trans. Math. Software, 26 (2000), pp. 581–601. · Zbl 1365.65103
[16] \AA. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996, .
[17] D. Braess and W. Hackbusch, Approximation of \(1/x\) by exponential sums in \([1,∞)\), IMA J. Numer. Anal., 25 (2005), pp. 685–697. · Zbl 1082.65025
[18] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Software, 38 (2011), pp. 1–25. · Zbl 1365.65123
[19] J. W. Demmel, O. A. Marques, B. N. Parlett, and C. Vömel, Performance and accuracy of LAPACK’s symmetric tridiagonal eigensolvers, SIAM J. Sci. Comput., 30 (2008), pp. 1508–1526, . · Zbl 1165.65014
[20] I. S. Dhillon, B. N. Parlett, and C. Vömel, The design and implementation of the MRRR algorithm, ACM Trans. Math. Software, 32 (2006), pp. 533–560. · Zbl 1230.65046
[21] L. Eldén, Algorithms for the regularization of ill-conditioned least squares problems, Nordisk Tidskr. Informationsbehandling (BIT), 17 (1977), pp. 134–145.
[22] L. Eldén, An algorithm for the regularization of ill-conditioned, banded least squares problems, SIAM J. Sci. Statist. Comput., 5 (1984), pp. 237–254, .
[23] I. P. Gavrilyuk, W. Hackbusch, and B. N. Khoromskij, \(\mathcal{H}\)-matrix approximation for the operator exponential with applications, Numer. Math., 92 (2002), pp. 83–111. · Zbl 1005.65113
[24] I. P. Gavrilyuk, W. Hackbusch, and B. N. Khoromskij, Data-sparse approximation to the operator-valued functions of elliptic operator, Math. Comp., 73 (2004), pp. 1297–1324. · Zbl 1065.47009
[25] S. Goedecker, Linear scaling electronic structure methods, Rev. Mod. Phys., 71 (1999), pp. 1085–1123.
[26] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037
[27] L. Grasedyck, W. Hackbusch, and B. N. Khoromskij, Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices, Computing, 70 (2003), pp. 121–165. · Zbl 1239.65026
[28] W. Hackbusch, A sparse matrix arithmetic based on \(\mathcal{H}\)-matrices. I. Introduction to \(\mathcal{H}\)-matrices, Computing, 62 (1999), pp. 89–108. · Zbl 0927.65063
[29] W. Hackbusch, Hierarchical Matrices: Algorithms and Analysis, Springer Ser. Comput. Math. 49, Springer, Heidelberg, 2015. · Zbl 1336.65041
[30] A. Haidar, H. Ltaief, and J. Dongarra, Parallel reduction to condensed forms for symmetric eigenvalue problems using aggregated fine-grained and memory-aware kernels, in Proceedings of the 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, ACM, New York, 2011, 8.
[31] A. Haidar, H. Ltaief, and J. Dongarra, Toward a high performance tile divide and conquer algorithm for the dense symmetric eigenvalue problem, SIAM J. Sci. Comput., 34 (2012), pp. C249–C274, . · Zbl 1261.65038
[32] A. Haidar, R. Solcà, M. Gates, S. Tomov, T. Schulthess, and J. Dongarra, Leading edge hybrid multi-GPU algorithms for generalized eigenproblems in electronic structure calculations, in Supercomputing, Lecture Notes in Comput. Sci. 7905, Springer, Berlin, Heidelberg, 2013, pp. 67–80.
[33] N. J. Higham and F. Tisseur, A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1185–1201, . · Zbl 0959.65061
[34] M. Lintner, Lösung der 2D Wellengleichung mittels hierarchischer Matrizen, Doctoral thesis, TU München, München, Germany, 2002.
[35] M. Lintner, The eigenvalue problem for the 2D Laplacian in \(\mathcal{H}\)-matrix arithmetic and application to the heat and wave equation, Computing, 72 (2004), pp. 293–323. · Zbl 1055.65049
[36] T. Mach, Eigenvalue Algorithms for Symmetric Hierarchical Matrices, Doctoral thesis, TU Chemnitz, Chemnitz, Germany, 2012.
[37] O. A. Marques, C. Vömel, J. W. Demmel, and B. N. Parlett, Algorithm 880: A testing infrastructure for symmetric tridiagonal eigensolvers, ACM Trans. Math. Software, 35 (2009), 8.
[38] Y. Nakatsukasa, Z. Bai, and F. Gygi, Optimizing Halley’s iteration for computing the matrix polar decomposition, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2700–2720, . · Zbl 1215.65081
[39] Y. Nakatsukasa and R. W. Freund, Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: The power of Zolotarev’s functions, SIAM Rev., 58 (2016), pp. 461–493, . · Zbl 1383.15012
[40] Y. Nakatsukasa and N. J. Higham, Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD, SIAM J. Sci. Comput., 35 (2013), pp. A1325–A1349, . · Zbl 1326.65049
[41] P. P. Petrushev and V. A. Popov, Rational Approximation of Real Functions, Encyclopedia Math. Appl. 28, Cambridge University Press, Cambridge, UK, 1987. · Zbl 0644.41010
[42] M. Petschow, E. Peise, and P. Bientinesi, High-performance solvers for dense Hermitian eigenproblems, SIAM J. Sci. Comput., 35 (2013), pp. C1–C22, . · Zbl 1264.65054
[43] H. R. Schwarz, Handbook Series Linear Algebra: Tridiagonalization of a symmetric band matrix, Numer. Math., 12 (1968), pp. 231–241. · Zbl 0165.50201
[44] E. Solomonik, G. Ballard, J. Demmel, and T. Hoefler, A Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue Problem, preprint, , 2016.
[45] R. Vandebril, M. Van Barel, and N. Mastronardi, Matrix Computations and Semiseparable Matrices. Vol. 1. Linear Systems, Johns Hopkins University Press, Baltimore, 2008. · Zbl 1141.65019
[46] J. Vogel, J. Xia, S. Cauley, and V. Balakrishnan, Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions, SIAM J. Sci. Comput., 38 (2016), pp. A1358–A1382, . · Zbl 1338.65104
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.