Hierarchical matrix: Difference between revisions

Revision as of 09:31, 22 May 2024

Latest revision as of 21:04, 14 April 2025

(One intermediate revision by one other user not shown)

Line 1:

{{Short description|Approximation method}}

{{Short description|Hierarchical Matrices (H-matrices): Used for data-sparse approximations of non-sparse matrices.Sparse Matrix: Dimension ( n ) can be stored in ( O(n) ) units of storage.Non-sparse Matrix: Requires ( O(n^2) ) units of storage, which is costly for larg}}

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|s2cid=24294140 }}</ref><ref name="GRHA02">{{cite journal|last1=Grasedyck|first1=Lars|last2=Hackbusch|first2=Wolfgang|date=2003|title=Construction and arithmetics of H-matrices|journal=Computing|volume=70|issue=4|pages=295&ndash;334|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|doi=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 by storing only its non-zero entries, a non-sparse matrix would require <math>O(n^2)</math> units of storage, and using this type of matrices for large problems would therefore be prohibitively expensive in terms of storage and computing time. Hierarchical matrices provide an approximation requiring only <math>O(n k\,\log(n))</math> units of storage, where <math>k</math> is a 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">{{cite journal|last1=Hackbusch|first1=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|doi=10.1007/PL00021408 }}</ref><ref name="MB00">{{cite journal|last=Bebendorf|first=Mario|title=Approximation of boundary element matrices|date=2000|journal=Numer. Math.|volume=86|issue=4|pages=565–589|doi=10.1007/pl00005410|s2cid=206858339 }}</ref><ref name="BERJ03">{{cite journal|last1=Bebendorf|first1=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|s2cid=16501661 }}</ref><ref name="BOGR05">{{cite journal|last1=Börm|first1=Steffen|last2=Grasedyck|first2=Lars|date=2005|title=Hybrid cross approximation of integral operators|journal=Numer. Math.|volume=101|issue=2|pages=221&ndash;249|doi=10.1007/s00211-005-0618-1|citeseerx=10.1.1.330.8950|s2cid=263882011 }}</ref><ref name="BOCH16">{{cite journal|last1=Börm|first1=Steffen|last2=Christophersen|first2=Sven|date=2016|title=Approximation of integral operators by Green quadrature and nested cross approximation|journal=Numer. Math.|volume=133|issue=3|pages=409&ndash;442|doi=10.1007/s00211-015-0757-y|arxiv=1404.2234|s2cid=253745725 }}</ref>

Line 108 ⟶ 109:

[https://github.com/JuliaMatrices/HierarchicalMatrices.jl HierarchicalMatrices.jl] is a Julia package implementing hierarchical matrices.

[[Category:Matrices (mathematics)]]