[petsc-users] Symmetric non-positive definite system

[Chetan Jhurani]

> From: Jed Brown <jed at jedbrown.org>
> 
> Jozsef Bakosi <jbakosi at lanl.gov> writes:
> 
> > Hi folks,
> >
> > I have a matrix as a result of a finite element discretization of the Poisson
> > operator and associated right hand side. As it turns out, the matrix is
> > symmetric but not positive definite since it has at least two negative small
> > eigenvalues. I have been solving this system without problem using the conjugate
> > gradients (CG) algorithm with ML as a preconditioner, but I'm wondering why it
> > works.
> 
> Is the preconditioned matrix
> 
>   P^{-1/2} A P^{-T/2}
> 
> positive definite?

This does not answer the original question regarding CG/ML, but
will reduce some debugging work.  P^{-1/2} A P^{-T/2} cannot be
positive definite since A is not positive definite.  This is due
to Sylvester's inertia theorem.

http://books.google.com/books?id=P3bPAgAAQBAJ&pg=PA202
Applied Numerical Linear Algebra By James W. Demmel, p 202

Chetan

> > Shouldn't CG fail for a non-positive-definite matrix? Does PETSc do some
> > additional magic if it detects that the dot-product in the CG algorithm is
> > negative? Does it solve the system using the normal equations, A'A, instead?
> 
> CG will report divergence in case a direction of negative curvature is
> found.