Sparse Pseudo Division
Roman 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 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.