Abstract

We present a new family of multigraph algorithms, based upon a graph interpretation of the hierarchical basis multigrid algorithm. The graph of the sparse matrix $A$ is recursively coarsened by eliminating vertices using a graph model similar to Gaussian elimination. Incomplete factorizations are obtained by allowing only the fillin generated by the vertex parents associated with each vertex. The restriction and interpolation operators of classical multigrid methods are replaced by the multipliers from an incomplete factorization of the matrix.