SMASH: Structured matrix approximation by separation and hierarchy
From MaRDI portal
Publication:6286708
DOI10.1002/NLA.2204arXiv1705.05443MaRDI QIDQ6286708FDOQ6286708
Authors: Difeng Cai, Edmond Chow, Lucas Erlandson, Y. Saad, Yuanzhe Xi 
Publication date: 15 May 2017
Abstract: This paper presents an efficient method to perform Structured Matrix Approximation by Separation and Hierarchy (SMASH), when the original dense matrix is associated with a kernel function. Given points in a domain, a tree structure is first constructed based on an adaptive partitioning of the computational domain to facilitate subsequent approximation procedures. In contrast to existing schemes based on either analytic or purely algebraic approximations, SMASH takes advantage of both approaches and greatly improves the efficiency. The algorithm follows a bottom-up traversal of the tree and is able to perform the operations associated with each node on the same level in parallel. A strong rank-revealing factorization is applied to the initial analytic approximation in the separation regime so that a special structure is incorporated into the final nested bases. As a consequence, the storage is significantly reduced on one hand and a hierarchy of the original grid is constructed on the other hand. Due to this hierarchy, nested bases at upper levels can be computed in a similar way as the leaf level operations but on coarser grids. The main advantages of SMASH include its simplicity of implementation, its flexibility to construct various hierarchical rank structures and a low storage cost. Rigorous error analysis and complexity analysis are conducted to show that this scheme is fast and stable. The efficiency and robustness of SMASH are demonstrated through various test problems arising from integral equations, structured matrices, etc.
Factorization of matrices (15A23) Numerical linear algebra (65F99) Toeplitz, Cauchy, and related matrices (15B05)
This page was built for publication: SMASH: Structured matrix approximation by separation and hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6286708)
