Normalized Convergence Rates for the PSMG Method

In a previous paper we have introduced an efficient multiscale PDE solver for massively parallel architectures, which called Parallel Superconvergent Multigrid, or PSMG. In this paper we derive sharp estimates for the normalized work involved in PSMG solution - the number of parallel arithmetic and communication operations required per digit of error reduction. PSMG is shown to provide fourth-order accurate solutions of Poisson type equations at convergence rates of .00165 per single relaxation iteration, and with parallel operation counts per grid level of 5.75 communications and 8.62 computations for each digit of error reduction. We show that PSMG requires less than half as many arithmetic and one fifth as many communication operations, per digit of error reduction, as a parallel standard multigrid algorithm RBTRB presented recently by N. Decker.