Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field? - MathOverflow

Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-10-25T20:14:03Z

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.)

Answer by Kim Greene for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-10-25T21:11:18Z

Matlab might be a better choice. Be sure to use the sparse matrix functionality rather than just regular matrices. I haven't used Matlab for this purpose but I've seen people using it for large systems.

Also, have you been using sparse matrices in Mathematica?

http://reference.wolfram.com/mathematica/howto/WorkWithSparseMatrices.html

This might improve the performance.

Answer by JP May for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-10-29T01:53:14Z

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.

Answer by Michael Hoffman for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-10-29T04:34:45Z

This sounds like a problem you'll really need to run through a strong solver in C, and if you want it to pull in objects easily it'd probably be best to use a Perl C-wrapper with MPI and Parallel LAPACK. I'll look into easily accessible sparse matrix solvers, that are modular enough to change the inputs (oy that's gonna be interesting, but I'll take a look). Honestly at numbers that high I don't see any reasonably sized computer that matlab or mathematica can deal with solving it.

Will be back with results of search soon.

Answer by Michael Hoffman for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-10-29T06:38:47Z

LinBox

May be quite helpful, as it contains routines for finite fields and has an interface to Maple (which is significantly easier to use than LinBox as a C++ library).

Hope that helps!

Answer by Jiahao Chen for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-11-10T19:08:38Z

A system that large is large enough where the speedup from skipping over all the layers of abstraction in most CAS packages is worth the trouble to write your own custom code to solve the problem.

If you are ok with a floating point solution, ScaLAPACK or another linear algebra package that has algorithms and data structures for sparse matrices would be a lot better than (P)LAPACK, which as far as I know uses only dense matrix data structures.

Python's scipy package also has sparse data structures and wrappers to call UMFPACK, and the syntax is easy enough that it wouldn't be significantly harder to use than a CAS program. It would be easier than writing a custom Fortran/C program straight up.

For solutions over the reals, there is an algorithm called the complete orthogonal decomposition (COD) that uses rank revealing QR factorization (see, e.g. Golub's Matrix Computations). This lets you separate out and project away the kernel of the problem, leaving behind only the part of the problem that lies in the range. I don't know if there is an analogue for arbitrary fields, but since you appear to have a problem with a small rank, it may be worth your trouble to look into this.

Answer by timur for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-11-20T18:32:17Z

I think here is someone who does related research:

http://www4.ncsu.edu/~kaltofen/bibliography/index.html

Answer by Greg Kuperberg for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-11-20T20:57:50Z

For a problem of this size, you should consider which algorithm before you consider which computer algebra system.

In floating point arithmetic, there is an excellent algorithm for solving a sparse system of linear equations. Even for dense matrices it is more robust than Gaussian elimination; for sparse matrices it is better still. This is the conjugate gradient method. It is available in certain packages and certain computer algebra systems, but it is also not very hard to implement from scratch. For instance, to me it feels simpler to code conjugate gradient than to code Gaussian elimination.

If you find floating point solutions to high precision, there are algorithms to convert them to elements of a number field with bounded complexity. (See the Inverse Symbolic Calculator, etc.) Some of these also exist in computer algebra systems. If you use one of these solvers, you can then check that it is an exact solution to the original system of equations.

If the solution space is low-dimensional but not 1-dimensional, then you can run conjugate gradient repeatedly after adding constraints to eliminate the kernel found so far. Conjugate gradient is an algorithm to minimize a positive-definite quadratic form. (If the system is not positive definite symmetric, you have to square or make some other change to fix that.) Thus it still works if you add constraints.

Answer by Alasdair McAndrew for Which computer algebra system should I be using to solve large systems of sparse linear equations over a number field?

2009-12-04T03:44:08Z

If Magma can do this, you may well look at Sage, which is open source, remarkably powerful, and with support for sparse linear algebra.