@Article{CSIAM-AM-2-263,
author = {Xia , Jianlin},
title = {Multi-Layer Hierarchical Structures},
journal = {CSIAM Transactions on Applied Mathematics},
year = {2021},
volume = {2},
number = {2},
pages = {263--296},
abstract = {<p style="text-align: justify;">In structured matrix computations, existing rank structures such as hierarchically semiseparable (HSS) forms admit fast and stable factorizations. However, for
discretized problems, such forms are restricted to 1D cases. In this work, we propose
a framework to break such a 1D barrier. We study the feasibility of designing multi-layer hierarchically semiseparable (MHS) structures for the approximation of dense
matrices arising from multi-dimensional discretized problems such as certain integral
operators. The MHS framework extends HSS forms to higher dimensions via the integration of multiple layers of structures, i.e., structures within the dense generator representations of HSS forms. Specifically, in the 2D case, we lay theoretical foundations
and justify the existence of MHS structures based on the fast multipole method (FMM)
and algebraic techniques such as representative subset selection. Rigorous numerical
rank bounds and conditions for the structures are given. Representative subsets of
points and a multi-layer tree are used to intuitively illustrate the structures. The MHS
framework makes it convenient to explore multidimensional FMM structures. MHS
representations are suitable for stable direct factorizations and can take advantage of
existing methods and analysis well developed for simple HSS methods. Numerical
tests for some discretized operators show that the appropriate inner-layer numerical
ranks are significantly smaller than the off-diagonal numerical ranks used in standard
HSS approximations.</p>},
issn = {2708-0579},
doi = {https://doi.org/10.4208/csiam-am.2021.nla.02},
url = {http://global-sci.org/intro/article_detail/csiam-am/18885.html}
}