Sparse Multivariate Polynomial Interpolation And Its Application In Computation Of Resultant

In the field of science and engineering,there are many black-box functions coming from the input and output of complex systems or constructed by algorithms.The characteristic of these functions is that they can be easily evaluated,but mathematical expressions can not be given directly.Interpolation strategy is very effective in constructing such black-box functions,especially for problems in computer algebra,such as GCD computation,resultant computation and so on.In addition,sparse interpolation is also widely used in signal processing,exponential analysis,rational approximation theory and other fields of science and engineering.At present,for sparse multivariate polynomial interpolation,there are mainly the following problems: first,the efficient sparse multivariate polynomial interpolation algorithm in finite field is non-deterministic,and can not accurately recover the black box polynomial with a certain probability.Second,when the existing schemes encounter large-scale polynomial interpolation problems,the required operations are high-order algebraic operations,and the computational complexity is high.Thirdly,the construction of resultant matrix is a computationally intensive task.When the number of variables and equations is large,the dimension of the resultant matrix is large and the elements are complex.Symbolic computation and interpolation strategy are needed to solve the problem of intermediate expression expansion.In this paper,a sparse interpolation computation model with controllable algebraic operation scale is constructed,and a Dixon resultant computation algorithm based on sparse interpolation is designed.The main research contents are as follows:(1)A high probability sparse multivariate polynomial interpolation algorithm over finite field is proposed.At present,the most efficient sparse interpolation algorithm based on diversified polynomials is a probabilistic algorithm,which has a certain probability of failure.In order to improve the accuracy of the algorithm to reconstruct the black box polynomial,three situations that the algorithm can not accurately recover the black box polynomial are analyzed,and the corresponding solutions are given for these three situations.The probability of successful interpolation is improved by adding interpolation points and primitive roots.Based on this,a high probability sparse interpolation algorithm based on diversified polynomial is designed.The time complexity analysis shows that the modified algorithm is the same order as the original one.(2)A sparse multivariate polynomial interpolation algorithm based on modular arithmetic is proposed.In order to solve the problem of high complexity of algebraic operations in large-scale polynomial interpolation over finite fields,a sparse interpolation algorithm based on divide-and-conquer strategy and modular arithmetic is proposed.Firstly,the original problem is divided into several sub-polynomial interpolation problems with smaller scale by using the idea of partition.Then the modular arithmetic strategy is used to efficiently resolve the information needed to recover the sub-polynomial with fewer interpolation points,so as to improve the computational efficiency of interpolation.A large number of comparative experiments show that the algorithm can effectively solve large-scale multivariate polynomial interpolation problem.(3)We designed the computation of Dixon resultant based on sparse interpolation.Considering the application of sparse interpolation algorithm in resultant computation,a fast recursive Dixon matrix construction algorithm based on heuristic strategy is proposed.Aiming at solving a class of sparse polynomial systems,a heuristic strategy is proposed.Sylvester resultant is used to eliminate some variables,and then the matrix multiplication is simplified to the sum of the multiplications of multiple submatrices.Finally,Di xon resultant is constructed by the strategy of replacing variable,and the Dixon resultant i s recovered by sparse interpolation algorithm based on the analysis of modulus arithmetic coefficients.The sparse interpolation algorithm proposed in this paper improves the probability of exact recovery of black-box polynomials,and the sparse interpolation algorithm based on modular arithmetic effectively solves the problem of large-scale polynomial sparse interpolation.The application of Dixon resultant calculation shows that the algorithm has a certain application prospect.