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

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