×

zbMATH — the first resource for mathematics

Introduction to hierarchical matrices with applications. (English) Zbl 1035.65042
Summary: We give a short introduction to methods for the data-sparse approximation of matrices resulting from the discretisation of non-local operators occurring in boundary integral methods, as the inverses of partial differential operators or as solutions of control problems.
The result of the approximation will be so-called hierarchical matrices (or short \(\mathcal H\)-matrices). These matrices form a subset of the set of all matrices and have a data-sparse representation. The essential operations for these matrices (matrix-vector and matrix-matrix multiplication, addition and inversion) can be performed in, up to logarithmic factors, optimal complexity.
We give a review of specialised variants of \(\mathcal H\)-matrices, especially of \(\mathcal H^2\)-matrices, and finally consider applications of the different methods to problems from integral equations, partial differential equations and control theory.

MSC:
65F30 Other matrix algorithms (MSC2010)
15A24 Matrix equations and identities
65F50 Computational methods for sparse matrices
65N38 Boundary element methods for boundary value problems involving PDEs
65K10 Numerical optimization and variational techniques
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bebendorf, M., Approximation of boundary element matrices, Numer math, 86, 565-589, (2000) · Zbl 0966.65094
[2] Bebendorf M, Hackbusch W. Existence of \(H\)-matrix approximants to the inverse FE-matrix of elliptic operators with L∞-coefficients. Technical report. Leipzig, Germany: Max Planck Institute for Mathematics in the Sciences; 2002 (submitted for publication). · Zbl 1033.65100
[3] Bebendorf, M.; Rjasanov, S., Technical report 39, Technical report 39, (2001), Universität Saarbrücken
[4] Börm, S.; Hackbusch, W., Technical report 86, Technical report 86, (2001), Max Planck Institute for Mathematics in the Sciences Leipzig, Germany
[5] Börm, S.; Hackbusch, W., Technical report 104, Technical report 104, (2001), Max Planck Institute for Mathematics in the Sciences Leipzig, Germany
[6] Gavrilyuk, I.; Hackbusch, W.; Khoromskij, B., Technical report 42, Technical report 42, (2000), Max Planck Institute for Mathematics in the Sciences Leipzig, Germany
[7] Gavrilyuk, I.; Hackbusch, W.; Khoromskij, B., \(H\)-matrix approximation for elliptic solution operators on cylindric domains, east – west, J numer math, 9, 25-58, (2001) · Zbl 1012.65134
[8] Giebermann, K., Multilevel approximation of boundary integral operators, Computing, 67, 183-207, (2001) · Zbl 0995.65121
[9] Grasedyck, L., Technical report 13, Technical report 13, (2001), University Kiel Germany
[10] Grasedyck L. Theorie und Anwendungen Hierarchischer Matrizen. PhD Thesis. Universität Kiel; 2001.
[11] Grasedyck L, Hackbusch W. Construction and arithmetics of \(H\)-matrices. Technical report. Leipzig, Germany: Max Planck Institute for Mathematics in the Sciences; 2002 (submitted for publication). · Zbl 1030.65033
[12] Grasedyck L, Hackbusch W, Khoromskij B. Application of \(H\)-matrices in control theory. Technical report. Leipzig, Germany: Max Planck Institute for Mathematics in the Sciences; 2002 (submitted for publication). · Zbl 1239.65026
[13] Grasedyck, L.; Hackbusch, W.; LeBorne, S., Technical report 106, Technical report 106, (2001), Max Planck Institute of Mathematics in the Sciences Leipzig, Germany
[14] Hackbusch, W., A sparse matrix arithmetic based on \(H\)-matrices. part I. introduction to \(H\)-matrices, Computing, 62, 89-108, (1999) · Zbl 0927.65063
[15] Hackbusch, W.; Khoromskij, B., Technical report 66, Technical report 66, (2000), Max Planck Institute for Mathematics in the Sciences Leipzig, Germany
[16] Hackbusch, W.; Khoromskij, B., \(H\)-matrix approximation on graded meshes, (), 307-316 · Zbl 0960.65047
[17] Hackbusch, W.; Khoromskij, B., A sparse matrix arithmetic based on \(H\)-matrices. part II. application to multi-dimensional problems, Computing, 64, 21-47, (2000) · Zbl 0962.65029
[18] Hackbusch, W.; Khoromskij, B., Towards \(H\)-matrix approximation of linear complexity, (), 194-220 · Zbl 1004.65125
[19] Hackbusch, W.; Khoromskij, B.; Sauter, S., On \(H\^{}\{2\}\)-matrices, (), 9-29 · Zbl 0963.65043
[20] Hackbusch, W.; Nowak, Z.P., On the fast matrix multiplication in the boundary element method by panel clustering, Numerische Mathematik, 54, 463-491, (1989) · Zbl 0641.65038
[21] Khoromskij, B., Technical report 79, Technical report 79, (2001), Max Planck Institute for Mathematics in the Sciences Leipzig, Germany
[22] Penzl, T., Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Syst control lett, 40, 139-144, (2000) · Zbl 0977.93034
[23] Roberts, J.D., Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Int J control, 32, 677-687, (1980) · Zbl 0463.93050
[24] Rosen, J.I.G.; Wang, C., A multilevel technique for the approximate solution of operator Lyapunov and algebraic Riccati equations, SIAM J numer anal, 32, 514-541, (1995) · Zbl 0857.65047
[25] Sauter, S., Variable order panel clustering, Computing, 64, 223-261, (2000) · Zbl 0959.65135
[26] Tyrtyshnikov, E., Mosaic-skeleton approximation, Calcolo, 33, 47-57, (1996) · Zbl 0906.65048
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.