huge memory leak: variable elimination over non-comm. algebra

[Andreas Steenpass]

computed on Murrumesh (almost idle); First computation is much faster than second with memory consumption 10 times compared to before; Second comp. takes 1:30 h, mem consumption is almost factored by 1000. Additionally, below SINGULAR says "used time: 4.14 sec". This takes actually about 10 min to determine.

First computation:

ring r = 0,(x(1),x(2),t(1),dx(1),dx(2),dt(1),u(1)),Dp; matrix C[7][7] = 0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0; matrix D[7][7] = 0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; def S = nc_algebra(C,D); setring S; basering;

characteristic : 0 number of vars : 7 block 1 : ordering Dp : names x(1) x(2) t(1) dx(1) dx(2) dt(1) u(1) block 2 : ordering C noncommutative relations: dx(1)x(1)=x(1)*dx(1)+1 dx(2)x(2)=x(2)*dx(2)+1 dt(1)t(1)=t(1)*dt(1)+1

ideal I = x(1)5*u(1)-5*x(1)4*x(2)*u(1)+10*x(1)3*x(2)2*u(1)-10*x(1)2*x(2)3*u(1)+5*x(1)*x(2)4*u(1)-x(2)5*u(1)-x(1)2*u(1)-2*x(1)*x(2)*u(1)-x(2)2*u(1)+t(1)*u(1),-5*x(1)4*dt(1)*u(1)+20*x(1)3*x(2)*dt(1)*u(1)-30*x(1)2*x(2)2*dt(1)*u(1)+20*x(1)*x(2)3*dt(1)*u(1)-5*x(2)4*dt(1)*u(1)+2*x(1)*dt(1)*u(1)+2*x(2)*dt(1)*u(1)+dx(1)*u(1),5*x(1)4*dt(1)*u(1)-20*x(1)3*x(2)*dt(1)*u(1)+30*x(1)2*x(2)2*dt(1)*u(1)-20*x(1)*x(2)3*dt(1)*u(1)+5*x(2)4*dt(1)*u(1)+2*x(1)*dt(1)*u(1)+2*x(2)*dt(1)*u(1)+dx(2)*u(1); memory(0);memory(1);memory(2);

170344 659456 659456

ideal J = eliminate(I,u(1)); J;

J[1]=0

memory(0);memory(1);memory(2);

1621176 2242496 2242496

listvar(all);

S [0] *ring J [0] ideal, 1 generator(s) I [0] ideal, 3 generator(s) r [0] ring D [0] matrix 7 x 7 C [0] matrix 7 x 7

kill S,r; listvar(all); memory(0);memory(1);memory(2);

1618856 2242496 2242496

Second computation:

timer = 1; ring r = 0,(x(1),x(2),t(1),dx(1),dx(2),dt(1),u(1)),Dp; matrix C[7][7] = 0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0; matrix D[7][7] = 0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; def S = nc_algebra(C,D); setring S; basering;

characteristic : 0 number of vars : 7 block 1 : ordering Dp : names x(1) x(2) t(1) dx(1) dx(2) dt(1) u(1) block 2 : ordering C noncommutative relations: dx(1)x(1)=x(1)*dx(1)+1 dx(2)x(2)=x(2)*dx(2)+1 dt(1)t(1)=t(1)*dt(1)+1

ideal I = x(1)5*u(1)-5*x(1)4*x(2)*u(1)+10*x(1)3*x(2)2*u(1)-10*x(1)2*x(2)3*u(1)+5*x(1)*x(2)4*u(1)-x(2)5*u(1)-x(1)2*u(1)-2*x(1)*x(2)*u(1)-x(2)2*u(1)+t(1)*u(1),-5*x(1)4*dt(1)*u(1)+20*x(1)3*x(2)*dt(1)*u(1)-30*x(1)2*x(2)2*dt(1)*u(1)+20*x(1)*x(2)3*dt(1)*u(1)-5*x(2)4*dt(1)*u(1)+2*x(1)*dt(1)*u(1)+2*x(2)*dt(1)*u(1)+dx(1)*u(1),5*x(1)4*dt(1)*u(1)-20*x(1)3*x(2)*dt(1)*u(1)+30*x(1)2*x(2)2*dt(1)*u(1)-20*x(1)*x(2)3*dt(1)*u(1)+5*x(2)4*dt(1)*u(1)+2*x(1)*dt(1)*u(1)+2*x(2)*dt(1)*u(1)+dx(2)*u(1),-x(1)*x(2)*u(1)+x(1)*x(2); ideal J = eliminate(I,u(1));

used time: 4717.84 sec

memory(0);memory(1);memory(2);

1308915904 used time: 4.14 sec 1329631232 1329631232

listvar(all);

S [0] *ring J [0] ideal, 60 generator(s) I [0] ideal, 4 generator(s) r [0] ring D [0] matrix 7 x 7 C [0] matrix 7 x 7

kill J; memory(0);memory(1);memory(2);

1307702232 1329631232 1329631232

kill S,r; listvar(all); memory(0);memory(1);memory(2);

1307699920 1329631232 1329631232

[seelisch]

SINGULAR session dumps

[steenpass]

Here is another example of a memory leak in non-commutative computations.
It is probably related to the previous one as I guess that eliminate uses std.
Thus it might be a good idea to fix this example first
and then to check whether or not the first one is also fixed.

> ring r = 0,(x(1),x(2),t(1),dx(1),dx(2),dt(1),u(1)),(a(intvec(1:7)),a(intvec(0,0,-1,0,0,1,0)),Dp);
> matrix C[7][7] = 0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0;
> matrix D[7][7] = 0,0,0,u(1)^2,0,0,0,0,0,0,0,u(1)^2,0,0,0,0,0,0,0,u(1)^2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;
> def S = nc_algebra(C,D);
> setring S;
> basering;
//   characteristic : 0
//   number of vars : 7
//        block   1 : ordering a
//                  : names    x(1) x(2) t(1) dx(1) dx(2) dt(1) u(1)
//                  : weights     1    1    1    1    1    1    1
//        block   2 : ordering a
//                  : names    x(1) x(2) t(1) dx(1) dx(2) dt(1) u(1)
//                  : weights     0    0   -1    0    0    1    0
//        block   3 : ordering Dp
//                  : names    x(1) x(2) t(1) dx(1) dx(2) dt(1) u(1)
//        block   4 : ordering C
//   noncommutative relations:
//    dx(1)x(1)=x(1)*dx(1)+u(1)^2
//    dx(2)x(2)=x(2)*dx(2)+u(1)^2
//    dt(1)t(1)=t(1)*dt(1)+u(1)^2
> poly f = 3*x(1)^3*x(2)*dt(1)+6*x(1)^2*x(2)^2*dt(1)+3*x(1)*x(2)^3*dt(1)-x(1)^2*x(2)*dx(1)*u(1)-x(1)*x(2)^2*dx(2)*u(1)-5*x(1)*x(2)*t(1)*dt(1)*u(1)-5*x(1)*x(2)*u(1)^3;
> poly g = 96*x(1)^2*x(2)*dt(1)^2*u(1)+96*x(1)*x(2)^2*dt(1)^2*u(1)+40*x(1)^2*x(2)*dx(1)^2*dt(1)+64*x(1)^2*x(2)*dx(1)*dx(2)*dt(1)+24*x(1)^2*x(2)*dx(2)^2*dt(1)+64*x(1)^2*dx(1)*dt(1)*u(1)^2+48*x(1)^2*dx(2)*dt(1)*u(1)^2+24*x(1)*x(2)^2*dx(1)^2*dt(1)+64*x(1)*x(2)^2*dx(1)*dx(2)*dt(1)+40*x(1)*x(2)^2*dx(2)^2*dt(1)+80*x(1)*x(2)*t(1)*dx(1)*dt(1)^2+80*x(1)*x(2)*t(1)*dx(2)*dt(1)^2+384*x(1)*x(2)*dx(1)*dt(1)*u(1)^2+384*x(1)*x(2)*dx(2)*dt(1)*u(1)^2+80*x(1)*t(1)*dt(1)^2*u(1)^2+304*x(1)*dt(1)*u(1)^4+48*x(2)^2*dx(1)*dt(1)*u(1)^2+64*x(2)^2*dx(2)*dt(1)*u(1)^2+80*x(2)*t(1)*dt(1)^2*u(1)^2+304*x(2)*dt(1)*u(1)^4+3*x(1)*x(2)*dx(1)^3*u(1)+9*x(1)*x(2)*dx(1)^2*dx(2)*u(1)+9*x(1)*x(2)*dx(1)*dx(2)^2*u(1)+3*x(1)*x(2)*dx(2)^3*u(1)+9*x(1)*dx(1)^2*u(1)^3+18*x(1)*dx(1)*dx(2)*u(1)^3+9*x(1)*dx(2)^2*u(1)^3+9*x(2)*dx(1)^2*u(1)^3+18*x(2)*dx(1)*dx(2)*u(1)^3+9*x(2)*dx(2)^2*u(1)^3+18*dx(1)*u(1)^5+18*dx(2)*u(1)^5;
> ideal I = f,g;
> homog(I);
1
> timer = 1;
> memory(0);memory(1);
176072
794624
> ideal J = std(I);
//used time: 30.92 sec
> kill J;
> memory(0);memory(1);
26718920
28057600
> listvar(all);
// S                    [0]  *ring
//      I                    [0]  ideal, 2 generator(s)
//      g                    [0]  poly
//      f                    [0]  poly
// r                    [0]  ring
//      D                    [0]  matrix 7 x 7
//      C                    [0]  matrix 7 x 7
> kill S,r;
> memory(0);memory(1);
26716176
28057600
> listvar(all);
> 

[hannes]

fixed: nc: nc_rKill, multiplication

[steenpass]

Due to the fix by hannes, the memory leak is MUCH smaller now, but it is still considerably big. In the first computation of the original post for example, its size is about 40 kB per {ideal J = eliminate(I, u(1)); kill J;}, thus the ticket should remain opened as discussed in the meeting.

[levandov]

The main point: this will happen with ANY routine and ANY computation involving polynomial multiplication, since some information will be stored in objects, associated to the basering. Namely, in many situations in the non-commutative case (except relations yx=c*xy for c a unit) to each pair of variables (x,y) a matrix will be associated, which (i,j)th entry is the polynomial y^{j x}i. These entries will be first killed when the ring gots killed. So if you have many multiplications, your internal multiplication tables grow in both matrix size as well as in the size on their entries.
Alex Motsak has some ideas how to enhance this greedy behaviour. We tried some of them in the summer of 2008 at RISC.

[hannes]

example 1

[hannes]

example 2

[hannes]

found two more memory leaks - memory consumption of examples b1, b2 is now stable.