Re: polynomial partial fractions

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Kevin Ryde [2014-12-16 11:19]:
> Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> writes:
> >
> >   C = vector(#P, i, Mod(B \/ PE[i], PE[i]));
> >   [Q, vector(#P, i, padic(lift(A/C[i]), P[i])), PE];
> 
> Nice.  I don't think I knew to go by poly inverses before.  How does
> that rate against a matsolve()? About the same but less taking apart
> and putting back together polynomials perhaps?

In theory, this can be implemented in almost linear time O~(n), n being
the degree of the denominator (assumed to be < deg(numerator)).
Against O(n^\omega) for any feasible matrix multiplication exponent
(n = 3 in PARI/GP, but n = log_2 7 would be practical after a modest
implementation effort).

In practice, the above implementation is quadratic. But it should still
be an order of magnitude faster than matsolve().

Cheers,

    K.B.

P.S. The (very nice) book "Modern Computer Algebra" (Gerhard & von zur Gathen)
provides the background for most of this.

--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`