Bill Allombert on Sun, 08 Aug 2010 01:38:37 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: nfinit() is eager for memory |
On Sat, Aug 07, 2010 at 05:53:53PM -0400, Max Alekseyev wrote: > >> Is that expected? Does nfinit() indeed needs that much memory? > > > > Independently of the algorithm used, nfinit output (amon other things) the > > multiplication table which is a NxNxN tensor where N is the degree of the polynomial. > > Here N = 45360, so it has 93*10^12 entries. This will not fit in memory. > > Is there a way to overcome this? > My goal is to compute > nffactor(x^3+x^2-16440*x+80375,nfinit(polcyclo(49321,y))) > that is, to express roots of x^3+x^2-16440*x+80375 in terms of > trigonometric functions (by later substituting y=exp(2*Pi*I/49321)). This is a known computation so there is a better way to do it: ? B=bnfinit(y); ? R=rnfconductor(B,x^3+x^2-16440*x+80375) %2 = [[Mat(49321), [0]], [22680, [1260, 6, 3], [34059, 26752, [-10111]~]], [1, 0, 0; 0, 3, 1; 0, 0, 1]] This tells you that x^3+x^2-16440*x+80375 defines an abelian extension of Q of conductor 49321 and congruence subgroup [1, 0, 0; 0, 3, 1; 0, 0, 1] over [22680, [1260, 6, 3], [34059, 26752, -10111]]. Now compute the associated Gauss sums: (This is a bit cumbersome since they have 7560 cosine terms each). a=Mod(34059,49321);b=Mod(26752,49321);c=Mod(-10111,49321); S1=sum(i=1,1260,sum(j=1,2,sum(k=1,3,2*cos(2*lift(a^i*b^(3*j+k)*c^k)*Pi/49321)))) S2=sum(i=1,1260,sum(j=1,2,sum(k=1,3,2*cos(2*lift(a^i*b^(3*j+k+1)*c^k)*Pi/49321)))) S3=sum(i=1,1260,sum(j=1,2,sum(k=1,3,2*cos(2*lift(a^i*b^(3*j+k+2)*c^k)*Pi/49321)))) PARI will compute the minimal polynomial of theses Gauss sums (using essentially the above formulae) with: ? galoissubcyclo([22680, [1260, 6, 3], [a, b, c]], R[3]) %7 = x^3 + x^2 - 16440*x + 80375 Since %65 is the polynomial you are looking for, you are done. Else you would need to factor your polynomial over the field given by this one (of degree 3 instead of 45360). So S1,S2,S3 are the three roots of x^3+x^2-16440*x+80375 expressed as sums of cosine, as you can check numerically. Cheers, Bill.