Andrew Knyazev
Multigrid absolute value preconditioning

University of Colorado Denver
Campus Box 170
PO Box 173364
Denver
CO 80217-3364
Andrew.Knyazev@ucdenver.edu
Eugene Vecharynski

For a given matrix $A$, its polar decomposition is $A=U\vert A\vert$, where $\vert A\vert=\sqrt{A^*A}$ and $U$ is unitary. Let $A$ be real symmetric and nonsingular, than the matrix absolute value $\vert A\vert$ is also nonsingular and $U$ is the matrix sign of $A$, having only two distinct eigenvalues, plus and minus one. The matrix $T=\vert A\vert^{-1}$ is the ideal symmetric positive definite preconditioner for the linear system $Ax=b$, making the preconditioned MINRES to converge in at most two steps. We call $T$ the absolute value preconditioner, if it is spectrally equivalent to $\vert A\vert^{-1}$.

If the matrix $A$ is (block) strictly diagonally dominant, the preconditioner $T$ can be chosen as the inverse to the absolute value of the (block) diagonal of $A$. Such a choice can, e.g., be efficient in plain-wave electronic structure calculations.

For a model problem, where $A$ is a finite difference approximation of the shifted negative Laplacian, we construct an efficient geometric multigrid absolute value preconditioner, in which the smoothing is done using the action of $A$ and $\vert A\vert^{-1}$ appears only on the coarsest grid. Our numerical tests demonstrate the effectiveness of such a preconditioning.