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 > 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 > 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 http://lists.eecs.utk.edu/mailman/listinfo/lapack -------------- next part -------------- An HTML attachment was scrubbed... URL: ```
 Current Thread [Lapack] LDL decomposition in SYTRF, Eric Hunsberger [Lapack] LDL decomposition in SYTRF, Eric Hunsberger [Lapack] LDL decomposition in SYTRF, Langou, Julien <=

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