1
$\begingroup$

CHOLMOD is very fast, but I am just wondering what kinds of size A such that it can solve Ax=b. I have a A of 200,000 * 200,000, but it outputs errors" problem too large". I am very appreciated if anyone can tell me which solver/software for numerical computing can solve such large size problem. Thanks!

$\endgroup$
2
  • $\begingroup$ How many nonzero elements are there in the matrix? $\endgroup$
    – Victor Liu
    Jun 22 '13 at 17:04
  • $\begingroup$ @Victor Liu: No. of nonzero elements are 5594648.. $\endgroup$
    – Hao Yu
    Jun 23 '13 at 14:30
1
$\begingroup$

The storage required by a sparse matrix depends (roughly linearly) on the number of nonzero elements in the matrix. When you then attempt to compute a Cholesky factorization (or more generally an LU factorization) of your sparse matrix, the factors typically have substantially more nonzero elements than the original matrix had- this is referred to as "fill-in."

The amount of fill-in that occurs will depend on the number and placement of the nonzeros in the original matrix. In many cases you can reduce fill-in by carefully ordering the rows/columns of your matrix before factoring it. There are many algorithms for reducing the fill-in, but computing an optimal ordering is an NP-hard problem, so in practice these algorithms use heuristic approaches to get a good fill-in reducing ordering.

It appears that CHOLMOD couldn't factor your matrix because there wasn't sufficient storage available to handle the fill-in that occurred during the factorization process. Did you reorder the rows/columns of your matrix before factoring it to reduce fill-in? If not, then using a good ordering might be enough to make this problem solvable within the memory that you have available.

Can you try to solve your problem on a computer with more memory?

$\endgroup$
2
  • 1
    $\begingroup$ If solving the system by sparse factorization techniques isn't going to work because you don't have enough memory, then you could also consider using an iterative method to solve your system of equations. There won't be any fill-in with an iterative method, but getting reasonably fast convergence typically requires a good preconditioning strategy for the system of equations. $\endgroup$ Jun 22 '13 at 20:20
  • 1
    $\begingroup$ cholmod by default uses a fill-reducing ordering (AMD or METIS) unless you disable it, see the docs $\endgroup$
    – Stefano M
    Jun 22 '13 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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