Year: 2021
Author: Jianlin Xia
CSIAM Transactions on Applied Mathematics, Vol. 2 (2021), Iss. 2 : pp. 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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/csiam-am.2021.nla.02
CSIAM Transactions on Applied Mathematics, Vol. 2 (2021), Iss. 2 : pp. 263–296
Published online: 2021-01
AMS Subject Headings: Global Science Press
Copyright: COPYRIGHT: © Global Science Press
Pages: 34
Keywords: MHS structure numerical rank representative subset inner-layer structure generator fast multipole method.
Author Details
-
Overlapping Domain Decomposition Preconditioner for Integral Equations
Chen, Chao | Biros, GeorgeSIAM Journal on Scientific Computing, Vol. 44 (2022), Iss. 6 P.A3617
https://doi.org/10.1137/21M1442917 [Citations: 0] -
SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices
Ou, Xiaofeng | Xia, JianlinSIAM Journal on Scientific Computing, Vol. 44 (2022), Iss. 5 P.A3041
https://doi.org/10.1137/21M1438633 [Citations: 8] -
Making the Nyström Method Highly Accurate for Low-Rank Approximations
Xia, Jianlin
SIAM Journal on Scientific Computing, Vol. 46 (2024), Iss. 2 P.A1076
https://doi.org/10.1137/23M1585039 [Citations: 0] -
Rank‐structured approximation of some Cauchy matrices with sublinear complexity
Lepilov, Mikhail | Xia, JianlinNumerical Linear Algebra with Applications, Vol. 31 (2024), Iss. 1
https://doi.org/10.1002/nla.2526 [Citations: 0] -
Solving Linear Systems on a GPU with Hierarchically Off-Diagonal Low-Rank Approximations
Chen, Chao | Martinsson, Per-GunnarSC22: International Conference for High Performance Computing, Networking, Storage and Analysis, (2022), P.1
https://doi.org/10.1109/SC41404.2022.00089 [Citations: 1] -
HODLRdD: A new black-box fast algorithm for N-body problems in d-dimensions with guaranteed error bounds
Khan, Ritesh | Kandappan, V.A. | Ambikasaran, SivaramJournal of Computational Physics, Vol. 501 (2024), Iss. P.112786
https://doi.org/10.1016/j.jcp.2024.112786 [Citations: 0] -
Multi-core parallel BRSMF method for 2D3T radiation diffusion equations
Zuo, Xian-yu | Wang, Qian-qian | Ge, Qiang | Qiao, Baojun | Fan, Ming-hu | Zhang, Li-taoWireless Networks, Vol. 27 (2021), Iss. 7 P.4363
https://doi.org/10.1007/s11276-021-02646-7 [Citations: 0]