论文部分内容阅读
非线性代数方程组的求解是一个基本而重要的问题，很多实际问题最终都可以转化为非线性代数方程组的求解问题。在现代计算机代数领域中，求解非线性方程组一般有三种方法：Groebner基方法，Ritt-Wu方法和结式方法。
在所有的结式方法中，Dixon 结式方法能够从一个非齐次多项式系统中同时消去多个变量，是效率最高的方法之一。然而这样一个优秀的方法并没有得到广泛应用，因为在很多实际问题中，可能会遇到Dixon结式的退化问题，也就是说Dixon 矩阵是奇异的，结式行列式恒为零而无法得到有关变元的有用信息，或者Dixon 矩阵为非方阵而根本无法求出结式。
针对Dixon 结式的退化问题，杨路等人提出了扩展Dixon结式方法，他们证明：如果奇异或非方阵的Dixon矩阵满足条件——“Dixon 矩阵中存在一列不能表示成其他列的线性组合”，则Dixon矩阵的最大非奇异子矩阵的行列式可以作为扩展Dixon结式，同样提供关于原多项式系统的解的有关信息，该方法的提出大大扩展了Dixon结式方法的应用范围。但是符号方法存在速度慢，效率低，中间表达膨胀等问题，使得它只适合解决小规模问题。为了缓解符号方法中间表达膨胀的问题，冯勇等人提出了数值化的扩展Dixon结式方法，使效率得到了提高。
数值化方法如果是串行执行的，那么在插值点过多的情况下，仍然会出现效率低下的问题，采用并行计算可以有效的解决这个问题。因此在数值化的扩展Dixon 结式方法的基础上，针对矩阵行列式是稠密或稀疏这两种情况，本文将两个并行算法应用到。Dixon结式的计算过程中，提出了Dixon结式的并行算法。该算法把Dixon结式计算过程中的瓶颈问题都采用数值且并行的方法实现，数值方法有利于缓解中间表达膨胀，而良好的并行性又使效率得到保证。本文从理论上分析了算法的高效性，并通过实验进行了验证。最后，文章还介绍了此并行算法在机器证明中的应用。