论文摘要
符号计算是数学和计算机领域融合产生的一个新的交叉学科,主要利用计算机严格处理准确的数学运算,没有舍入误差,因此在许多领域有着非常重要的应用。由于准确计算需要耗费大量内存和ICPU运算的缘故,符号计算关于复杂问题的计算效率一直不能满足实用要求,主要表现为计算速度慢和中间表达式膨胀两个问题,严重阻碍问题的求解。另一方面,随着计算机软硬件普及和技术水平的日益提升,并行计算已经成为高性能计算的核心力量。利用集群计算机中多个处理器协同工作的计算优势,并行计算不仅可以大幅度加快问题的求解速度,而且可以平衡计算过程中内存负载。因此,如何将并行计算引入到符号计算过程中,既能发挥并行计算的优势,又能推广符号计算的应用领域,这是目前在符号计算和高性能计算领域里的一个非常重要的问题。本文立足于并行计算和符号计算的基础上,主要讨论符号计算中若干个问题以及并行化解决方法的研究。本文主要的工作包含以下五点:（1）.多项式矩阵行列式展开是符号计算中一个很基础的数学运算。我们讨论了将多项式行列式展开转化为多项式插值的方法。利用多项式插值的思想,将繁杂的行列式展开问题,转化为大量的数值插值点计算和解线性方程组两个步骤。由于计算量很大,特将并行计算引入整个计算过程。首先在插值点计算上,由于需要计算的插值点很多,可以在多个处理器上并行计算插值点,最后将所有的插值点汇总起来。并行计算采用粗粒度方式,每个处理器独立计算自己的插值点,只需要很少的消息传递。在线性方程组求解上,扩展了两个变元的Bjorck-Perevra方法,并且将计算中重点运算部份分配到多个节点同时进行。将原有的文献[135]的Bjorck-Pereyra方法的复杂程度下降到O(rn+1/nc)。通过计算机代数系统MAPLE程序语言实现了以上并行行列式展开方法,并对若干个实际例子进行验证,结果是非常有效的。并行计算不仅加快插值点的求值计算,而且平衡了单个机器过高的内存负载,有效克服了中间表达式膨胀的问题。（2）.不等式的证明一直是个比较困难的问题。我们讨论了差分代换方法。差分代换方法使用起来非常简单,但是却能够非常有效证明许多不平凡的不等式。对于某些次数较高或者变元较多的不等式,其它不等式证明的方法几乎都无法求解,而差分代换却能够化繁为简,利用简单多项式合并和化简步骤就可以证明不等式。而且整个证明过程是可读的,容易被读者理解和验证。在连续差分代换方法的基础上,结合并行计算技术,将差分代换所产生的大量分支不等式分散到多个计算节点上,每个节点独立计算,并将结果汇总到一起,完成整个不等式的证明。通过若干个实际例子证明了并行差分代换方法是非常有效的,不仅加快了计算求解速度,而且还能将计算过程中大多项式所引起的内存消耗峰值平均分配到多个计算节点上,充分克服了符号计算中内存瓶颈的问题,使得求解更加迅速,且延扩了串行差分代换所证明的不等式范围。（3）.差分代换方法的进一步讨论。我们讨论了基于差分代换方法证明的不等式所组成的集合的拓扑结构,证明了这个集合是一个有限生成锥,并且给出一个实用算法用来计算锥的端点。通过连续差分代换,可以对这个锥进行了扩展,使之能够证明更多的不等式。我们还比较差分代换和Schur分拆两种不等式证明方法进行比较,证明了能够被Schur分拆证明的不等式同样可以用差分代换方法来证明,这表明差分代换方法在不等式证明部分可以替代Schur分拆方法。（4）.Heilbronn七点问题。Heilbronn问题是离散组合几何中一个经典的问题,其中七点的Heilbronn问题到目前为止还没有一个满意的解决方法。我们给出了一个合理的解决方法。首先利用蒙特卡罗随机搜索方法,在单位正方形内随意放入七个点后,进行最优化搜索,利用Matlab自带的非线性规划求解得到的结果是目前为止最好的。虽然随机搜索随意性很大,但是经过大量重复的取值后,在某种程度上弥补了结果的随机性。这种随机搜索的方法原理简单,可以推广到其它离散几何问题。接着,利用数值计算和符号计算等工具证明这个结果是最优的。根据H5,H6等已知结果,将H7分成两个大类十五个小类分别进行讨论,将最终问题转化为456427个非线性问题求解问题。利用数值计算软件Matlab产生非线性问题的基本条件,然后结合符号计算中GrSbner基、区间代数等多种方法,求出非线性问题的形式实解。由于非线性问题个数高达几十万个,计算量很大,所以采用并行计算策略,在多个计算节点上并发计算,加快问题的求解。由于方程的次数较高,我们的最优结果是以区间表示的形式实解。（5）.计算机代数软件是符号计算的最重要的研究基础。如何高效利用这些计算机代数软件在集群计算机的基础上协同工作提升符号计算效率,是一个非常重要的问题。集群环境下计算机代数软件协同工作需要两个基础:集群管理软件和合适的数学表达式表示方法。首先讨论了集群管理软件SGE和并行消息通讯库MPI,分析它们在并行计算和任务管理调度方面的特性。然后描述了数学表达式在计算机中合理表示的多种方法,分析了它们相应的优缺点。最后在详细分析异构的计算机代数系统之间通讯调用机制的基础上,提出了一种高性能计算机代数环境HHPCAS,综合多种现有的多种计算机代数软件,结合集群管理软件和并行环境,可以提供高性能计算的计算机代数计算环境,并且通过一个并行差分代换的实例证明HHPCAS的准确性和高效性。通过对四个典型问题的并行化解决方法研究,充分将并行计算和符号计算结合起来,利用并行计算的并发特点,加速符号计算的求解。同时将符号计算中巨大的数学对象分配到多个计算节点上,平衡内存消耗峰值,克服中间表达式膨胀问题。而且经过一系列实验表明,并行计算能够有效加快符号计算的计算速度,扩大符号计算的求解范围,对符号计算的发展是非常有益的。
论文目录
相关论文文献
标签：符号计算论文; 并行计算论文; 多项式矩阵行列式论文; 结式论文; 不等式证明论文; 差分代换论文; 七点问题论文;