6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ What do you mean that your results are "better"? $\endgroup$
    – Sycorax ♦
    Feb 11, 2018 at 14:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – rhombidodecahedron
    Feb 11, 2018 at 14:26
  • $\begingroup$ 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.) $\endgroup$
    – usεr11852
    Feb 11, 2018 at 19:40
  • $\begingroup$ 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? $\endgroup$
    – usεr11852
    Feb 11, 2018 at 19:43
  • 3
    $\begingroup$ I think that the question could be moved to the Computational Science SE scicomp.stackexchange.com $\endgroup$
    – usεr11852
    Feb 11, 2018 at 19:44

1 Answer 1

Reset to default
4
$\begingroup$

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."

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Sycorax ♦
    Feb 11, 2018 at 19:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.