0
$\begingroup$

I am making a code in C that requires the equivalent of Matlab's '\' command for a linear system of the form AX=B where A is an NxN matrix and X, B are Nx1 vectors- i.e a code that performs X=A\B that is optimized to recognize it will be receiving a symmetric positive-definite sparse matrix. I was wondering if there is any open source code in C to do this operation.

$\endgroup$
  • 3
    $\begingroup$ CHOLMOD from SuiteSparse (faculty.cse.tamu.edu/davis/suitesparse.html) will solve systems of this type, is written in C, and is open source. $\endgroup$ – Bill Greene Jul 22 '16 at 17:09
  • 1
    $\begingroup$ Which, incidentally, is exactly what Matlab is using if backslash detects an spd matrix... $\endgroup$ – Christian Clason Jul 22 '16 at 17:24
  • $\begingroup$ precisely what I was looking for! Works perfect thank you. $\endgroup$ – user20973 Jul 22 '16 at 17:34
1
$\begingroup$

CHOLMOD is definitely the go-to for if you want a direct solver. It's what MATLAB and Julia use for solving A\b with a positive-definite sparse matrix, and likely many others.

However, you may not want to use a direct solver for large sparse matrices. Since direct solvers are $\mathcal{O}(n^3)$, they tend to not do very well as the problem grows in size. Instead, people use iterative methods to iterative get solutions $Ax_n \approx b$ where the solution $x_n \rightarrow x$ as the number of iterations $n \rightarrow \infty$.

For example, since your matrix is positive definite, conjugate-gradient methods are well suited for the problem. There are tons of implementations like this one if you don't want a whole library. But then there are multigrid methods and all kinds of other things. There is a whole CSSE question devoted to picking the right method. If you want a library that would make it easy to swap around to different solvers and see which one is fastest, try PetsC (I linked the page which shows all of the solvers). If you're going to put some time into it and performance really matters, I would definitely go with PetsC.

$\endgroup$

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.