Hierarchical matrix: Difference between revisions

Revision as of 08:33, 21 August 2018

Revision as of 13:33, 22 November 2018

Line 1:

In [[numerical mathematics]], '''hierarchical matrices (H-matrices)'''

<ref name="HA99">{{cite journal|last=Hackbusch|first=Wolfgang|date=1999|title=A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices|journal=Computing|volume=62|issue=2|pages=89&ndash;108|doi=10.1007/s006070050015}}</ref>

<ref name="GRHA02">{{cite journal|last=Grasedyck|first=Lars|last2=Hackbusch|first2=Wolfgang|date=2003|title=Construction and arithmetics of H-matrices|journal=Computing|volume=70|issue=4|pages=295&ndash;334|url=https://dx.doi.org/10.1007/s00607-003-0019-1|doi=10.1007/s00607-003-0019-1}}</ref>

<ref name="HA09">{{cite book|last=Hackbusch|first=Wolfgang|date=2015|title=Hierarchical matrices: Algorithms and Analysis|volume=49|publisher=Springer|url=https://dx.doi.org/=10.1007/978-3-662-47324-5|series=Springer Series in Computational Mathematics|isbn=978-3-662-47323-8}}</ref>

are used as data-sparse approximations of non-sparse matrices.

While a [[sparse matrix]] of dimension <math>n</math> can be represented efficiently in <math>O(n)</math> units of storage

Line 12:

<ref name="MB08">{{cite book|last=Bebendorf|first=Mario|date=2008|title=Hierarchical matrices: A means to efficiently solve elliptic boundary value problems|publisher=Springer}}</ref>

<ref name="HAKH00">{{cite journal|last=Hackbusch|first=Wolfgang|last2=Khoromskij|first2=Boris N.|date=2000|title=A sparse H-Matrix Arithmetic. Part II: Application to Multi-Dimensional Problems|journal=Computing|volume=64|pages=21&ndash;47}}</ref>

<ref name="MB00">{{cite journal|last=Bebendorf|first=Mario|title=Approximation of boundary element matrices|date=2000|journal=Num. Math.|volume=86|issue=4|pages=565–589|doi=10.1007/pl00005410}}</ref>

<ref name="BERJ03">{{cite journal|last=Bebendorf|first=Mario|last2=Rjasanow|first2=Sergej|date=2003|title=Adaptive low-rank approximation of collocation matrices|journal=Computing|volume=70|pages=1&ndash;24|doi=10.1007/s00607-002-1469-6|citeseerx=10.1.1.133.182}}</ref>

<ref name="BOGR05">{{cite journal|last=Börm|first=Steffen|last2=Grasedyck|first2=Lars|date=2005|title=Hybrid cross approximation of integral operators|journal=Num. Math.|volume=101|issue=2|pages=221&ndash;249|doi=10.1007/s00211-005-0618-1|citeseerx=10.1.1.330.8950}}</ref>

,<ref name="BOCH16">{{cite journal|last=Börm|first=Steffen|last2=Christophersen|first2=Sven|date=2016|title=Approximation of integral operators by Green quadrature and nested cross approximation|journal=Num. Math.|volume=133|issue=3|pages=409&ndash;442|url=https://dx.doi.org/10.1007/s00211-015-0757-y|doi=10.1007/s00211-015-0757-y|arxiv=1404.2234}}</ref>

preconditioning the resulting systems of linear equations

,<ref name="FAMEPR16">{{cite journal|last=Faustmann|first=Markus|last2=Melenk|first2=J.&nbsp;Markus|last3=Praetorius|first3=Dirk|date=2016|title=Existence of H-matrix approximants to the inverses of BEM matrices: The simple-layer operator|journal=Math. Comp.|volume=85|issue=297|pages=119&ndash;152|url=https://dx.doi.org/10.1090/mcom/2990|doi=10.1090/mcom/2990|arxiv=1311.5028}}</ref>

or solving elliptic partial differential equations

<ref name="BEHA03">{{cite journal|last=Bebendorf|first=Mario|last2=Hackbusch|first2=Wolfgang|date=2003|title=Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with <math>L^\infty</math>-coefficients|journal=Num. Math.|volume=95|pages=1&ndash;28|doi=10.1007/s00211-002-0445-6}}</ref>

<ref name="BO10">{{cite journal|last=Börm|first=Steffen|date=2010|title=Approximation of solution operators of elliptic partial differential equations by H- and H²-matrices|journal=Num. Math.|volume=115|issue=2|pages=165&ndash;193|url=https://dx.doi.org/10.1007/s00211-009-0278-7|doi=10.1007/s00211-009-0278-7}}</ref>

,<ref name ="FAMEPR13">{{cite journal|last=Faustmann|first=Markus|last2=Melenk|first2=J.&nbsp;Markus|last3=Praetorius|first3=Dirk|date=2015|title=H-matrix approximability of the inverses of FEM matrices|journal=Num. Math.|volume=131|issue=4|pages=615&ndash;642|urldoi=https://dx.doi.org/10.1007/s00211-015-0706-9|doiarxiv=101308.1007/s00211-015-0706-90499}}</ref>

a rank proportional to <math>\log(1/\epsilon)^\gamma</math> with a small constant <math>\gamma</math> is sufficient to ensure an

accuracy of <math>\epsilon</math>.

Line 87:

<ref name="MB00"/>

<ref name="BERJ03"/>

<ref name="TY00">{{cite journal|last=Tyrtyshnikov|first=Eugene|date=2000|title=Incomplete cross approximation in the mosaic-skeleton method|journal=Computing|volume=64|issue=4|pages=367&ndash;380|doi=10.1007/s006070070031|citeseerx=10.1.1.100.6153}}</ref>

that use only the entries of the original matrix <math>G</math> to construct a [[low rank approximation|low-rank approximation]].

Line 116:

[[Schur complement]]s of diagonal blocks and combining both using the matrix-matrix multiplication.

In a similar way, the [[LU decomposition]]

<ref name="BE07">{{cite journal|last=Bebendorf|first=Mario|date=2007|title=Why finite element discretizations can be factored by triangular hierarchical matrices|journal=SIAM J. Num. Anal.|volume=45|issue=4|pages=1472&ndash;1494|doi=10.1137/060669747}}</ref>

<ref name="GRKRBO09">{{cite journal|last=Grasedyck|first=Lars|last2=Kriemann|first2=Ronald|last3=Le&nbsp;Borne|first3=Sabine|date=2009|title=Domain decomposition based H-LU preconditioning|journal=Num. Math.|volume=112|issue=4|pages=565&ndash;600|doi=10.1007/s00211-009-0218-6}}</ref>

can be constructed using only recursion and multiplication.

Both operations also require <math>O(n k^2\,\log(n)^2)</math> operations.

Line 124:

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

H²-matrices

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

<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|isbn=9783037190913}}</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 131:

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">{{cite journal|last=Sauter|first=Stefan|date=2000|title=Variable order panel clustering|journal=Computing|volume=64|issue=3|pages=223&ndash;261|url=https://link.springer.com/article/10.1007/s006070050045|doi=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|issue=251|pages=1139&ndash;1177|url=http://www.ams.org/journals/mcom/2005-74-251/S0025-5718-04-01733-8|doi=10.1090/s0025-5718-04-01733-8}}</ref>

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

Line 138:

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&ndash;258|urlarxiv=http://www1402.arxiv5056|doi=10.org1007/abs/1402.5056s00791-015-0233-3}}</ref>

== Literature ==