Opened 14 years ago

Closed 13 years ago

#214 closed bug (fixed)

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

Reported by: Andreas Steenpass Owned by: hannes
Priority: minor Milestone: 3-1-1
Component: memory leak Version: 3-1-1
Keywords: nc eliminate Cc: Oleksandr

Description

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

Attachments (3)

bugReport.txt (4.0 KB) - added by seelisch 14 years ago.
SINGULAR session dumps
b1 (1008 bytes) - added by hannes 13 years ago.
example 1
b2 (1.0 KB) - added by hannes 13 years ago.
example 2

Download all attachments as: .zip

Change History (8)

Changed 14 years ago by seelisch

Attachment: bugReport.txt added

SINGULAR session dumps

comment:1 Changed 14 years ago by 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);
> 

comment:2 Changed 14 years ago by hannes

Resolution: fixed
Status: newclosed

fixed: nc: nc_rKill, multiplication

comment:3 Changed 14 years ago by steenpass

Component: singular-kernelmemory leak
Priority: majorminor
Resolution: fixed
Status: closedreopened

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.

comment:4 Changed 14 years ago by levandov

Cc: Oleksandr added

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 yj xi. 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.

Changed 13 years ago by hannes

Attachment: b1 added

example 1

Changed 13 years ago by hannes

Attachment: b2 added

example 2

comment:5 Changed 13 years ago by hannes

Resolution: fixed
Status: reopenedclosed

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

Note: See TracTickets for help on using tickets.