Talk
eSeminar: Faster modular composition of polynomials
Talk by Dr. Vincent Neiger
Date: 19.05.21 Time: 15.00 - 16.00 Room:
(**This eSeminar will take place on Zoom, using the same meeting details as previous seminars. If you do not have meeting details, please contact simran.tinani@math.uzh.ch **)
This talk is about algorithms for modular composition of univariate
polynomials, and for computing minimal polynomials. For two univariate
polynomials a and g over a commutative field, modular composition asks to
compute h(a) mod g for some given h, while the minimal polynomial problem is
to compute h of minimal degree such that h(a) = 0 mod g. We propose
algorithms
whose complexity bound improves upon previous algorithms and in
particular upon
Brent and Kung's approach (1978); the new complexity bound is
subquadratic in
the degree of g and a even when using cubic-time matrix multiplication. Our
improvement comes from the fast computation of specific bases of
bivariate ideals,
and from efficient operations with these bases thanks to fast univariate
polynomial
matrix algorithms. We report on preliminary experimental results using
our new
Polynomial Matrix Library ( https://github.com/vneiger/pml ).
Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost,
Gilles Villard.