[GiNaC-devel] [PATCH] {add, power}::eval(): convert terms into primitive polynomials when possible.

[Sheplyakov Alexei]

On Sat, Aug 11, 2007 at 11:11:57PM +0200, Richard B. Kreckel wrote:

> It is not some overhead that worries me. Rather, it is the algorithmic 
> complexity of the new overhead. The new transformation appears to 
> introduce quadratic behavior at the eval() level.

[snipped]

> >>Looking at the code it appears to me like mul::eval recurses now. 
> >
> >mul::eval calls evalchildren, so it is recursive even without my patch.
> 
> 
> Well, but that recurses into *children* only! At the end of the loop 
> that you introduced into mul::eval(), a new mul object is returned. It 
> is not evaluated yet and enters mul::eval() again. And it might contain 
> most of the original terms. This is an entirely different quantity of 
> recursion that is responsible for potentially quadratic behavior, IINM.

mul::eval() *is quadratic* even without my patch:

ex mul::eval(int level) const
{
	std::auto_ptr<epvector> evaled_seqp = evalchildren(level);
	if (evaled_seqp.get()) {
		// do more evaluation later
		return (new mul(evaled_seqp, overall_coeff))->
		           setflag(status_flags::dynallocated);
	}

If evaluation of children gives something non-trivial, a new mul object
is returned. It is not evaluated and enters mul::eval() again.
	
> That's bad.

My patch increases the coefficient. And that is indeed awful.

> One of the points of choosing the algorithms that are done at the eval()
> stage to be only subquadratic algorithms was that otherwise one might be
> unable to merely construct the ex object.

I think this requirement is way too strict. I'd say anything of polynomial
complexity (with "reasonable" coefficients) is OK.

 
> >>Wouldn't it be faster to collect the coefficients in one sweep? 
> >
> >I've tried this (see the patch [1]), it has almost no effect.
> 
> 
> It still appears to be quadratic.  Must it really be quadratic?

Yes. After numeric coefficients are collected, some re-evaluation is
necessary. For example,

(3*x+3*y)*(x+y) -> (3*(x+y)*(x+y)).eval() -> 3*(x+y)^2

1/9*(9*x+9*y)*(x+y)^2 -> ((x+y)*(x+y)^2).eval() -> (x+y)^3
(N.B.: the result is not mul object)


> >>Well, I recognize that most terms will be trivial in the following
> >>recursions, but still.
> >
> >My patch causes overhead even in the trivial case, e.g. when the
> >polynomial is already unit normal. Consider e.g. 
> >
> >e = (x+1)*(2*x^2+x+1)*...*(100*x^100+99*x^99+...+1);
> 
> 
> Indeed. This expression is well suited to study the asymptotic behavior:
> 
> $ { echo -n "time((1+x)"; for i in $(seq 2 100); do echo -n "*(1+x"; for 
> j in $(seq 2 $i); do echo -n "+${j}*x^${j}"; done; echo -n ")"; done; 
> echo ");";} | ginsh-1.3.5
> 0.089994s

To make the test a little bit more interesting, let's take more than 2 points:

{ echo "plot '-' using 1:2 with lines title 'mul::eval() asymptotic behaviour'"
echo
for N in `seq 100 100 2000`; do
TIME=$({ echo -n "time((1+x)"
         for i in $(seq 2 $N); do
				    echo -n "*(1+x"
				    for j in $(seq 2 $i); do 
						    echo -n "+${j}*x^${j}" 
						done
						echo -n ")" 
				 done
				 echo ");" ; } | ginsh | sed -e 's/s//g')
echo "$N $TIME" 
done
echo "e" ; } | gnuplot -persist '-'

This gives a beautiful parabola (both with my patch or without it).
Coefficients are different, but both versions of mul::eval() are
quadratic.

Best regards,
 Alexei

-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20070812/55d822ac/attachment.pgp