A Sparse Strategy for Polynomial Division with Application to F4.
Roman Pearce, CECM
Abstract: We will introduce a sparse strategy for multivariate polynomial division based on linear algebra and the F4 algorithm for computing Groebner bases. Like F4, our method constructs a large sparse linear system to efficiently reduce several polynomials at once. Unlike F4, our linear system is block triangular, so it can be solved using back substitution and a topological sort. The resulting algorithm constructs the terms of the remainder(s) directly as linear combinations of irreducible terms. Finally, we will demonstrate an improved F4 algorithm based on this technique.