Sparse approximate inverse smoother for multigrid

Abstract. Various forms of sparse approximate inverses (SAI) have been shown to be useful for preconditioning. Their potential usefulness in a parallel environment has motivated much interest in recent years. However, the capability of an approximate inverse in eliminating the local error has not yet been fully exploited in multigrid algorithms. A careful examination of the iteration matrices of these approximate inverses indicates their superiority in smoothing the high-frequency error in addition to their inherent parallelism. We propose a new class of SAI smoothers in this paper and present their analytic smoothing factors for constant coefficient PDEs. The following are several distinctive features that make this technique special: • By adjusting the quality of the approximate inverse, the smoothing factor can be improved accordingly. For hard problems, this is useful. • In contrast to the ordering sensitivity of other smoothing techniques, this technique is ordering independent. • In general, the sequential performance of many superior parallel algorithms is not very competitive. This technique is useful in both parallel and sequential computations. Our theoretical and numerical results have demonstrated the effectiveness of this new technique