1
$\begingroup$

What is the best known algorithm for exactly solving a large sparse system of linear equations? The system I'm working on is not symmetric, not positive definite and integer. The only benefit is being sparse. I also need to point out that the matrix is not square. The dimension is m×n and it is not generally either underestimate or overestimate.

$\endgroup$
9
  • $\begingroup$ possible duplicate of What guidelines should I follow when choosing a sparse linear system solver? $\endgroup$ – J. M. Jul 12 '12 at 9:54
  • $\begingroup$ In which sense do you want to solve your system? How large are your m and n? $\endgroup$ – Arnold Neumaier Jul 12 '12 at 10:41
  • $\begingroup$ I want to solve this system exactly. m and n can be very large i.e., more than $10^5$. $\endgroup$ – Star Jul 12 '12 at 11:39
  • $\begingroup$ exactly = rounding-error free? Are the matrix entries rational? You must be prepared to get answers with very big fractions, or do you have additional information that forbids this? - Also if $m>n$ there will be generally no solution while for $m<n$ there will be infinitely many. Is this really what you want? $\endgroup$ – Arnold Neumaier Jul 12 '12 at 12:29
  • $\begingroup$ By exact, I mean rounding-error free. My matrix has rational entries as well. Also, $m \leq n$. $\endgroup$ – Star Jul 12 '12 at 12:45
1
$\begingroup$

The exact solution of linear equations with rational coefficients belongs to the field of computer algebra. For an entry to the literature, see
http://www2.isye.gatech.edu/~dsteffy/papers/OSLifting.pdf
http://www2.isye.gatech.edu/~dsteffy/papers/rationalsolver.pdf
http://www.eecis.udel.edu/~youse/post/itersolve.pdf
http://www.lirmm.fr/~giorgi/issac06.pdf
You can do a literature search based on this and the citation facilities of http://scholar.google.com .

$\endgroup$
1
  • $\begingroup$ $@$ Arnold: You are above a gentleman.Thanks a lot Arnold. $\endgroup$ – Star Jul 12 '12 at 17:11
0
$\begingroup$

Krylov Iterative methods are a usual choice.

If you happen to have access to Mathematica, it offers a good way to test for different method: if A is your matrix, write B=SparseArray[A]; Then use the LinearSolve function with Method->"Krylov". You can also test to see if there are advantages to retaining integer digits. Converting to real numbers may yield faster results, possibly at the cost of accuracy.

$\endgroup$
1
  • 1
    $\begingroup$ This is an iterative, approximate method. It won't give exact solutions. $\endgroup$ – David Ketcheson Jul 12 '12 at 14:01

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