Hi there, Recently I have been talking with Alex about a weird inefficency of GiNaC's expand() that showed up in some series expansion. It reappeared, this time in a clearer form, when I tried to implement an asymptotically optimal algorithm for computing characteristic polynomials (by transforming the matrix to an upper block-Frobenius form, but that's uninteresting here). That algorithm gives the characteristic polynomial in a partly factorized form and when I expand it I see horrible execution times or even worse, memory exhaustions. Consider this:
expand((-1+5*x-5*x^4-10*x^2+x^5+10*x^3)*(1-4*x+x^4+6*x^2-4*x^3)* (-1+7*x-35*x^4-21*x^2+21*x^5-7*x^6+35*x^3+x^7)* (1-8*x+70*x^4+28*x^2+x^8-56*x^5+28*x^6-56*x^3-8*x^7)* (1-6*x+15*x^4+15*x^2-6*x^5+x^6-20*x^3)*(-1+x)^36* (-1+9*x+x^9-126*x^4-36*x^2-9*x^8+126*x^5-84*x^6+84*x^3+36*x^7)^2* (1-2*x+x^2)); Out of virtual memory.
expand((-1+5*x-5*x^4-10*x^2+x^5+10*x^3)*(1-4*x+x^4+6*x^2-4*x^3)* (-1+7*x-35*x^4-21*x^2+21*x^5-7*x^6+35*x^3+x^7)* (1-8*x+70*x^4+28*x^2+x^8-56*x^5+28*x^6-56*x^3-8*x^7)* (1-6*x+15*x^4+15*x^2-6*x^5+x^6-20*x^3)*(-1+x)^36* (-1+9*x+x^9-126*x^4-36*x^2-9*x^8+126*x^5-84*x^6+84*x^3+36*x^7)^2* (1-2*x+x^2)*(-75810815066186520+75810815066186521*x+165*x^9-165*x^4-11*x^2-330* x^8+11*x^11+330*x^5-55*x^10-462*x^6+55*x^3-x^12+462*x^7)*(-1+3*x-3*x^2+x^3)); bad_alloc
Virtual memory was 1GB. (BTW: The second polynomial is identical to the one computed in expanded form in check/time_lw_P.cpp.) Alex, would you be able to have a look into this? Cheers -richy. -- Richard Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
On Mon, 18 Sep 2000, I wrote:
Consider this:
expand((-1+5*x-5*x^4-10*x^2+x^5+10*x^3)*(1-4*x+x^4+6*x^2-4*x^3)* (-1+7*x-35*x^4-21*x^2+21*x^5-7*x^6+35*x^3+x^7)* (1-8*x+70*x^4+28*x^2+x^8-56*x^5+28*x^6-56*x^3-8*x^7)* (1-6*x+15*x^4+15*x^2-6*x^5+x^6-20*x^3)*(-1+x)^36* (-1+9*x+x^9-126*x^4-36*x^2-9*x^8+126*x^5-84*x^6+84*x^3+36*x^7)^2* (1-2*x+x^2)); Out of virtual memory.
Hint: expanding the mul object successively step by step makes it fly. Is it really a good idea to expand all children first and then do some gymnastics with them? Or am I missing some point? (It just comes into my mind that the issue is also of interest for some algorithms in class matrix. It throws some new light on a number of empirically inserted additional .expand()s which turned out to be absolutely necessary to be efficient. I guess I can remove all these once this is resolved.) Cheers -richy. -- Richard Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
a=1/(1-x-x^2); (1-x-x^2)^(-1) b=series(a,x==0,3); 1+1*x+2*x^2+Order(x^3) b/2; 1/2*1+1*x+2*x^2+Order(x^3) ^^^^^^ I checked and find out it's not the print() problem so maybe it comes from
Hi all, I'm now back with Xloops project and this is my "hello" to you :-): in ginsh type the expand()? Hope not to have to say "hello" every day :-) Cheers, Son.
On Fri, 22 Sep 2000, Do Hoang Son wrote:
a=1/(1-x-x^2); (1-x-x^2)^(-1) b=series(a,x==0,3); 1+1*x+2*x^2+Order(x^3) b/2; 1/2*1+1*x+2*x^2+Order(x^3) ^^^^^^ I checked and find out it's not the print() problem so maybe it comes from the expand()?
Of course it is a pseries::print() problem! There were two mistakes: 1) It didn't check precedence against upper_precedence (blame me) and 2) pseries was inheriting it's precedence from basic (blame christian). I have committed the patches to CVS. Cheers -richy. -- Richard Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
participants (2)
-
Do Hoang Son
-
Richard B. Kreckel