<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Jul 18, 2014 at 1:19 PM, Chetan Jhurani <span dir="ltr"><<a href="mailto:chetan.jhurani@gmail.com" target="_blank">chetan.jhurani@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">> From: Jed Brown <<a href="mailto:jed@jedbrown.org">jed@jedbrown.org</a>><br>
><br>
> Jozsef Bakosi <<a href="mailto:jbakosi@lanl.gov">jbakosi@lanl.gov</a>> writes:<br>
><br>
> > Hi folks,<br>
> ><br>
> > I have a matrix as a result of a finite element discretization of the Poisson<br>
> > operator and associated right hand side. As it turns out, the matrix is<br>
> > symmetric but not positive definite since it has at least two negative small<br>
> > eigenvalues. I have been solving this system without problem using the conjugate<br>
> > gradients (CG) algorithm with ML as a preconditioner, but I'm wondering why it<br>
> > works.<br>
><br>
> Is the preconditioned matrix<br>
><br>
>   P^{-1/2} A P^{-T/2}<br>
><br>
> positive definite?<br>
<br>
This does not answer the original question regarding CG/ML, but<br></blockquote><div><br></div><div>It is possible for CG to convergence with an indefinite matrix, but it is also</div><div>possible for it to fail.</div><div>
<br></div><div>  Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
will reduce some debugging work.  P^{-1/2} A P^{-T/2} cannot be<br>
positive definite since A is not positive definite.  This is due<br>
to Sylvester's inertia theorem.<br>
<br>
<a href="http://books.google.com/books?id=P3bPAgAAQBAJ&pg=PA202" target="_blank">http://books.google.com/books?id=P3bPAgAAQBAJ&pg=PA202</a><br>
Applied Numerical Linear Algebra By James W. Demmel, p 202<br>
<br>
Chetan<br>
<br>
> > Shouldn't CG fail for a non-positive-definite matrix? Does PETSc do some<br>
> > additional magic if it detects that the dot-product in the CG algorithm is<br>
> > negative? Does it solve the system using the normal equations, A'A, instead?<br>
><br>
> CG will report divergence in case a direction of negative curvature is<br>
> found.<br>
<br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
-- Norbert Wiener
</div></div>