the expand() thing.

[Richard B. Kreckel]

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 at Uni-Mainz.DE>
<http://wwwthep.physik.uni-mainz.de/~kreckel/>