# Sparse non-square system of linear equations in exact arithmetic [closed]

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.

-
 possible duplicate of What guidelines should I follow when choosing a sparse linear system solver? – J. M. Jul 12 '12 at 9:54 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 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 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 . - $@\$ Arnold: You are above a gentleman.Thanks a lot Arnold. – Star Jul 12 '12 at 17:11

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.

-
This is an iterative, approximate method. It won't give exact solutions. – David Ketcheson Jul 12 '12 at 14:01