5
$\begingroup$

Given symmetric, positive-definite matrix $A$ and its preconditioner $M^{-1}$. What's kind of preconditioner $M^{-1}$ which preserve the symmetry of $M^{-1}A$?

$\endgroup$
8
$\begingroup$

Often $M^{-1}A$ is not symmetric, even if $M$ and $A$ are. There are two common approaches to dealing with this:

  1. Find a Cholesky factorization of $M$ into $LL^\top$, and instead solve for $L^{-1}AL^{-\top}$. If you're using an incomplete Cholesky factorization preconditioner, this involves no extra work. For other preconditioners, this might be impractical.
  2. Exploit the fact that $M^{-1}A$ is a symmetric linear operator with respect to the inner product

    $ \langle x, y\rangle_M = x^*My$.

    Apply the conjugate gradient method to $M^{-1}A$ with this new inner product. With a bit of book-keeping, you can guarantee that, in each CG iteration, you only compute one matrix multiplication with $A$ and one with $M^{-1}$.

From what I've seen, (2) is the more commonly used approach. Moreover, they're all equivalent in the end anyway, so there's no particular advantage to one or the other besides ease of implementation. For more details, see Saad's book.

$\endgroup$
6
$\begingroup$

Not a real answer probably: typically for positive-definite matrices the problem is avoided by switching to two-side preconditioning: one looks for $M=LL^T$ that approximates the spectrum of $A$ and then uses an iterative method to solve the linear system $L^{-1}AL^{-T}y=L^{-1}b$, with $y=L^{T}x$. See for instance the wikipedia page for preconditioned CG.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.