基于多变元插值算法计算Dixon多项式

Computing Dixon Polyhemial via Interpolation Algorithms

Dixon多项式的计算需要涉及到行列式的展开.但是,由于行列式中的元素通常是符号化的,即其中每个元素都是关于变元(或参数)的多项式,导致行列式展开时的中间计算过程膨胀(甚至爆炸).对此,作者提出符号计算数值化的思想,即对变元选择不同的数值构成插值结点,并赋值到行列式中的相应变元,使符号行列式转化为数值行列式.相对来说,数值行列式的值可以非常容易求出.这样,作者通过选择一系列插值结点代入行列式后计算出结果,并利用输入值和输出值之间的关系构造出了原多项式即Dixon多项式.在插值过程中,作者提出了将Lagrange插值与Zippel多变元随机插值算法相结合以充分利用原多项式的稀疏性,并将该算法并行化处理以提高算法效率的思想,有效克服了经典算法的中间计算过程膨胀问题.

When we use classical method to compute Dixon polynomial, we often manipulate matrix and determinant in the procedure of computation. However, as each entry in the determinant is symbolic, that is, a polynomial in variable（s）, this leads to the intermediate expression swell （or explosion） problem in the expansion of determinant. In order to avoid this, the authors convert the symbolic computation to numerical computation, i.e., select support points for variables and evaluate the value to each entries of the determinant. As the result of this, the symbolic determinant is become numerical one and its determinant can be computed out very easily. They get the interpolative polynomial by selecting different suprt points. In the procedure of computation, they combine the Zippel multivariate probabilistic method and Lagrange interpolation to take advantage of the sparsity of Dixon polynomial. In addition, in order to improve the efficiency of algorithm, the idea of algorithmic parallelization is presented. Finally, the Dixon polynomial are obtained by interpolation methods. By using this method, the intermediate expression swell problem is avoided in the classical computation.