The LR Cholesky algorithm for symmetric hierarchical matrices. (English) Zbl 1281.65051
Summary: We investigate the application of the LR Cholesky algorithm to symmetric hierarchical matrices, symmetric simple structured hierarchical matrices and symmetric hierarchically semiseparable (HSS) matrices. The data-sparsity of these matrices make the otherwise expensive LR Cholesky algorithm applicable, as long as the data-sparsity is preserved. We see in an example that the ranks of the low rank blocks grow and the data-sparsity gets lost. {
} We explain this behavior by applying a theorem on the structure preservation of diagonal plus semiseparable matrices under LR Cholesky transformations. Therefore, we have to give a new more constructive proof for the theorem. We show that the structure of \(\mathcal H_\ell\)-matrices is almost preserved and so the LR Cholesky algorithm is of almost quadratic complexity for \(\mathcal H_\ell\)-matrices.
MSC:
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65F50 | Computational methods for sparse matrices |
Keywords:
symmetric hierarchical matrices; eigenvalues; LR Cholesky algorithm; semiseparable matrices; \(\mathcal H_\ell\)-matrices; numerical example; sparse matricesReferences:
| [1] | Anderson, E.; Bai, Z.; Bischof, C.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Sorensen, D., LAPACK Users’ Guide (1999), SIAM: SIAM Philadelphia, PA · Zbl 0934.65030 |
| [2] | (Bai, Z.; Demmel, J.; Dongarra, J.; Ruhe, A.; van der Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (2000), SIAM: SIAM Philadelphia, PA) · Zbl 0965.65058 |
| [3] | Bebendorf, M., Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Lecture Notes in Computational Science and Engineering (LNCSE), vol. 63 (2008), Springer Verlag: Springer Verlag Berlin, Heidelberg · Zbl 1151.65090 |
| [4] | Benner, P.; Faßbender, H.; Watkins, D. S., Two connections between the SR and HR eigenvalue algorithms, Linear Algebra Appl., 272, 17-32 (1997) · Zbl 0899.65018 |
| [5] | Benner, P.; Mach, T., On the QR decomposition of \(H\)-matrices, Computing, 88, 3-4, 111-129 (2010) · Zbl 1211.65049 |
| [6] | 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 |
| [7] | Benner, P.; Mach, T., The preconditioned inverse iteration for hierarchical matrices, Numer. Linear Algebra Appl., 20, 1, 150-166 (2013) · Zbl 1289.65074 |
| [8] | Bevilacqua, R.; Bozzo, E.; Del Corso, G. M., qd-type methods for quasiseparable matrices, SIAM J. Matrix Anal. Appl., 32, 3, 722-747 (2011) · Zbl 1238.65025 |
| [9] | Börm, S.; Grasedyck, L.; Hackbusch, W., Introduction to hierarchical matrices with applications, Eng. Anal. Boundary Elements, 27, 405-422 (2003) · Zbl 1035.65042 |
| [10] | Delvaux, S.; Frederix, K.; Van Barel, M., Transforming a hierarchical into a unitary-weight representation, Electron. Trans. Numer. Anal., 33, 163-188 (2009) · Zbl 1188.65056 |
| [11] | Delvaux, S.; Van Barel, M., Structures preserved by the QR-algorithm, J. Comput. Appl. Math., 187, 1, 29-40 (2005) · Zbl 1083.65043 |
| [12] | Delvaux, S.; Van Barel, M., Rank structures preserved by the QR-algorithm: the singular case, J. Comput. Appl. Math., 189, 157-178 (2006) · Zbl 1090.65044 |
| [13] | Fasino, D., Rational Krylov matrices and QR steps on Hermitian diagonal-plus-semiseparable matrices, Numer. Linear Algebra Appl., 12, 743-754 (2005) · Zbl 1164.15339 |
| [14] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 0865.65009 |
| [16] | Grasedyck, L.; Hackbusch, W., Construction and arithmetics of \(H\)-matrices, Computing, 70, 4, 295-334 (2003) · Zbl 1030.65033 |
| [17] | Hackbusch, W., A sparse matrix arithmetic based on \(H\)-matrices. Part I: Introduction to \(H\)-matrices, Computing, 62, 2, 89-108 (1999) · Zbl 0927.65063 |
| [18] | Hackbusch, W., Hierarchische Matrizen. Hierarchische Matrizen, Algorithmen und Analysis (2009), Springer-Verlag: Springer-Verlag Berlin · Zbl 1180.65004 |
| [19] | Hackbusch, W.; Khoromskij, B. N.; Kriemann, R., Hierarchical matrices based on a weak admissibility criterion, Computing, 73, 207-243 (2004) · Zbl 1063.65035 |
| [21] | Parlett, B. N., The Symmetric Eigenvalue Problem (1980), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 0431.65017 |
| [22] | Plestenjak, B.; Van Barel, M.; Van Camp, E., A Cholesky LR algorithm for the positive definite symmetric diagonal-plus-semiseparable eigenproblem, Linear Algebra Appl., 428, 586-599 (2008) · Zbl 1136.65043 |
| [23] | Rutishauser, H., Une méthode pour la détermination des valeurs propres d’une matrice, C. R. Math. Acad. Sci. Paris, 240, 34-36 (1955) · Zbl 0056.35002 |
| [24] | Rutishauser, H., Solution of eigenvalue problems with the LR-transformation, Nat. Bur. Standards Appl. Math. Ser., 49, 47-81 (1958) · Zbl 0123.11303 |
| [25] | Rutishauser, H., Über eine kubisch konvergente Variante der LR-Transformation, Z. Angew. Math. Mech., 40, 1-3, 49-54 (1960) · Zbl 0128.11701 |
| [26] | Rutishauser, H.; Schwarz, H. R., The LR transformation method for symmetric matrices, Numer. Math., 5, 1, 273-289 (1963) · Zbl 0112.34801 |
| [27] | Vandebril, R.; Van Barel, M.; Mastronardi, N., An implicit Q theorem for Hessenberg-like matrices, Mediterranean J. Math., 2, 259-275 (2005) · Zbl 1150.15010 |
| [28] | Vandebril, R.; Van Barel, M.; Mastronardi, N., An implicit QR algorithm for symmetric semiseparable matrices, Numer. Linear Algebra Appl., 12, 7, 625-658 (2005) · Zbl 1164.65368 |
| [29] | Watkins, D. S., QR-like algorithms for eigenvalue problems, J. Comput. Appl. Math., 123, 67-83 (2000) · Zbl 0979.65027 |
| [30] | Watkins, D. S., The Matrix Eigenvalue Problem: GR and \(K\) rylov Subspace Methods (2007), SIAM: SIAM Philadelphia, PA, USA · Zbl 1142.65038 |
| [31] | Watkins, D. S.; Elsner, L., Convergence of algorithms of decomposition type for the eigenvalue problem, Linear Algebra Appl., 143 (1995) · Zbl 0712.65025 |
| [32] | Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Oxford University Press: Oxford University Press Oxford · Zbl 0258.65037 |
| [33] | Xia, J.; Chandrasekaran, S.; Gu, M.; Li, X., Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17, 6, 953-976 (2010) · Zbl 1240.65087 |
| [34] | Xu, H., The relation between the QR and LR algorithms, SIAM J. Matrix Anal. Appl., 19, 2, 551-555 (1998) · Zbl 0916.65033 |
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.
