Lazy and Forgetful Polynomial Arithmetic and Applications

Abstract

We present lazy and forgetful algorithms for multiplying and dividing multivariate polynomials. The lazy property allows us to compute the i-th term of a polynomial without doing the work required to compute all the terms. The forgetful property allows us to forget earlier terms that have been computed to save space. For example, given polynomials A,B,C,D,E we can compute the exact quotient $Q = \frac{A \times B - C \times D}{E}$ without explicitly computing the numerator A ×B − C ×D which can be much larger than any of A,B,C,D,E and Q. As applications we apply our lazy and forgetful algorithms to reduce the maximum space needed by the Bareiss fraction-free algorithm for computing the determinant of a matrix of polynomials and the extended Subresultant algorithm for computing the inverse of an element in a polynomial quotient ring.