关键词: 稀疏插值, 多元多项式, Javadi/Monagan算法, 二部图, 完美匹配

Abstract: Sparse interpolation is an effective method to reduce the time complexity of computer algebraic algorithms. It has been widely used in the fields of signal processing, compressed sensing, resultant computation, image processing and so on. In order to improve the efficiency of sparse multivariate polynomial interpolation algorithms, an improved sparse interpolation algorithm addressed by Javadi and Monagan is presented. Firstly, the restriction on [T], which is the bound on the number of terms and necessary condition in the original method, has been eliminated. In fact, the exact number of terms in [f] can be obtained by computing the determinant of special defined matrix. Secondly, the necessary condition that the degree bound [D] in [f] must be given in advance has been also eliminated. The exact degree of [f] is obtained by forming an auxiliary function, applying the high probabilistic method, and combining with early termination technique in Cauchy interpolation. Thus the problem of high computational complexity caused by the bad degree bound [D] in Javadi/Monagan algorithm is solved. Compared to Javadi/Monagan algorithm, the theory analysis and experiment results reveal that the performance has been highly improved by applying new algorithm, especially when the given degree bound is too high. Furthermore, the improved algorithm does not need [T] and [D] in advance, so it is more practical to use the interpolation recovery or approximation for real problems.

Key words: sparse interpolation, multivariate polynomial, Javadi/Monagan algorithm, bipartite graph, perfect matching