Hiptmair–Xu preconditioner

In mathematics, Hiptmair–Xu (HX) preconditioners are preconditioners for solving $H(\operatorname {curl} )$ and $H(\operatorname {div} )$ problems based on the auxiliary space preconditioning framework. An important ingredient in the derivation of HX preconditioners in two and three dimensions is the so-called regular decomposition, which decomposes a Sobolev space function into a component of higher regularity and a scalar or vector potential. The key to the success of HX preconditioners is the discrete version of this decomposition, which is also known as HX decomposition. The discrete decomposition decomposes a discrete Sobolev space function into a discrete component of higher regularity, a discrete scale or vector potential, and a high-frequency component.

HX preconditioners have been used for accelerating a wide variety of solution techniques, thanks to their highly scalable parallel implementations, and are known as AMS and ADS precondition. HX preconditioner was identified by the U.S. Department of Energy as one of the top ten breakthroughs in computational science in recent years. Researchers from Sandia, Los Alamos, and Lawrence Livermore National Labs use this algorithm for modeling fusion with magnetohydrodynamic equations. Moreover, this approach will also be instrumental in developing optimal iterative methods in structural mechanics, electrodynamics, and modeling of complex flows.

HX preconditioner for $H(\operatorname {curl} )$

Consider the following $H(\operatorname {curl} )$ problem: Find $u\in H_{h}(\operatorname {curl} )$ such that

$(\operatorname {curl} ~u,\operatorname {curl} ~v)+\tau (u,v)=(f,v),\quad \forall v\in H_{h}(\operatorname {curl} ),$ with $\tau >0$.

The corresponding matrix form is

$A_{\operatorname {curl} }u=f.$

The HX preconditioner for $H(\operatorname {curl} )$ problem is defined as

$B_{\operatorname {curl} }=S_{\operatorname {curl} }+\Pi _{h}^{\operatorname {curl} }\,A_{vgrad}^{-1}\,(\Pi _{h}^{\operatorname {curl} })^{T}+\operatorname {grad} \,A_{\operatorname {grad} }^{-1}\,(\operatorname {grad} )^{T},$

where $S_{\operatorname {curl} }$ is a smoother (e.g., Jacobi smoother, Gauss–Seidel smoother), $\Pi _{h}^{\operatorname {curl} }$ is the canonical interpolation operator for $H_{h}(\operatorname {curl} )$ space, $A_{vgrad}$ is the matrix representation of discrete vector Laplacian defined on $[H_{h}(\operatorname {grad} )]^{n}$,$grad$ is the discrete gradient operator, and $A_{\operatorname {grad} }$ is the matrix representation of the discrete scalar Laplacian defined on $H_{h}(\operatorname {grad} )$. Based on auxiliary space preconditioning framework, one can show that

$\kappa (B_{\operatorname {curl} }A_{\operatorname {curl} })\leq C,$

where $\kappa (A)$ denotes the condition number of matrix $A$.

In practice, inverting $A_{vgrad}$ and $A_{grad}$ might be expensive, especially for large scale problems. Therefore, we can replace their inversion by spectrally equivalent approximations, $B_{vgrad}$ and $B_{\operatorname {grad} }$, respectively. And the HX preconditioner for $H(\operatorname {curl} )$ becomes $B_{\operatorname {curl} }=S_{\operatorname {curl} }+\Pi _{h}^{\operatorname {curl} }\,B_{vgrad}\,(\Pi _{h}^{\operatorname {curl} })^{T}+\operatorname {grad} B_{\operatorname {grad} }(\operatorname {grad} )^{T}.$

HX Preconditioner for $H(\operatorname {div} )$

Consider the following $H(\operatorname {div} )$ problem: Find $u\in H_{h}(\operatorname {div} )$

$(\operatorname {div} \,u,\operatorname {div} \,v)+\tau (u,v)=(f,v),\quad \forall v\in H_{h}(\operatorname {div} ),$ with $\tau >0$.

The corresponding matrix form is

$A_{\operatorname {div} }\,u=f.$

The HX preconditioner for $H(\operatorname {div} )$ problem is defined as

$B_{\operatorname {div} }=S_{\operatorname {div} }+\Pi _{h}^{\operatorname {div} }\,A_{vgrad}^{-1}\,(\Pi _{h}^{\operatorname {div} })^{T}+\operatorname {curl} \,A_{\operatorname {curl} }^{-1}\,(\operatorname {curl} )^{T},$

where $S_{\operatorname {div} }$ is a smoother (e.g., Jacobi smoother, Gauss–Seidel smoother), $\Pi _{h}^{\operatorname {div} }$ is the canonical interpolation operator for $H(\operatorname {div} )$ space, $A_{vgrad}$ is the matrix representation of discrete vector Laplacian defined on $[H_{h}(\operatorname {grad} )]^{n}$, and $\operatorname {curl}$ is the discrete curl operator.

Based on the auxiliary space preconditioning framework, one can show that

$\kappa (B_{\operatorname {div} }A_{\operatorname {div} })\leq C.$

For $A_{\operatorname {curl} }^{-1}$ in the definition of $B_{\operatorname {div} }$, we can replace it by the HX preconditioner for $H(\operatorname {curl} )$ problem, e.g., $B_{\operatorname {curl} }$, since they are spectrally equivalent. Moreover, inverting $A_{vgrad}$ might be expensive and we can replace it by a spectrally equivalent approximations $B_{vgrad}$. These leads to the following practical HX preconditioner for $H(\operatorname {div} )$ problem,

$B_{\operatorname {div} }=S_{\operatorname {div} }+\Pi _{h}^{\operatorname {div} }B_{vgrad}(\Pi _{h}^{\operatorname {div} })^{T}+\operatorname {curl} B_{\operatorname {curl} }(\operatorname {curl} )^{T}=S_{\operatorname {div} }+\Pi _{h}^{\operatorname {div} }B_{vgrad}(\Pi _{h}^{\operatorname {div} })^{T}+\operatorname {curl} S_{\operatorname {curl} }(\operatorname {curl} )^{T}+\operatorname {curl} \Pi _{h}^{\operatorname {curl} }B_{vgrad}(\Pi _{h}^{\operatorname {curl} })^{T}(\operatorname {curl} )^{T}.$

Derivation

The derivation of HX preconditioners is based on the discrete regular decompositions for $H_{h}(\operatorname {curl} )$ and $H_{h}(\operatorname {div} )$, for the completeness, let us briefly recall them.

Theorem:[Discrete regular decomposition for $H_{h}(\operatorname {curl} )$]

Let $\Omega$ be a simply connected bounded domain. For any function $v_{h}\in H_{h}(\operatorname {curl} \Omega )$, there exists a vector${\tilde {v}}_{h}\in H_{h}(\operatorname {curl} \Omega )$, $\psi _{h}\in [H_{h}(\operatorname {grad} \Omega )]^{3}$, $p_{h}\in H_{h}(\operatorname {grad} \Omega )$, such that $v_{h}={\tilde {v}}_{h}+\Pi _{h}^{\operatorname {curl} }\psi _{h}+\operatorname {grad} p_{h}$ and$\Vert h^{-1}{\tilde {v}}_{h}\Vert +\Vert \psi _{h}\Vert _{1}+\Vert p_{h}\Vert _{1}\lesssim \Vert v_{h}\Vert _{H(\operatorname {curl} )}$

Theorem:[Discrete regular decomposition for $H_{h}(\operatorname {div} )$] Let $\Omega$ be a simply connected bounded domain. For any function $v_{h}\in H_{h}(\operatorname {div} \Omega )$, there exists a vector ${\widetilde {v}}_{h}\in H_{h}(\operatorname {div} \Omega )$ , $\psi _{h}\in [H_{h}(\operatorname {grad} \Omega )]^{3},$ $w_{h}\in H_{h}(\operatorname {curl} \Omega ),$ such that $v_{h}={\widetilde {v}}_{h}+\Pi _{h}^{\operatorname {div} }\psi _{h}+\operatorname {curl} \,w_{h},$ and $\Vert h^{-1}{\widetilde {v}}_{h}\Vert +\Vert \psi _{h}\Vert _{1}+\Vert w_{h}\Vert _{1}\lesssim \Vert v_{h}\Vert _{H(\operatorname {div} )}$

Based on the above discrete regular decompositions, together with the auxiliary space preconditioning framework, we can derive the HX preconditioners for $H(\operatorname {curl} )$ and $H(\operatorname {div} )$ problems as shown before.