
Sparse Pseudo DivisionRoman Pearce, CECM, SFU
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 nonmonic algebraic extensions. We will show that in the sparse case, the widelyused 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. 