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. 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.
ALGEBRA EQUATION SYSTEMS CODE
(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.Ī 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. Conjugate gradient is an algorithm to minimize a positive-definite quadratic form. 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. If you use one of these solvers, you can then check that it is an exact solution to the original system of equations. (See the Inverse Symbolic Calculator, etc.) Some of these also exist in computer algebra systems. If you find floating point solutions to high precision, there are algorithms to convert them to elements of a number field with bounded complexity. For instance, to me it feels simpler to code conjugate gradient than to code Gaussian elimination.
It is available in certain packages and certain computer algebra systems, but it is also not very hard to implement from scratch. Even for dense matrices it is more robust than Gaussian elimination for sparse matrices it is better still. In floating point arithmetic, there is an excellent algorithm for solving a sparse system of linear equations. See for example Emily Peter's thesis for an explanation, or our follow-up paper, with Noah Snyder and Stephen Bigelow.)įor a problem of this size, you should consider which algorithm before you consider which computer algebra system. (For background, this problem is simply finding the "low weight spaces" in a graph planar algebra.
A previous slightly smaller instance of our problem was within Mathematica's range, but now I'm having trouble. 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. One significant difficulty here is that even writing down all the equations occupies a big fraction of a typical computer's available RAM. 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. (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.
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. 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. This is related to Noah's recent question about solving quadratics in a number field, but about an even earlier and easier step.
0 kommentar(er)
