Hierarchical matrix: Difference between revisions

Revision as of 02:33, 6 January 2017

Revision as of 18:26, 7 January 2017

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|pages=89-108}}</ref>

<ref name="HA99">W. Hackbusch,

<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|pages=295-334|url=http://dx.doi.org/10.1007/s00607-003-0019-1}}</ref>

''A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices'',

<ref name="HA09">{{cite book|last=Hackbusch|first=Wolfgang|date=2015|title=Hierarchical matrices: Algorithms and Analysis|publisher=Springer|url=http://dx.doi.org/10.1007/978-3-662-47324-5}}</ref>

Computing (1999), 62:89–108</ref>

<ref name="MB08">M. Bebendorf,

''Hierarchical matrices: A means to efficiently solve elliptic boundary value problems'',

Springer (2008)</ref>

<ref name="HA09">W. Hackbusch,

''Hierarchische Matrizen. Algorithmen und Analysis'',

Springer (2009)</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 16 ⟶ 10:

parameter controlling the accuracy of the approximation.

In typical applications, e.g., when discretizing integral equations

''<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">W. Hackbusch and B. N. Khoromskij,

''<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-47}}</ref>

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

Computing (2000), 64:21–47</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-24}}</ref>

<ref name="MB00">M. Bebendorf,

<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|pages=221-249}}</ref>

''Approximation of boundary element matrices'',

<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|pages=409-442|url=http://dx.doi.org/10.1007/s00211-015-0757-y}}</ref>,

Num. Math. (2000), 86:565--589</ref>

<ref name="BERJ03">M. Bebendorf and S. Rjasanow,

''Adaptive low-rank approximation of collocation matrices'',

Computing (2003), 70:1–24</ref>

<ref name="BOGR05">S. B&ouml;rm and L. Grasedyck,

''Hybrid cross approximation of integral operators'',

Num. Math. (2005), 101:221–249</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-28}}</ref>

<ref name="BEHA03">M. Bebendorf and W. Hackbusch,

<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|pages=165-193|url=http://dx.doi.org/10.1007/s00211-009-0278-7}}</ref>

''Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with <math>L^\infty</math>-coefficients'',

Num. Math. (2003), 95:1–28</ref>

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

''Approximation of solution operators of elliptic partial differential equations by H- and H²-matrices'',

Num. Math. (2010), 115:165&ndash;193</ref>

<ref name ="FAMEPR13">M. Faustmann, J.&nbsp;M. Melenk and D. Praetorius,

''H-matrix approximability of the inverses of FEM matrices'',

Line 42 ⟶ 26:

Compared to many other data-sparse representations of non-sparse matrices, hierarchical matrices offer a major advantage:

the results of matrix arithmetic operations like matrix multiplication, factorization or inversion can be approximated

in <math>O(n k^\alpha\,\log(n)^\beta)</math> operations, where <math>\alpha,\beta\in\{1,2,3\}.</math><ref name="HAGR03GRHA02"/>L. Grasedyck and W. Hackbusch,

''Construction and Arithmetics of H-Matrices'',

Computing (2003), 70:295–334</ref>

== Basic idea ==