polynomial arithmetic over ginac

[Parisse Bernard]

"Richard B. Kreckel" a écrit :
> 
> 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?)

Of course, and I'm currently working on this. I did not know that NTL
was GPL now. I will have a look. But it might be better to rewrite
the remaining part of the code on my side since I do not want
to have a huge library.

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

Yes, but I prefer Hermite's method, I believe it "factorizes" in
some sense the linear algebra operations of Horowitz' method.