Parallel superconvergent multigrid

We describe a class of multiscale algorithms for the solution of large sparse linear systems that are particularly well adapted to massively parallel supercomputers. While standard multigrid algorithms are unable to effectively use all processors when computing on coarse grids, the new algorithms utilize the same number of processors at all times. The basic idea is to solve many coarse scale problems simultaneously, combining the results in an optimal way to provide an improved fine scale solution. As a result, convergence rates are much faster than for standard multigrid methods - we have obtained V-cycle convergence rates as good as .0046 with one smoothing application per cycle, and .0013 with two smoothings. On massively parallel machines the improved convergence rate is attained at no extra computational cost since processors that would otherwise be sitting idle are utilized to provide the better convergence. On serial machines the algorithm is slower because of the extra time spent on multiple coarse scales, though in certain cases the improved convergence rate may justify this - particularly in cases where other methods do not converge. In constant coefficient situations the algorithm is easily analyzed theoretically using Fourier methods on a single grid. The fact that only one grid is involved substantially simplifies convergence proofs. A feature of the algorithms is the use of a matched pair of operators: an approximate inverse for smoothing and a superinterpolation operator to move the correction from coarse to fine scales, chosen to optimize the rate of convergence.