Gcd computation over algebraic function fields.

Mahdi Javadi, MITACS

Wednesday October 18th, 10:30am in IRMACS 10908.


We will present SparseModGcd, an algorithm which computes polynomials
gcds over an algebraic function field with multiple field extensions
using sparse interpolation. Our algorithm is an extension to Monagan and van
Hoeij's ModGcd algorithm which uses dense interpolation and supports one
field extension. We will show that SparseModGcd is more efficient when
the gcd of the inputs is sparse. It is also competetive to ModGcd
for dense polynomials.