next up previous
Next: About this document ...

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.




next up previous
Next: About this document ...
Copper Mountain Conference 2011-02-20