5

I am inverting a sparse, symmetric, ill-conditioned matrix. I have used both SVD and the LDL decomposition. I find that my results are better with the latter. Why?

I understand that LDL decomposition works only on symmetric matrices. But that doesn't necessarily say why it works better than a "more general" algorithm.

rhombidodecahedron
  • 2,322
  • 3
  • 23
  • 37
  • 2
    What do you mean that your results are "better"? – Sycorax Feb 11 '18 at 14:15
  • 1
    @Sycorax I am using these decompositions to find the least squares solution to a system of linear equations. I can generate systems with known ground truth values and see which of the two methods is more reliable in recovering them. – rhombidodecahedron Feb 11 '18 at 14:26
  • I think it is important to note here that you are having sparse matrices. In general, Cholesky should be better in terms of time-complexity. Cholesky has time-complexity of order $\frac{1}{3}O(n^3)$ instead $\frac{8}{3}O(n^3)$ which is the case with the SVD. These go a bit out of the window now that you are talking about sparse matrices because the sparsity pattern changes the rules of the game. I strongly suspect you are using CHOLMOD for the sparse Cholesky and that is a great work-horse, but the sparse SVD, maybe ARPACK, maybe straight-up MKL? (cont.) – usεr11852 Feb 11 '18 at 19:40
  • What are dimensions of the matrices involved and what percentage of the entries are non-zero? Are you explicitly setting them as sparse matrices (the obvious thing)? Do you have any reproducible examples? – usεr11852 Feb 11 '18 at 19:43
  • 3
    I think that the question could be moved to the Computational Science SE https://scicomp.stackexchange.com/ – usεr11852 Feb 11 '18 at 19:44
  • @usεr11852 Yes, I am using CHOLMOD for LDLT and LAPACK for SVM. – rhombidodecahedron Feb 12 '18 at 14:19

1 Answers1

3

There are trade-offs between computational speed, accuracy, and constraints. The Eigen library has a pretty good summary here https://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html

(And there's also a page comparing SVD and QR-decomposition for least-square solvers at https://eigen.tuxfamily.org/dox/group__LeastSquares.html )

From this second page:

"The three methods discussed on this page are the SVD decomposition, the QR decomposition and normal equations. Of these, the SVD decomposition is generally the most accurate but the slowest, normal equations is the fastest but least accurate, and the QR decomposition is in between."

Hugh Perkins
  • 4,279
  • 1
  • 23
  • 38
  • 2
    Perhaps it would be helpful to OP if you clarified the relationship between the content of your answer and OP's question comparing SVD and Cholesky factors. – Sycorax Feb 11 '18 at 19:19