Misplaced Pages

In mathematics, Hiptmair–Xu (HX) preconditioners are preconditioners for solving ${\displaystyle H(\operatorname {curl} )}$ and ${\displaystyle 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 ${\displaystyle H(\operatorname {curl} )}$

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

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

The corresponding matrix form is

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

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

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

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

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

In practice, inverting ${\displaystyle A_{vgrad}}$ and ${\displaystyle A_{grad}}$ might be expensive, especially for large scale problems. Therefore, we can replace their inversion by spectrally equivalent approximations, ${\displaystyle B_{vgrad}}$ and ${\displaystyle B_{\operatorname {grad} }}$, respectively. And the HX preconditioner for ${\displaystyle H(\operatorname {curl} )}$ becomes ${\displaystyle 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 ${\displaystyle H(\operatorname {div} )}$

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

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

The corresponding matrix form is

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

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

${\displaystyle 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 ${\displaystyle S_{\operatorname {div} }}$ is a smoother (e.g., Jacobi smoother, Gauss–Seidel smoother), ${\displaystyle \Pi _{h}^{\operatorname {div} }}$ is the canonical interpolation operator for ${\displaystyle H(\operatorname {div} )}$ space, ${\displaystyle A_{vgrad}}$ is the matrix representation of discrete vector Laplacian defined on ${\displaystyle ^{n}}$, and ${\displaystyle \operatorname {curl} }$ is the discrete curl operator.

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

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

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

${\displaystyle 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 ${\displaystyle H_{h}(\operatorname {curl} )}$ and ${\displaystyle H_{h}(\operatorname {div} )}$, for the completeness, let us briefly recall them.

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

Let ${\displaystyle \Omega }$ be a simply connected bounded domain. For any function ${\displaystyle v_{h}\in H_{h}(\operatorname {curl} \Omega )}$, there exists a vector${\displaystyle {\tilde {v}}_{h}\in H_{h}(\operatorname {curl} \Omega )}$, ${\displaystyle \psi _{h}\in ^{3}}$, ${\displaystyle p_{h}\in H_{h}(\operatorname {grad} \Omega )}$, such that ${\displaystyle v_{h}={\tilde {v}}_{h}+\Pi _{h}^{\operatorname {curl} }\psi _{h}+\operatorname {grad} p_{h}}$ and${\displaystyle \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 ${\displaystyle H_{h}(\operatorname {div} )}$] Let ${\displaystyle \Omega }$ be a simply connected bounded domain. For any function ${\displaystyle v_{h}\in H_{h}(\operatorname {div} \Omega )}$, there exists a vector ${\displaystyle {\widetilde {v}}_{h}\in H_{h}(\operatorname {div} \Omega )}$ , ${\displaystyle \psi _{h}\in ^{3},}$ ${\displaystyle w_{h}\in H_{h}(\operatorname {curl} \Omega ),}$ such that ${\displaystyle v_{h}={\widetilde {v}}_{h}+\Pi _{h}^{\operatorname {div} }\psi _{h}+\operatorname {curl} \,w_{h},}$ and ${\displaystyle \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 ${\displaystyle H(\operatorname {curl} )}$ and ${\displaystyle H(\operatorname {div} )}$ problems as shown before.

References

1. Hiptmair, Ralf; Xu, Jinchao (2007-01-01). "{Nodal auxiliary space preconditioning in $backslash$bf H($backslash$bf curl) and $backslash$bf H($backslash$rm div)} spaces". SIAM J. Numer. Anal. ResearchGate: 2483. doi:10.1137/060660588. Retrieved 2020-07-06.
2. J.Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids. Computing. 1996;56(3):215–35.
3. T. V. Kolev, P. S. Vassilevski, Parallel auxiliary space AMG for H (curl) problems. Journal of Computational Mathematics. 2009 Sep 1:604–23.
4. T.V. Kolev, P.S. Vassilevski. Parallel auxiliary space AMG solver for H(div) problems. SIAM Journal on Scientific Computing. 2012;34(6):A3079–98.
5. Report of The Panel on Recent Significant Advancements in Computational Science, https://science.osti.gov/-/media/ascr/pdf/program-documents/docs/Breakthroughs_2008.pdf
6. E.G. Phillips, J. N. Shadid, E.C. Cyr, S.T. Miller, Enabling Scalable Multifluid Plasma Simulations Through Block Preconditioning. In: van Brummelen H., Corsini A., Perotto S., Rozza G. (eds) Numerical Methods for Flows. Lecture Notes in Computational Science and Engineering, vol 132. Springer, Cham 2020.

• Polynomials