FAST MATRIX ALGORITHMS FOR HIERARCHICALLY SEMI-SEPARABLE REPRESENTATIONS

摘要

The hierarchically semi-separable representation for arbitrary matrices is presented, and fast backward stable direct solvers for such representations are constructed. This technique generalizes earlier work by Rokhlin and his co-workers on certain kinds of fast integral equation solvers. This work can also be viewed as a generalization of the work of Dewilde and his co-workers in time-varying systems theory. The method has the further advantage of reproducing optimal complexities independently of the number of underlying spatial dimensions. In particular the method will reproduce the optimal complexity for solving many sparse matrices by direct factorization.