Journal
COMPUTING
Volume 88, Issue 3-4, Pages 111-129Publisher
SPRINGER WIEN
DOI: 10.1007/s00607-010-0087-y
Keywords
Hierarchical matrices; QR decomposition; Orthogonalisation; HQR decomposition
Categories
Funding
- Free State of Saxony [501-G-209]
Ask authors/readers for more resources
The hierarchical (H-) matrix format allows storing a variety of dense matrices from certain applications in a special data-sparse way with linear-polylogarithmic complexity. Many operations from linear algebra like matrix-matrix and matrix-vector products, matrix inversion and LU decomposition can be implemented efficiently using the H-matrix format. Due to its importance in solving many problems in numerical linear algebra like least-squares problems, it is also desirable to have an efficient QR decomposition of H-matrices. In the past, two different approaches for this task have been suggested in Bebendorf (Hierarchical matrices: a means to efficiently solve elliptic boundary value problems. Lecture notes in computational science and engineering (LNCSE), vol 63. Springer, Berlin, 2008) and Lintner (Dissertation, Fakultat fur Mathematik, TU Munchen. http://tumb1.biblio.tu-muenchen.de/publ/diss/ma/2002/lintner.pdf, 2002). We will review the resulting methods and suggest a new algorithm to compute the QR decomposition of an H-matrix. Like other H-arithmetic operations, the H QR decomposition is of linear-polylogarithmic complexity. We will compare our new algorithm with the older ones by using two series of test examples and discuss benefits and drawbacks of the new approach.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available