Abstract: Sparse multivariate polynomial interpolation is an effective strategy to reconstruct black box functions by using the sparse structure of polynomials and the given interpolation point information, which is widely used in science and engineering fields. The complexity of the traditional sparse interpolation algorithm based on Prony method is related to the number and degree of polynomial terms, and the efficiency is low when en-countering large-scale problems due to the execution of multiple high-order algebraic operations. Therefore, this paper proposes a sparse multivariate polynomial interpolation algorithm based on polynomial coefficient parsing. The core operation is to resolve the coefficients of univariate polynomials by using modular arithmetic, which avoids the solution of higher-order equations and finding the roots of higher order equation in the traditional method. In this method, black box polynomial is regarded as a univariate polynomial with one variable as the principal component, and the multivariate polynomial is recovered by parsing the values of the coefficient polynomials of the principal component at different interpolation point. Theoretical analysis and numerical experiments show that the algorithm is effective and feasible.

Key words: sparse multivariate polynomial interpolation, coefficient parsing, Ben-Or/Tiwari algorithm, modular arithmetic