search

flintlib / calcium

Calcium has been merged into FLINT -- use https://github.com/flintlib/flint/ instead
http://fredrikj.net/calcium/
GNU Lesser General Public License v2.1
79 stars 11 forks source link

qqbar: fast polynomial evaluation and powering #19

Closed fredrik-johansson closed 3 years ago

fredrik-johansson commented 3 years ago

Evaluating an fmpz_poly or fmpq_poly at a qqbar argument just uses Horner's rule at the moment, requiring repeated expensive qqbar arithmetic operations. It should be possible to do much better, i.e. finding an annihilating polynomial in one go using linear algebra (at least so I've been told -- I don't know the algorithm myself).

The same applies to powering.

fredrik-johansson commented 3 years ago

This has been fixed. (Powering can be improved, but should be decent now.)