Sparse Approximate Inverse Smoother for Multigrid

Wei-Pai Tang

Department of Computer Science University of Waterloo, Waterloo, Ontario Canada, N2L 3G1

Wing-Lok Wan

Department of Mathematics University of California, Los Angeles Los Angeles, CA 90095-1555


We propose and analyze sparse approximate inverses as smoothers for multigrid methods. The sparse approximate inverse preconditioners are inherently parallel and have been shown to be effective for a wide variety of matrices. But for matrices arising from differential equations, they may not be as efficient as methods like multigrid. Parallelization of multigrid methods, however, is still an open issue. Among other things, there is a lack of effective parallel smoothers. Our idea is to combine the advantage of the two techniques and obtain a parallel and effective iterative method. We show theoretically and numerically that sparse approximate inverses are effective as smoothers for multigrid. A preliminary numerical comparison with standard relaxation smoothers are presented.