  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.
