Sparse Pseudo Division

Roman Pearce, CECM, SFU

Wednesday October 24th, 2007 at 3:30pm in K9509.

Abstract: 

This talk will examine different ways to implement pseudo division
for sparse multivariate polynomials with rational coefficients.
Pseudo division is used to reduce polynomials with respect to a
Groebner basis or a triangular set, and to test the divisibility
of polynomials in the presence of non-monic algebraic extensions.
We will show that in the sparse case, the widely-used classical
algorithm has poor complexity in terms of both the number of
monomial comparisons and the number of arithmetic operations,
and we will demonstrate a faster algorithm.