Multi-Layer Hierarchical Structures (CSIAM Transactions on Applied Mathematics, 2021)
In structured matrix computations, existing rank structures such as hierarchically semiseparable (HSS) forms admit fast and stable factorizations. However, fordiscretized problems, such forms are restricted to 1D cases. In this work, we proposea framework to break such a 1D barrier. We study the feasibility of designing multi-layer hierarchically semiseparable (MHS) structures for the approximation of densematrices arising from multi-dimensional discretized problems such as certain integraloperators. 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 foundationsand justify the existence of MHS structures based on the fast multipole method (FMM)and algebraic techniques such as representative subset selection. Rigorous numericalrank bounds and conditions for the structures are given. Representative subsets ofpoints and a multi-layer tree are used to intuitively illustrate the structures. The MHSframework makes it convenient to explore multidimensional FMM structures. MHSrepresentations are suitable for stable direct factorizations and can take advantage ofexisting methods and analysis well developed for simple HSS methods. Numericaltests for some discretized operators show that the appropriate inner-layer numericalranks are significantly smaller than the off-diagonal numerical ranks used in standardHSS approximations.