Options
A block householder-based algorithm for the QR decomposition of hierarchical matrices
Publikationstyp
Journal Article
Date Issued
2024
Sprache
English
Author(s)
Griem, Vincent
Volume
45
Issue
2
Start Page
847
End Page
874
Citation
SIAM Journal on Matrix Analysis and Applications 45 (2): 847-874 (2024)
Publisher DOI
Scopus ID
Publisher
Society for Industrial and Applied Mathematics, SIAM
Hierarchical matrices are dense but data-sparse matrices that use low-rank factorizations of suitable submatrices to reduce the storage and computational cost to linear-polylogarithmic complexity. In this paper, we propose a new approach to efficiently compute QR factorizations in the hierarchical matrix format based on block Householder transformations. To prevent unnecessarily high ranks in the resulting factors and to increase speed and accuracy, the algorithm meticulously tracks for which intermediate results low-rank factorizations are available. We also use a special storage scheme for the block Householder reflector to further reduce computational and storage costs. Numerical tests for two- and three-dimensional Laplacian boundary element matrices, different radial basis function kernel matrices, and matrices of typical hierarchical matrix structures but filled with random entries illustrate the performance of the new algorithm in comparison to some other QR algorithms for hierarchical matrices from the literature.
Subjects
block Householder
hierarchical matrices
QR factorization
DDC Class
510: Mathematics