# 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<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

## 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