Solving multivariate diophantine equations and their role in multivariate polynomial factorization

Date created: 
Multivariate polynomial factorization
Multivariate Hensel lifting
Multivariate polynomial diophantine problem
Sparse interpolation
Sparse Hensel lifting

Multivariate polynomial factorization over integers via multivariate Hensel lifting (MHL) is one of the central areas of research in computer algebra. Most computer algebra platforms, such as Maple, Magma and Singular, implement Wang's incremental design of MHL which lifts the factors one variable at a time and one degree at a time. At each step MHL must solve a multivariate diophantine problem (MDP) which Wang solves using the same idea; lifting the solutions one variable and one degree at a time. Although this performs well when the evaluation points are mostly zero, it performs poorly when there are many non-zero evaluation points as the number of MDP problems to be solved can be exponential in the number of variables. In this thesis we introduce a new non-recursive solution to the MDP which explicitly exploits the sparsity of the solutions to the MDP. We use sparse interpolation techniques and exploit the fact that at each step of MHL, the solutions to MDP's are structurally related. We design a probabilistic sparse Hensel lifting algorithm (MTSHL) and give a complete average case complexity analysis for it. We describe a series of experiments based on our implementation of MTSHL, compare its efficiency with Wang's algorithm, and show that MTSHL performs better for many practical applications. We also show that previous probabilistic approaches proposed for MHL as an alternative to Wang's algorithm are not practical whereas MTSHL is practical and the running time is predictable.

Document type: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
Senior supervisor: 
Michael Monagan
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.