Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates.

Börm, Steffen and Reimer, Knut (2013) Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates. Computing and Visualization in Science, 16 (6). pp. 247-258. DOI 10.1007/s00791-015-0233-3.

Full text not available from this repository.

Supplementary data:

Abstract

Many matrices appearing in numerical methods for partial differential equations and integral equations are rank-structured, i.e., they contain submatrices that can be approximated by matrices of low rank. A relatively general class of rank-structured matrices are {\mathcal {H}}^2-matrices: they can reach the optimal order of complexity, but are still general enough for a large number of practical applications. We consider algorithms for performing algebraic operations with {\mathcal {H}}^2-matrices, i.e., for approximating the matrix product, inverse or factorizations in almost linear complexity. The new approach is based on local low-rank updates that can be performed in linear complexity. These updates can be combined with a recursive procedure to approximate the product of two {\mathcal {H}}^2-matrices, and these products can be used to approximate the matrix inverse and the LR or Cholesky factorization. Numerical experiments indicate that the new algorithm leads to preconditioners that require {\mathcal {O}}(n)units of storage, can be evaluated in {\mathcal {O}}(n)operations, and take {\mathcal {O}}(n \log n)operations to set up.

Document Type: Article
Research affiliation: Kiel University > Kiel Marine Science
OceanRep > The Future Ocean - Cluster of Excellence > FO-R11
OceanRep > The Future Ocean - Cluster of Excellence
Kiel University
Refereed: Yes
Open Access Journal?: Yes
DOI etc.: 10.1007/s00791-015-0233-3
ISSN: 1432-9360
Date Deposited: 14 Dec 2017 13:53
Last Modified: 11 Apr 2019 06:37
URI: http://oceanrep.geomar.de/id/eprint/40657

Actions (login required)

View Item View Item