Fast Tensor Product Schwarz Smoothers for High-Order Discontinuous Galerkin Methods

We discuss the efficient implementation of powerful domain decomposition smoothers for multigrid methods for high-order discontinuous Galerkin (DG) finite element methods. In particular, we study the inversion of matrices associated to mesh cells and to the patches around a vertex, respectively, in order to obtain fast local solvers for additive and multiplicative subspace correction methods. The effort of inverting local matrices for tensor product polynomials of degree k is reduced from <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi mathvariant="script">𝒪</m:mi> <m:mo>⁢</m:mo> <m:mrow> <m:mo stretchy="false">(</m:mo> <m:msup> <m:mi>k</m:mi> <m:mrow> <m:mn>3</m:mn> <m:mo>⁢</m:mo> <m:mi>d</m:mi> </m:mrow> </m:msup> <m:mo stretchy="false">)</m:mo> </m:mrow> </m:mrow> </m:math> {O(k³ᵈ)} to <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi mathvariant="script">𝒪</m:mi> <m:mo>⁢</m:mo> <m:mrow> <m:mo stretchy="false">(</m:mo> <m:mrow> <m:mi>d</m:mi> <m:mo>⁢</m:mo> <m:msup> <m:mi>k</m:mi> <m:mrow> <m:mi>d</m:mi> <m:mo>+</m:mo> <m:mn>1</m:mn> </m:mrow> </m:msup> </m:mrow> <m:mo stretchy="false">)</m:mo> </m:mrow> </m:mrow> </m:math> {O(dkᵈ⁺¹)} by exploiting the separability of the differential operator and resulting low rank representation of its inverse as a prototype for more general low rank representations in space dimension d .