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.