Improved sweeping preconditioners for domain decomposition algorithms applied to time-harmonic Helmholtz and Maxwell problems★★★

Abstract

Sweeping-type algorithms have recently gained a lot of interest for the solution of highfrequency time-harmonic wave problems, in particular when used in combination with perfectly matched layers. However, an inherent problem with sweeping approaches is the sequential nature of the process, which makes them inadequate for efficient implementation on parallel computers. We propose several improvements to the double-sweep preconditioner originally presented in [18], which uses sweeping as a matrix-free preconditioner for a Schwarz domain decomposition method. Similarly, the improved preconditioners are based on approximations of the inverse of the Schwarz iteration operator: the general methodology is to apply well-known algebraic techniques to the operator seen as a matrix, which in turn is processed to obtain equivalent matrix-free routines that we use as preconditioners. A notable feature of the new variants is the introduction of partial sweeps that can be performed concurrently in order to make a better usage of the resources. As these modifications still leave some unexploited computational power, we also propose to combine them with right-hand side pipelining to further improve parallelism and achieve significant speed-ups. Examples are presented on high-frequency Helmholtz and Maxwell problems, in two and three dimensions, to demonstrate the properties of our improvements on parallel computer architectures.