This is related to Noah's recent question about solving quadratics in a number field, but about an even earlier and easier step.
Suppose I have a huge system of linear equations, say ~10^6 equations in ~10^4 variables, and I have some external knowledge that suggests there's a small solution space, ~100 dimensional. Moreover, the equations are sparse; in fact, the way I produce the equations gives me an upper bound on the number of variables appearing in each equation, ~10. (These numbers all come form the latest instance of our problem, but we expect to want to try even bigger things later.) Finally, all the coefficients are in some number field.
Which computer algebra system should I be using to solve such a system? Everyone knows their favourite CAS, but it's often hard to get useful comparisons. One significant difficulty here is that even writing down all the equations occupies a big fraction of a typical computer's available RAM.
I'll admit that so far I've only tried Mathematica; it's great for most of our purposes, but I'm well aware of its shortcomings, hence this question. A previous slightly smaller instance of our problem was within Mathematica's range, but now I'm having trouble.
(For background, this problem is simply finding the "low weight spaces" in a graph planar algebra. See for example Emily Peter's thesis for an explanation, or our follow-up paper, with Noah Snyder and Stephen Bigelow.)
Best Answer
It probably goes without saying that solving linear systems over number fields is probably far from the being among the most important user-level functionality of the main commercial computer algebra systems. That said, I do know that this functionality in Maple was written by someone with a specific interest in this sort of thing. If you have access to a recent version of Maple, take a look at the help page: ?SolveTools,Linear. 10^6 is pretty big, but it might still be within reach of the solver.
While, I do not know much about how Mathematica does these things, I do know that in Maple sparse linear systems are more efficiently solved as polynomials (rather than sparse-matrices) since underlying polynomial data-structure turns out to be well suited to sparse system solving.
If Maple does not work for you (or you do not have access to it), this strikes me as exactly the sort of problem that MAGMA might be targeting.