# How smart is Solve? Figuring out what tricks I should try

I’m trying to solve a large system (~10000) of linear equations using Solve, but the process keeps failing. As-is, I don’t know whether it’s failing because it’s using too much memory or too much time (I’m running it via a batch scheduler, and the scheduler’s output is ambiguous). Either way, I’d like to find a better way to solve the problem. I’ve got a few ideas, the problem is I don’t know how many of them are things that Solve already does.

Some examples:

Sort the equations so that the ones involving fewer variables come
first, so mathematica can substitute them in to the longer ones and
hopefully have an easier time with that.
Use Reduce instead (is Reduce faster or slower for this kind of task? Does it use more or less memory?)
Try to search for equations that are proportional to eachother and eliminate them.
Use RowReduce instead, then solve the resulting equations. (Possibly after sorting things.)

Is there a point in trying any of these, or are they all things Solve does faster by itself? Are there any other tricks I should be considering?

To preempt some possible responses:

I can’t use LinearSolve because I need the full space of solutions, and I know that most of the variables will not be uniquely fixed.
I can’t do this numerically for the same reason, I need an exact solution.

Edit: A bit more information: I can now confirm that the problem is running out of memory, not time. Also, a collaborator of mine who uses Maple can apparently solve this sort of thing in about 10mins. While it’s plausible this is just something Maple is better at, I suspect this means that Mathematica is trying to do something unnecessarily complicated here, and that there is either a setting that turns the “extra” stuff off or another, stripped-down function that can handle it. It’s not like Maple could just be better at this, after all. ;P

=================

Any chance you could partition this into Sqrt[n] sub-problems, solve each, where solve may or may not be Solve[], union those results and turn that into something that could then be solved?
– Bill
Sep 22 ’14 at 15:55

Absent a concrete example, I cannot speculate beyond the remark that the memory overrun is probably in an attempt at dense row reduction.
– Daniel Lichtblau
Sep 22 ’14 at 21:47

=================