Volume 2, Issue 2
Multi-Layer Hierarchical Structures

Jianlin Xia

CSIAM Trans. Appl. Math., 2 (2021), pp. 263-296.

Published online: 2021-05

Export citation
  • Abstract

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.

  • AMS Subject Headings

15A23, 65F05, 65F30

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@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 = {

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.

}, 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} }
TY - JOUR T1 - Multi-Layer Hierarchical Structures AU - Xia , Jianlin JO - CSIAM Transactions on Applied Mathematics VL - 2 SP - 263 EP - 296 PY - 2021 DA - 2021/05 SN - 2 DO - http://doi.org/10.4208/csiam-am.2021.nla.02 UR - https://global-sci.org/intro/article_detail/csiam-am/18885.html KW - MHS structure, numerical rank, representative subset, inner-layer structure, generator, fast multipole method. AB -

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.

Jianlin Xia. (2021). Multi-Layer Hierarchical Structures. CSIAM Transactions on Applied Mathematics. 2 (2). 263-296. doi:10.4208/csiam-am.2021.nla.02
Copy to clipboard
The citation has been copied to your clipboard