Sparse Cholesky of Gram Matrix (SuiteSparse?)

[guille]

@Oscar_Smith

Note that the backsolves are only O(n^2) compared to the factoring which is O(n^3) , so 2 backsolves of a QR matrix shouldn’t be a problem.

Yup, this is why I cache the factorization On the other hand, a backsolve is still very expensive in an inner loop of an algorithm, which is what I’m currently worried about! (I mentioned this above, but these matrices are ~ 10^7\times 10^7, with roughly 10^8 nnz).

@stevengj

(Using Cholesky factors also requires one backsolve and one forward solve, which is equivalent to two backsolves, no?) It might well be be that Cholesky factorization itself is faster than QR factorization for your sparse matrix, of course.

Absolutely; my main worry is that solving the problem using the QR factorization requires a multiplication by Q and a backsolve (both done twice, once for each problem, in the inner loop). But I don’t know the performance of sparse QR vs. sparse Cholesky for these kinds of large, sparse, structured matrices, so I guess it’s worth a comparison! I’ll report results once I have them

Thanks for the help!