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

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

1 Answer
1

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

This is a bit long for a comment.

You can use a tandem of LinearSolve and NullSpace. But for exact problems this will, I’m fairly sure, use dense matrices. That takes you back to what Solve is doing anyway, under the hood.

Assuming your inputs are integer or rationals you might avoid dense matrix algebra as follows. Use numerical methods to find a single solution via LinearSolve, now working on a sparse matrix. This also assumes (1) the matrix actually is sparse) and (2) you can later do numeric refinement to get an exact solution. You will also need to do something similar to get exact null vectors. A good reference for this approach is Z. Wan. “An algorithm to solve integer linear systems exactly using numerical methods”. Journal of Symbolic Computation 41:621-632, 2006.