Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
In which sense do you want to solve your system? How large are your m and n? – Arnold Neumaier Jul 12 '12 at 10:41
I want to solve this system exactly. m and n can be very large i.e., more than $10^5$. – Star Jul 12 '12 at 11:39
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? – Arnold Neumaier Jul 12 '12 at 12:29
By exact, I mean rounding-error free. My matrix has rational entries as well. Also, $m \leq n$. – Star Jul 12 '12 at 12:45
show 4 more comments

closed as not a real question by J. M., Geoff Oxberry♦ Jul 13 '12 at 0:59

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

2 Answers

up vote 1 down vote

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 .

share|improve this answer
$@$ Arnold: You are above a gentleman.Thanks a lot Arnold. – Star Jul 12 '12 at 17:11
up vote 0 down vote

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.

share|improve this answer
1  
This is an iterative, approximate method. It won't give exact solutions. – David Ketcheson Jul 12 '12 at 14:01

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