The incomplete factorization multigraph algorithm

We present a new family of multigraph algorithms, ILU-MG, based upon an incomplete sparse matrix factorization using a particular ordering and allowing a limited amount of fill-in. While much of the motivation for multigraph comes from multigrid ideas, ILU-MG is distinctly different from algebraic multilevel methods. 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 fill-in generated by the vertex parents associated with each vertex. Multigraph is numerically compared with algebraic multigrid on some examples arising from discretizations of partial differential equations on unstructured grids.