polynomial arithmetic over ginac

[Richard B. Kreckel]

Hi Bernard,

On Fri, 11 Aug 2000, Parisse Bernard wrote:
> I have now a little bit improved the package of my polynomial and 
> rational fractions utilities over GiNaC (0.6.4)
> It provides now gcd normalization, factor (square-free and rational
> roots), 
> partfrac & integrate (assuming factor works on the denominator), 
> for example:
> integrate '1/(x^4-1)^5'
> returns
> -1155/8192*log(1+x)-1155/4096*atan(x)+1155/8192*log(-1+x)+1/2048*(-893*x-1375*x^9+1755*x^5+385*x^13)*(-1+x^4)^(-4)
> # Time for (integrate)0.04

Thanks for your contribution.  We are quite interested in this.  Just a
remark: you know about Victor Shoup's library NTL that does highly
efficient factorization for univariate polynomials?  It was recently
relicensed under GPL and thus it is possible to merge code with GiNaC.
It is available from <http://www.shoup.net/ntl/>. 

Your integrate is impressive but it depends on factor() to work on the
denominator.  This is IMHO not very satisfactory until factor is
guaranteed to always work efficiently. (BTW: over what field?  I hope no
algebraic extensions are needed?)  Are you familiar with Horowitz'
Algorithm for integrating rational functions [1]?  AFAICT it reduces
the whole integration to linear algebra.  This looks much more attractive
to me since all the facilities needed should already be present in GiNaC.

Regards
    -richy.

[1] Ellis Horowitz: Algorithms for Partial Fraction Decomposition and
    Rational Function Integration.  Proc. 2nd Symposium on Symbolic and
    Algebraic Manipulation, ACM Inc, 1971, pp. 441-457.
-- 
Richard B. Kreckel
<Richard.Kreckel at Uni-Mainz.DE>
<http://wwwthep.physik.uni-mainz.de/~kreckel/>