Hiptmair–Xu preconditioner explained

In mathematics, Hiptmair–Xu (HX) preconditioners^[1] are preconditioners for solving

H(\operatorname{curl})

and

H(\operatorname{div})

problems based on the auxiliary space preconditioning framework.^[2] 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^[3] and ADS^[4] precondition. HX preconditioner was identified by the U.S. Department of Energy as one of the top ten breakthroughs in computational science^[5] in recent years. Researchers from Sandia, Los Alamos, and Lawrence Livermore National Labs use this algorithm for modeling fusion with magnetohydrodynamic equations.^[6] 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\inH_{h(\operatorname{curl})}

such that

(\operatorname{curl}~u,\operatorname{curl}~v)+\tau(u,v)=(f,v), \forallv\inH_{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_ + \Pi_h^ \, A_^ \, (\Pi_h^)^T + \operatorname \, A_^ \, (\operatorname)^T,

where

S_{\operatorname{curl}

} is a smoother (e.g., Jacobi smoother, Gauss–Seidel smoother),

	\operatorname{curl
\Pi
	h

} is the canonical interpolation operator for

H_{h(\operatorname{curl})}

space,

A_vgrad

is the matrix representation of discrete vector Laplacian defined on

	n
[H
	h(\operatorname{grad})]

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_) \leq C,

where

\kappa(A)

denotes the condition number of matrix

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_ + \Pi_h^ \, B_ \, (\Pi_h^)^T + \operatorname B_ (\operatorname)^T.

HX Preconditioner for

H(\operatorname{div})

Consider the following

H(\operatorname{div})

problem: Find

u\inH_{h(\operatorname{div})}

(\operatorname{div}u,\operatorname{div}v)+\tau(u,v)=(f,v), \forallv\inH_{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_ + \Pi_h^ \, A_^ \, (\Pi_h^)^T + \operatorname \, A_^ \, (\operatorname)^T,

where

S_{\operatorname{div}

} is a smoother (e.g., Jacobi smoother, Gauss–Seidel smoother),

	\operatorname{div
\Pi
	h

} is the canonical interpolation operator for

H(\operatorname{div})

space,

A_vgrad

is the matrix representation of discrete vector Laplacian defined on

	n
[H
	h(\operatorname{grad})]

, and

\operatorname{curl}

is the discrete curl operator.

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

\kappa(B_{\operatorname{div}

} A_) \leq C.

For

A_{\operatorname{curl}

}^ 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_ + \Pi_h^ B_ (\Pi_h^)^T + \operatorname B_ (\operatorname)^T = S_ + \Pi_h^ B_ (\Pi_h^)^T + \operatorname S_ (\operatorname)^T + \operatorname \Pi_h^ B_ (\Pi_h^)^T (\operatorname)^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 <math>H_h(\operatorname{curl})</math>]

Let

\Omega

be a simply connected bounded domain. For any function

v_h\inH_{h(\operatorname{curl}}\Omega)

, there exists a vector

\tilde{v}_h\inH_{h(\operatorname{curl}}\Omega)

\psi_h\in[H_h(\operatorname{grad}\Omega)]³

p_h\inH_{h(\operatorname{grad}}\Omega)

, such that

v_h=\tilde{v}_h+\Pi

	\operatorname{curl

	h

}\psi_+ \operatorname p_h and

\Verth^-1\tilde{v}_h\Vert+\Vert\psi_h\Vert₁+\Vertp_h\Vert₁\lesssim\Vertv_h\Vert_{H(\operatorname{curl})}

Theorem:[Discrete regular decomposition for <math>H_{h}(\operatorname{div})</math>]Let

\Omega

be a simply connected bounded domain. For any function

v_h\inH_h(\operatorname{div}\Omega)

, there exists a vector

\widetilde{v}_h\inH_{h(\operatorname{div}}\Omega)

\psi_h\in[H_{h(\operatorname{grad}}\Omega)]³,

w_h\inH_{h(\operatorname{curl}}\Omega),

such that

v_h=\widetilde{v}_h+\Pi

	\operatorname{div

	h

}\psi_h+ \operatorname \, w_h, and

\Verth^-1\widetilde{v}_h\Vert+\Vert\psi_h\Vert₁+\Vertw_h\Vert₁\lesssim\Vertv_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.

Notes and References

Hiptmair . Ralf . Xu . Jinchao . 2007-01-01 . spaces . 2020-07-06 . SIAM J. Numer. Anal. . . 2483 . 10.1137/060660588.
J.Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids. Computing. 1996;56(3):215–35.
T. V. Kolev, P. S. Vassilevski, Parallel auxiliary space AMG for H (curl) problems. Journal of Computational Mathematics. 2009 Sep 1:604–23.
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.
Report of The Panel on Recent Significant Advancements in Computational Science, https://science.osti.gov/-/media/ascr/pdf/program-documents/docs/Breakthroughs_2008.pdf
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.