I am trying to solve a bunch of homogenous polynomial equations in several variables, using Groebner basis method. I expect to get a unique rational solution.
The problem is that the coefficients of my polynomials are huge. To be precise, I have 12 homogenous equations in 12 variables of degrees <= 5 (1 linear, 1 of degree 5, and several of degrees 2, 3 and 4). The coefficients are rational numbers whose numerators have between 200-800 digits, and whose denominators have between 300-1700 digits.
The GroebnerBasis command in Magma is taking forever to finish. Questions.
- Will Magma be able to complete the process in a reasonable amount of time?
- Are there ways to expedite it?
- Any other approaches to solving the equations? assuming our expected form of the solution?
- I can produce more equations with similar sized coefficients and degrees greater than or equal to 4. Will having more equations make GrobnerBasis computation easier or harder?
Since you are only after solutions, it might be more effective to consider the system modulo various primes and then use rational reconstruction after you have enough of them. If the system is fast to solve for any given prime, then you can pick primes where the number of solutions is low (preferably 1) and so not blow up the number of cases to check.
Assuming that you can quickly solve the system modulo p, and can find many primes with only a single solution, then the idea would be to find a certain number of them, apply rational reconstruction, and check if the result is a solution. If not, use more primes until the resulting reconstructed rational is the solution you are looking for. Of course, this only terminates if there is actually a solution, but you have stipulated that there is. (If not, then one could hope to find a prime for which there are no solutions, thereby establishing this.)
If I recall correctly, good primes to use (from the point of view of Magma's speed) are those a little less than 2^15 or 2^23.