Demo of F4.
Roman Pearce, November 2005.
restart;
currentdir("/home/rpearce/f5talk"):
Please set the above directory to where the files below are stored.
kernelopts(opaquemodules=false):
read "PolynomialIdeals.f4": read rowsort: read maintest:
bind(PolynomialIdeals:-GroebnerBasis):
PolynomialIdeals test suite
---------------------------
butcher caprasse cassou circles cyclic5 cyclic6
cyclohexane des18_3 des22_24 discriminant4 eco7
hairer1 katsura5 katsura6 kinema noon4 pavelle
rabmo reimer4 reimer5 rose S4 S6 schwarz7 schwarz8
sendra tangents trinks utbikker vermeer wang92c
wang92e weispfenning94 wright
cyclic6;
LUkwUE9MWU5PTUlBTElERUFMRzYiNissLkkieEdGJCIiIkkieUdGJEYoSSJ6R0YkRihJInRHRiRGKEkidUdGJEYoSSJ2R0YkRigsLiomRidGKEYpRihGKComRilGKEYqRihGKComRipGKEYrRihGKComRitGKEYsRihGKComRixGKEYtRihGKComRidGKEYtRihGKCwuKihGJ0YoRilGKEYqRihGKCooRilGKEYqRihGK0YoRigqKEYqRihGK0YoRixGKEYoKihGK0YoRixGKEYtRihGKCooRixGKEYtRihGJ0YoRigqKEYtRihGJ0YoRilGKEYoLC4qKkYnRihGKUYoRipGKEYrRihGKCoqRilGKEYqRihGK0YoRixGKEYoKipGKkYoRitGKEYsRihGLUYoRigqKkYrRihGLEYoRi1GKEYnRihGKCoqRixGKEYtRihGJ0YoRilGKEYoKipGLUYoRidGKEYpRihGKkYoRigsJiouRidGKEYpRihGKkYoRitGKEYsRihGLUYoRihGKCEiIiwuKixGJ0YoRilGKEYqRihGK0YoRixGKEYoKixGKUYoRipGKEYrRihGLEYoRi1GKEYoKixGKkYoRitGKEYsRihGLUYoRidGKEYoKixGK0YoRixGKEYtRihGJ0YoRilGKEYoKixGLEYoRi1GKEYnRihGKUYoRipGKEYoKixGLUYoRidGKEYpRihGKkYoRitGKEYoL0kqdmFyaWFibGVzR0YkPChGLUYrRidGKkYsRikvSS9jaGFyYWN0ZXJpc3RpY0dGJCIiIS9JNWtub3duX2dyb2VibmVyX2Jhc2VzR0YkPUYkSSZmYWxzZUclKnByb3RlY3RlZEdFXFtsIQ==
GroebnerBasis(cyclic6,'tord',method=f4): # uses row-reductions
-> F4 algorithm
basis: 6 degree: 4 pairs: 1 of 6
matrix 8 x 36
new pivots 1
basis: 7 degree: 5 pairs: 4 of 5
matrix 34 x 78
new pivots 3
basis: 10 degree: 6 pairs: 8 of 8
matrix 52 x 102
new pivots 6
Warning, computation interrupted
A := rowsort(PolynomialIdeals:-XLA:-A); # double click and look at "structure"
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEiQUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIzo9RicvJSVmb3JtR1EmaW5maXhGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGPi8lJ2xzcGFjZUdRL3RoaWNrbWF0aHNwYWNlRicvJSdyc3BhY2VHRkMvJSlzdHJldGNoeUdGPi8lKnN5bW1ldHJpY0dGPi8lKG1heHNpemVHUSlpbmZpbml0eUYnLyUobWluc2l6ZUdRIjFGJy8lKGxhcmdlb3BHRj4vJS5tb3ZhYmxlbGltaXRzR0Y+LyUnYWNjZW50R0Y+LUkobWFjdGlvbkdGJDYkLUkobWZlbmNlZEdGJDYlLUknbXRhYmxlR0YkNiYtSSRtdHJHRiQ2Iy1JJG10ZEdGJDYjLUYjNiQtRiw2JVErfjUyfnh+MTAyfkYnRi9GMi1GLDYlUSdNYXRyaXhGJ0YvRjItRmpuNiMtRl1vNiMtRiM2JC1GLDYlUSxEYXRhflR5cGU6fkYnRi9GMi1GLDYlUSlhbnl0aGluZ0YnRi9GMi1Gam42Iy1GXW82Iy1GIzYkLUYsNiVRKlN0b3JhZ2U6fkYnRi9GMi1GLDYlUSxyZWN0YW5ndWxhckYnRi9GMi1Gam42Iy1GXW82Iy1GIzYkLUYsNiVRKE9yZGVyOn5GJ0YvRjItRiw2JVEuRm9ydHJhbl9vcmRlckYnRi9GMi8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJy8lK2FjdGlvbnR5cGVHUS1icm93c2VydGFibGVGJw==
GroebnerBasis(schwarz9,'tord',method=f4): # a bigger system
-> F4 algorithm
basis: 9 degree: 3 pairs: 15 of 15
matrix 85 x 210
new pivots 15
basis: 24 degree: 4 pairs: 63 of 70
matrix 345 x 545
new pivots 22
Warning, computation interrupted
A := rowsort(PolynomialIdeals:-XLA:-A);
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEiQUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi9RIzo9RicvJSVmb3JtR1EmaW5maXhGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGPi8lJ2xzcGFjZUdRL3RoaWNrbWF0aHNwYWNlRicvJSdyc3BhY2VHRkMvJSlzdHJldGNoeUdGPi8lKnN5bW1ldHJpY0dGPi8lKG1heHNpemVHUSlpbmZpbml0eUYnLyUobWluc2l6ZUdRIjFGJy8lKGxhcmdlb3BHRj4vJS5tb3ZhYmxlbGltaXRzR0Y+LyUnYWNjZW50R0Y+LUkobWFjdGlvbkdGJDYkLUkobWZlbmNlZEdGJDYlLUknbXRhYmxlR0YkNiYtSSRtdHJHRiQ2Iy1JJG10ZEdGJDYjLUYjNiQtRiw2JVEsfjM0NX54fjU0NX5GJ0YvRjItRiw2JVEnTWF0cml4RidGL0YyLUZqbjYjLUZdbzYjLUYjNiQtRiw2JVEsRGF0YX5UeXBlOn5GJ0YvRjItRiw2JVEpYW55dGhpbmdGJ0YvRjItRmpuNiMtRl1vNiMtRiM2JC1GLDYlUSpTdG9yYWdlOn5GJ0YvRjItRiw2JVEscmVjdGFuZ3VsYXJGJ0YvRjItRmpuNiMtRl1vNiMtRiM2JC1GLDYlUShPcmRlcjp+RidGL0YyLUYsNiVRLkZvcnRyYW5fb3JkZXJGJ0YvRjIvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRicvJSthY3Rpb250eXBlR1EtYnJvd3NlcnRhYmxlRic=
P := pivots(A):
S := sort([op({op(P)})], `<`):
At := LinearAlgebra:-Transpose(A):
A1 := Matrix([seq(convert(At[i,1..-1], list), i=S)]):
A1; # Transpose(A) * Nullspace(A1) -> new polynomials
LUkobWFjdGlvbkc2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkobWZlbmNlZEdGJDYlLUknbXRhYmxlR0YkNiYtSSRtdHJHRiQ2Iy1JJG10ZEdGJDYjLUklbXJvd0dGJDYkLUkjbWlHRiQ2JVEsfjI3MH54fjM0NX5GJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictRjs2JVEnTWF0cml4RidGPkZBLUYyNiMtRjU2Iy1GODYkLUY7NiVRLERhdGF+VHlwZTp+RidGPkZBLUY7NiVRKWFueXRoaW5nRidGPkZBLUYyNiMtRjU2Iy1GODYkLUY7NiVRKlN0b3JhZ2U6fkYnRj5GQS1GOzYlUSxyZWN0YW5ndWxhckYnRj5GQS1GMjYjLUY1NiMtRjg2JC1GOzYlUShPcmRlcjp+RidGPkZBLUY7NiVRLkZvcnRyYW5fb3JkZXJGJ0Y+RkEvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRicvJSthY3Rpb250eXBlR1EtYnJvd3NlcnRhYmxlRic=
# nullspace computation -> linear system A x = B
# row reduce mod a prime
p := prevprime(2^25): dtype := float[8]:
Ap := LinearAlgebra:-Modular:-Mod(p,A1,dtype):
LinearAlgebra:-Modular:-RowReduce(p,Ap,op(1,Ap),op(1,Ap)[2],0$5,false):
P1 := pivots(Ap): # put dependent columns in B
A2 := Matrix([seq([seq(A1[i,j], j=P1)], i=1..op(1,A1)[1])]):
NP1 := remove(member, [$1..op(1,A1)[2]], P1):
B2 := Matrix([seq([seq(A1[i,j], j=NP1)], i=1..op(1,A1)[1])]):
# solve the following system: use p-adic lifting
A2, B2;
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkobWFjdGlvbkdGJDYkLUkobWZlbmNlZEdGJDYlLUknbXRhYmxlR0YkNiYtSSRtdHJHRiQ2Iy1JJG10ZEdGJDYjLUYjNiQtSSNtaUdGJDYlUSx+Mjcwfnh+MjcwfkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GPTYlUSdNYXRyaXhGJ0ZARkMtRjU2Iy1GODYjLUYjNiQtRj02JVEsRGF0YX5UeXBlOn5GJ0ZARkMtRj02JVEpYW55dGhpbmdGJ0ZARkMtRjU2Iy1GODYjLUYjNiQtRj02JVEqU3RvcmFnZTp+RidGQEZDLUY9NiVRLHJlY3Rhbmd1bGFyRidGQEZDLUY1NiMtRjg2Iy1GIzYkLUY9NiVRKE9yZGVyOn5GJ0ZARkMtRj02JVEuRm9ydHJhbl9vcmRlckYnRkBGQy8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJy8lK2FjdGlvbnR5cGVHUS1icm93c2VydGFibGVGJy1JI21vR0YkNi9RIixGJy8lJWZvcm1HUSZpbmZpeEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZCLyUnbHNwYWNlR1EkMGVtRicvJSdyc3BhY2VHUTN2ZXJ5dGhpY2ttYXRoc3BhY2VGJy8lKXN0cmV0Y2h5R0ZpcC8lKnN5bW1ldHJpY0dGaXAvJShtYXhzaXplR1EpaW5maW5pdHlGJy8lKG1pbnNpemVHUSIxRicvJShsYXJnZW9wR0ZpcC8lLm1vdmFibGVsaW1pdHNHRmlwLyUnYWNjZW50R0ZpcC1GLDYkLUYvNiUtRjI2Ji1GNTYjLUY4NiMtRiM2JC1GPTYlUSt+Mjcwfnh+NzV+RidGQEZDRkZGSUZVRltvRmdvRmpvRl1w
# solution produces elements of nullspace -> new polynomials
# some of those polynomials may be zero however
# -> more wasted effort versus just row-reduction