Re: [eigen] Instability in LLT and LDLT methods.

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]


On Tue, 27 Jan 2009, Keir Mierle wrote:

Probably it's better to do full pivoting. Apparently cholesky is
stable for semidefinite matrices when full pivoting is used:

http://eprints.ma.man.ac.uk/1101/01/covered/MIMS_ep2008_56.pdf

Cholesky (LL^T) is stable without any pivoting for positive definite matrices. So I think the possibility of Cholesky without pivoting should remain.

On Wed, 28 Jan 2009, Gael Guennebaud wrote:

yes, it seems the test to check whether the matrix is positive
definite was too strict. I changed the absolute tolerance a bit, but
we still need something better. Basically, in Cholesky we compute at
each iteration 1/sqrt(x), and so x must be >0 with some epsilon...

Why do you need an epsilon? Perhaps a better question is, why does the routine test whether the matrix is positive definite? As you say, it's not easy to write such a test, and it could be said that it's the user's responsibility that the matrix is positive definite - though of course a test is nice when the code is run in debug mode.

A related issue I've been wondering about is: why does LU decomposition use complete pivoting? I believe that's quite a bit more expensive than partial pivoting, though I didn't run any tests. When solving a linear system with an invertible matrix, partial pivoting performs as well as complete pivoting, doesn't it? LAPACK uses partial pivoting, as does GSL.

Cheers,
Jitse



Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/