Polynomial Algebraic Algorithms And Their Applications Based On Sparse Interpolation

Polynomial algebra is a basic and typical nonlinear algebra,which can be used to describe and deal with various nonlinear scientific problems.The classic contents of polynomial algebra lie in the establishment of the existence theory and methods,rather than the constructive study of concrete algebra and geometry objects.Be-cause the latter involves a large number of complex polynomial operations,it is often complicated beyond the scope of the traditional manual deduction.The transforma-tion to constructivity and algorithmization for polynomial algebra began in the 60s.From then on,with the rapid development of symbolic and algebraic computation and software,it is feasible to carry out large-scale polynomial operations on comput-er.Although the use of symbolic methods for solving algebraic problems can obtain the complete solution,they are far from the requirements of practical application-s caused by the high computation complexity and expressions swell which lead to increase storage space and lower computation speed.Present more efficient polynomial algebraic algorithms and then use them to solve all kinds of problems in theory and practice has become the main research direction in the field of polynomial algebra in recent years.Sparse interpolation is an effective method to reduce the time complexity of algebraic algorithms.It has been widely used in the fields of resultant computation,signal processing,compressed sensing,uncertainty quantification and so on.In this paper,we study two typical polynomial algebra problems based on sparse interpolation,including resultant e-limination and the greatest common divisor computation.We present the resultant elimination method via implicit equation interpolation and the greatest common di-visor computation algorithms based on sparse multivariate polynomial interpolation.The resultant elimination method via implicit function interpolation is applied to solve a class of complex combinatorial geometric optimization problems.The main work and method are carried out as follows:?We discuss the problem of implicit equation interpolation,design and imple-ment the algorithm for implicit equation interpolation problem.We give the definition to implicit equation interpolation and transfer this problem to several multivariate rational function interpolations,which are recovered by combining univariate rational function interpolation and sparse multivariate polynomial interpolation.For univariate rational function interpolation we apply the high probabilistic method,by combining with early termination technique in Cauchy interpolation;for sparse multivariate polynomial interpolation we employ a de-terministic polynomial time algorithm given by Ben-Or and Tiwari.For the evaluation at the zero point is undefined,or the zero point is the degenerate case of rational functions,we present a new approach to treat the general case that whether the constant terms of numerator and denominator of rational function are zeros.And we present the probabilistic analysis of our method.?We present the resultant elimination method based on implicit equation inter-polation in order to solve a class of complicated nonlinear multivariate poly-nomial equation systems which can not be deal with by pure symbolic and numerical computation.We eliminate variables sequentially,based on comput-ing the Sylvester resultant of two multivariate polynomials.It is noticed that the extraneous factors will be removed during the process of variable elimina-tion via Sylvester resultants.The above elimination process is able to construct a black box of the implicit equation,by providing the initial values to the given polynomial system.We transform the resultant elimination problems to im-plicit equation interpolation problems and recover the resultant of polynomial system by using implicit function interpolation algorithm.?We apply resultant elimination method based on implicit equation interpola-tion successfully for solving a class of complicated combinatorial geometric and optimization problems,such as finding the maximal perimeter of triangle con-stituted by three points on an ellipse,Morley's trisector theorem,finding the minimum perimeter of triangle constituted by three points on the edges of a triangle.The experiments show that our approach of resultant elimination is more efficient than some existing resultant elimination methods on these diffi-cult problems.?We present the sparse interpolation algorithms for the greatest common divisor of two multivariate polynomials.By introducing the homogenizing variable,we form auxiliary polynomials and shift auxiliary polynomials.Our approaches build on the normalization of the target GCD representation.In the first step,the sparsity structure of the target GCD is determined by univariate GCD com-putations with respect to the homogenizing variable.In the second step,the sparse multivariate polynomial interpolation based on the variation of Zippel's algorithm and Ben-Or/Tiwari algorithm can reconstruct the coefficient poly-nomials in the homogenizing variable,that is the homogenizing polynomials of target GCD.Our algorithms do not require any polynomial factorization and have no restriction on the form of the target GCD.The complexity of our al-gorithms is sensitive to the sparsity of the target GCD and the choice of the employed sparse multivariate polynomial interpolation algorithms.?To reduce computational complexity of implicit function interpolation,resultan-t elimination based on implicit function interpolation and sparse interpolation algorithms for multivariate polynomial GCD computation,we apply probabilis-tic,modular arithmetic techniques and the modular arithmetic technique.