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.
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.
The exact solution of linear equations with rational coefficients belongs to the field of computer algebra. For an entry to the literature, see
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.