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