Hierarchical matrix: Difference between revisions

Revision as of 19:56, 5 January 2017

Revision as of 20:27, 5 January 2017

Line 148:

In order to treat very large problems, the structure of hierarchical matrices can be improved:

H²-matrices

<ref name="HAKHSA02">{{cite journal|last=Hackbusch|first=Wolfgang|last2=Khoromskij|first2=Boris N.|last3=Sauter|first3=Stefan|date=2002|title=On H²-matrices|journal=Lectures on Applied Mathematics|pages=9-29|url=http://link.springer.com/chapter/10.1007/978-3-642-59709-1_2}}</ref>

<ref name="HAKHSA02">W. Hackbusch, B. N. Khoromskij and S. A. Sauter,

<ref name="BO10b">{{cite book|last=Börm|first=Steffen|date=2010|title=Efficient Numerical Methods for Non-local Operators: H²-Matrix Compression, Algorithms and Analysis|publisher=EMS Tracts in Mathematics|url=http://www.ems-ph.org/books/book.php?proj_nr=125}}</ref>

''On H²-matrices'',

Lectures on Applied Mathematics (2002), 9–29</ref>

<ref name="BO10b">S. B&ouml;rm,

''Efficient Numerical Methods for Non-local Operators: H²-Matrix Compression, Algorithms and Analysis'',

EMS Tracts in Mathematics 14 (2010)</ref>

replace the general low-rank structure of the blocks by a hierarchical representation closely related to the

[[fast multipole method]] in order to reduce the storage complexity to <math>O(n k)</math>.

Line 159 ⟶ 155:

In the context of boundary integral operators, replacing the fixed rank <math>k</math> by block-dependent ranks

leads to approximations that preserve the rate of convergence of the underlying boundary element method

at a complexity of <math>O(n).</math><ref name="SA00">S. A.{{cite journal|last=Sauter,|first=Stefan|date=2000|title=Variable order panel clustering|journal=Computing|volume=64|pages=223-261|url=http://link.springer.com/article/10.1007/s006070050045}}</ref>

<ref name="BOSA05">{{cite journal|last=Börm|first=Steffen|last2=Sauter|first2=Stefan|date=2005|title=BEM with linear complexity for the classical boundary integral operators|journal=Math. Comp.|volume=74|pages=1139-1177|url=http://www.ams.org/journals/mcom/2005-74-251/S0025-5718-04-01733-8}}</ref>

''Variable order panel clustering'',

Computing (2000), 64:223–261</ref><ref name="BOSA05">S. B&ouml;rm and S. A. Sauter,

Arithmetic operations like multiplication, inversion, Cholesky or LR factorization of H²-matrices

''BEM with linear complexity for the classical boundary integral operators'',

can be implemented based on two fundamental operations: the matrix-vector multiplication with submatrices

Math. Comp. (2005), 74:1139–1177</ref>

and the low-rank update of submatrices.

While the matrix-vector multiplication is straightforward, implementing efficient low-rank updates with

adaptively optimized cluster bases poses a significant challenge<ref name=HARE14">{{cite journal|last=Börm|first=Steffen|last2=Reimer|first2=Knut|date=2015|title=Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates|journal=Comp. Vis. Sci.|volume=16|issue=6|pages=247-258|url=http://www.arxiv.org/abs/1402.5056}}</ref>

== Literature ==