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

摘要：

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

关键词：Dixon多项式、多变元插值、中间计算过程膨胀、稀疏多项式

所属期刊栏目：43

分类号：O24(计算数学)

资助基金：国家研究发展基金2004CB318003;国家高技术研究发展计划863计划10172028

在线出版日期：2006-08-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：489-496