Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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$?

share|improve this question

migrated from mathoverflow.net Jul 16 at 15:11

This question came from our site for professional mathematicians.

    
Thanks, I flagged my question for migration. –  user2863620 Jul 16 at 15:00

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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