Abstract

Solving linear systems of equations efficiently continues to be a major task in scientific computing. In recent decades multigrid and AMG algorithms have been the methods of choice for many mathematical systems. In an even broader sense multilevel algorithms can be applied to a variety of problems including document and protein clustering.

Hierarchical matrices (H-matrices) approximate matrices in a data-sparse way. The storage and computational complexity of approximate arithmetic for H-matrices are almost optimal. For example, the complexity of computing the approximate inverse of an H-matrix is O(n^2\log{n}). H-matrices provide an alternative way to solve linear systems arising from partial differential equations.

An H-matrix is usually represented by a tree structure which shows the hierarchical block partitioning of its corresponding matrix. To build an H-matrix corresponding to a sparse matrix M, we developed a scheme based on multilevelmethods.