SMASH: Structured matrix approximation by separation and hierarchy

Difeng Cai, Edmond Chow, Lucas Erlandson, Yousef Saad, Yuanzhe Xi

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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 the points in a domain, a tree structure is first constructed based on an adaptive partition 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 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. The efficiency and robustness of SMASH are demonstrated through various test problems arising from integral equations, structured matrices, etc.

Original languageEnglish (US)
Article numbere2204
JournalNumerical Linear Algebra with Applications
Issue number6
StatePublished - Dec 2018

Bibliographical note

Funding Information:
We would like to thank anonymous referees for their useful suggestions that led to substantial improvements of the original version of this paper. YX would like to thank Prof. Ming Gu for fruitful discussions about the SRRQR algorithm and Prof. Steffen Börm for his kind explanation of the new developments of 2 matrices and providing us with a kernel matrix interface for his H2Lib package.71 This work was supported jointly by NSF under awards ACI-1306573 and DMS-1521573 and Minnesota Supercomputing Institute.

Publisher Copyright:
© 2018 John Wiley & Sons, Ltd.


  • Cauchy-like matrix
  • complexity analysis
  • hierarchical rank structure
  • integral equation
  • nested basis


Dive into the research topics of 'SMASH: Structured matrix approximation by separation and hierarchy'. Together they form a unique fingerprint.

Cite this