Jump to content

Hiptmair–Xu preconditioner

From Wikipedia, the free encyclopedia

In mathematics, Hiptmair–Xu (HX) preconditioners[1] are preconditioners for solving and 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

[edit]

Consider the following problem: Find such that

with .

The corresponding matrix form is

The HX preconditioner for problem is defined as

where is a smoother (e.g., Jacobi smoother, Gauss–Seidel smoother), is the canonical interpolation operator for space, is the matrix representation of discrete vector Laplacian defined on , is the discrete gradient operator, and is the matrix representation of the discrete scalar Laplacian defined on . Based on auxiliary space preconditioning framework, one can show that

where denotes the condition number of matrix .

In practice, inverting and might be expensive, especially for large scale problems. Therefore, we can replace their inversion by spectrally equivalent approximations, and , respectively. And the HX preconditioner for becomes

HX Preconditioner for

[edit]

Consider the following problem: Find

with .

The corresponding matrix form is

The HX preconditioner for problem is defined as

where is a smoother (e.g., Jacobi smoother, Gauss–Seidel smoother), is the canonical interpolation operator for space, is the matrix representation of discrete vector Laplacian defined on , and is the discrete curl operator.

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

For in the definition of , we can replace it by the HX preconditioner for problem, e.g., , since they are spectrally equivalent. Moreover, inverting might be expensive and we can replace it by a spectrally equivalent approximations . These leads to the following practical HX preconditioner for problem,

Derivation

[edit]

The derivation of HX preconditioners is based on the discrete regular decompositions for and , for the completeness, let us briefly recall them.

Theorem:[Discrete regular decomposition for ]

Let be a simply connected bounded domain. For any function , there exists a vector, , , such that and

Theorem:[Discrete regular decomposition for ] Let be a simply connected bounded domain. For any function , there exists a vector , such that and

Based on the above discrete regular decompositions, together with the auxiliary space preconditioning framework, we can derive the HX preconditioners for and problems as shown before.

References

[edit]
  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.