Solving parametric systems using Dixon resultants and sparse interpolation tools

Many elimination techniques such as Grobner bases and Triangular sets have been employed to address the growing demand for solving parametric polynomial systems in practice. However, experiments have shown that these elimination methods when used in computer algebra systems such as Maple and Magma often fail on systems that have many parameters; they can take a very long time to execute or run out of memory. To address this problem, this thesis presents a new interpolation algorithm for solving parametric polynomial systems (systems of n polynomial equations involving n variables and m parameters with rational coefficients) over Q using Dixon resultants. The Dixon resultant R of a parametric polynomial system is a multiple of the unique monic generator of an elimination ideal of a polynomial system, and it can be expressed as the determinant of a matrix M of polynomial entries called the Dixon matrix. Given a black box for the Dixon resultant R = det(M) (we evaluate the Dixon matrix M at integer points modulo primes and compute determinant of integer matrices modulo primes), we present a new Dixon resultant algorithm that interpolates the monic square-free factors Rj of the Dixon resultant R from monic univariate polynomial images of R. This new Dixon resultant algorithm uses our newly developed sparse multivariate rational function interpolation method over Q to interpolate the rational function coefficients of the monic square-free factors modulo primes. It further uses rational number reconstruction and Chinese remaindering to recover the rational coefficients of the Rj 's. We have made a hybrid Maple and C implementation of our Dixon resultant algorithm. Our benchmarks show that our new Dixon resultant algorithm can solve many parametric polynomial systems that other algorithms for computing R are unable to solve. However, the new Dixon resultant algorithm may fail to produce an answer, and even when it is successful, the returned answer might be wrong with provably low probability. Consequently, we identify and classify all the causes of failure in our new algorithm, and we give a detailed failure probability analysis and complexity analysis of our new Dixon resultant algorithm. Furthermore, we consider another related problem. Let Ax = b be a parametric linear system such that the coefficient matrix A is of full rank. In general, the solutions xi will be rational functions in the parameters. We present a new black box algorithm for interpolating iii the entries xi using our new sparse multivariate rational function interpolation method. We present timing results comparing our hybrid Maple and C implementation of our new algorithm with four other algorithms in Maple for solving Ax = b. A failure probability analysis and complexity analysis for our new algorithm is also presented.