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/>