Frequency domain behavior of a set of parallel multigrid smoothing operators

Abstract

A set of alternative smoothing operators to the usual relaxation methods for multigrid algorithms is presented and analyzed in terms of frequency domain behavior. The operations presented are inherently parallel and fit well onto hypercube multiprocessors: they can be readily calculated and applied in a parallel manner. We start by interpreting multigrid smoothers as approximate inverses. In particular, a least squares approximate inverse obtained by solving a Frobenius matrix norm minimization problem proves effective. This approximate inverse also has a least squares interpretation in the frequency domain for the special case of circulant operators, or in the case of local mode Fourier analysis for the discrete operator in the central part of the domain over which the discretization is performed. Experimental results are presented for one and two dimensional problems. Convergence rates as determined by direct iteration are compared with local mode Fourier analysis results.

Keywords:

• Approximate inverse
• multigrid
• frequency
• smoothing

^∗ This work was supprted in part by the Natural Sciences and Engineering Reserch Council of Canada through grant A5031.

^∗ This work was supprted in part by the Natural Sciences and Engineering Reserch Council of Canada through grant A5031.

Notes

^∗ This work was supprted in part by the Natural Sciences and Engineering Reserch Council of Canada through grant A5031.