;
RadicalDecomposition(I);
Perhaps someone who reads this message in the year 2010 will enter these
commands and get their answer in minutes, but with 1998 machines this is
hopeless -- memory usage swells past the 100MB available on my machines
in minutes, and I'm sure that even if memory were available, execution
time would be in weeks, years, or lifetimes.
On the other hand, there are several tricks which may make the computation
feasible: each seems to reduce memory use or execution time or both.
1. Rather than treat the initial parameters a_i as indeterminates,
given them assigned values. (I assume them to be rational so I can perform
all calculations integrally.) "Most" choices of the a_i will lead to
varieties of the same cardinality, but of course you won't know in
advance whether or not your choices of a_i were "generic". In Magma,
the parameters are assigned simply with commands like
a1:=1;a2:=2;a3:=3;a4:=5;a5:=7;a6:=11;a7:=12;a8:=17;a9:=25;
a10:=31;a11:=197;a12:=1001;
after the declaration of the ring.
2. Rather than work over the integers, work mod p for several large primes
and then lift with the Chinese Remainder Theorem. Again, most but not all
primes will show the same size variety. In order for the lift to integers
to work, you have to know that the coefficients integrally are "small",
which is something of a gamble. The commands are, say,
p:=10000000019;
R:=GF(p);
I'm not really sure why the rational calculations take so much longer, but
that's my experience. (They don't seem to consume any more memory.)
3. Rather than study the variety in R^12, look only for the projection to
R^3 which retains only the coordinates p, q, and r. This is sufficient in
practice since these three parameters locate the lines; then from the
initial data there are at most 8 possible locations for each of the three
points; a check of the 8^3 combinations will show which ones have the correct
inter-point distances. The command is
J:=EliminationIdeal(I,9);
4. Rather than ask for the complete computation of the prime ideals, just
simplify the presentation of the ideal a bit. The command
Groebner(J);
will re-formulate the presentation of the ideal using Groebner bases which,
if lexicographic ordering has been selected, may be close enough to the
desired format to enable reading off the equations which really determine
the values of the variables. Some commands of intermediate difficulty and
value might be
Radical(J);
ProbableRadicalDecomposition(J);
Variety(J);
VarietySizeOverAlgebraicClosure(J);
5. One factor which determines the difficulty of a problem is the size of
the solution set. In this problem, there are many more solutions than is
really necessary: we have already noted there is an 8-fold symmetry in the
solution set. One way out of this is to solve only for p^2, q^2, and r^2
rather than p, q, and r. This is a little tricky since those symmetries also
change the signs of the x_i, y_i, and z_i. Since you have stated you're
not interested in what happens in degenerate cases, let me assume that
p, q, and r aren't zero. Then you can restate the problem in terms of
the variables P=p^2, Q=q^2, R=r^2, X1=x1*p, Y1=y1*q, etc. Substituting
and clearing denominators gives another 12 equations in the new variables;
this appears to be a more complicated ideal, but in fact as the solution set
is smaller, Magma seems to treat it more efficiently.
Perhaps some of the algorithmic commutative algebra people can comment
as to the comparative efficiency of the several approaches. I've still
got some machines playing with examples, so I'd be willing to experiment
with suggestions.
This run succeeded, for example:
//Magma program to help deduce locations of lines meeting given conditions
p:=10000000019;
K:=GF(p); //Now, I can't call the ring and the variable both R so let
G