LAPACK Archives

[Lapack] LDL decomposition in SYTRF


Hi Eric,

Yes SYTRF is much slower than POTRF and this is to be expected.

SYTRF performs an LDLT factorization with pivoting while POTRF performs a 
Cholesky factorization.

SYTRF is for symmetric indefinite matrices (so the need to pivot), while POTRF 
is for positive definite matrices.

The cost of both algorithms is N^3/3 FLOPS. So in term of FLOPS both algorithms 
have the same cost.

Now in term of performance, the pivoting in LDLT is just killing performance.

This is actually a research problem. (How to do better than SYTRF for symmetric 
indefinite matrices.)

You are correct that PORTF perform some square roots but there are only N of 
them, and so are totally negligible with respect to the N^3 / 3 FLOPS. Even if 
a square root is slightly more expensive than a FLOP, these square roots are 
totally negligible in term of time as soon as N is in the 10s.

Also nowadays taking a square root is not that bad and is really fast anyhow. 
It was true, a while back ago, that taking  a square root was expensive and 
algorithms were designed to avoid them.

I am not sure we really try to avoid them these days. Square roots are pretty 
fast these days.

Are there any other routines that expose an LDL decomposition that is 
essentially the same as the Cholesky decomposition but without the square 
roots? Or is POTRF my best bet for solving positive-definite symmetric systems?

Yes you could devise a Cholesky-like factorization without square roots. (Yes a 
LDL without pivoting as you mention would do the job.)
This would be as fast as Cholesky. This would not have any square roots. I 
doubt the time improvement of the square root free Cholesky with respect to the 
square root Cholesky will be of any significance.

So, finally if you have a symmetric positive definite matrix, I think this is a 
no brainer.
The algorithm is Cholesky. The square roots are just fine.

Cheers,
Julien.



On Feb 14, 2014, at 3:24 PM, Eric Hunsberger 
<erichuns@Domain.Removed<mailto:erichuns@Domain.Removed>> wrote:

Hi again,

Please disregard the numbers in my previous email; I had LWORK set too small. 
Fixing that, the algorithms are closer, but SYTRF is still slower by about 1.5 
times.

Best,
Eric


On 14 February 2014 16:47, Eric Hunsberger 
<erichuns@Domain.Removed<mailto:erichuns@Domain.Removed>> wrote:
Hi LAPACK team,

I was recently playing around with the SYTRF group of routines, which from what 
I can tell perform the LDL decomposition. I was thinking these routines should 
be faster than the Cholesky decomposition (in POTRF), because as far as I know 
the decompositions are essentially the same except that the LDL decomposition 
avoids taking square roots (and does some pivoting, which I wasn't expecting).

However, what I've found is that SYTRF is much slower than POTRF, on my machine 
about 20 times slower for a 5000 by 5000 float64 matrix. Is this to be 
expected? I realize that SYTRF is more general, in that it does not require 
inputs to be positive definite, but I had still hoped it would be faster than 
POTRF, and certainly not so much slower.

Are there any other routines that expose an LDL decomposition that is 
essentially the same as the Cholesky decomposition but without the square 
roots? Or is POTRF my best bet for solving positive-definite symmetric systems?

Regards,
Eric Hunsberger

_______________________________________________
Lapack mailing list
Lapack@Domain.Removed<mailto:Lapack@Domain.Removed>
http://lists.eecs.utk.edu/mailman/listinfo/lapack

-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
<http://lists.eecs.utk.edu/mailman/private/lapack/attachments/20140219/0d39c08b/attachment.html>

<Prev in Thread] Current Thread [Next in Thread>


For additional information you may use the LAPACK/ScaLAPACK Forum.
Or one of the mailing lists, or