【作者】 陈良育；

【导师】 杨路；

【作者基本信息】 华东师范大学 ， 系统分析与集成， 2008， 博士

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

【Abstract】 Symbolic computation is generated from Mathematics and Computer Science field and has been an independent and developing research field.Unlike numeric computation,symbolic computation does the exact and precise mathematical calculations on computer so that it has been used in many different fields widely.However,doing the exact computation consumes much memory and CPU cost,symbolic computation has poor efficiency and perfermance for some large and complicated problems,it results in slow calculation and immediate expressions swell.So it is natural to find a quick way to accelerate the calculation performance.With the improvement of computer technology and progress in scientific research,parallel computers show more and more excellence and superiority.Through the cooperation of multiple processors in the parallel computer,parallel computation can accelerate the calculation and balance the memory load during the whole process.Hence,how to utilize and integrate parallel computation has become a hotspot of research in symbolic computation.In this thesis,we introduce parallel computation and symbolic computation,and mainly present several complex problems and their parallel solutions in symbolic computation.The main content of this thesis is follows:（1）Computing determinants of polynomial matrices is a basic and common mathematical operation.But for some large or complex polynomial matrices,it is difficult to get the determinant by expanding directly.We introduce the interpolation method,which converts the polynomial multiplication expansion into polynomial interpolation.By using the interpolation method,we solve the determinant of polynomial matrix into two steps.One is numerical calculation on interpolation point,and the other is solving linear equations.During the whole process,we use parallel computation to speed up the calculation.In the step of interpolation,we adopt coarse granularity to calculate the independent interpolation point on different computers with fewer communications between nodes.In the second step,we extend the Bj（?）rck-Pereyra algorithm of two variables to solve the equations of n variables.We distribute the serious loop of Bj（?）rck-Pereyra computation to several nodes so that we make the complexity of Bj（?）rck-Pereyra computation lower to O(rⁿ⁺¹/nc).We implement the parallel solution in MAPLE,and validate it by some examples from different areas.The result shows that parallel computation can not only quicken the calculation but also avoid the memory problem of immediate expression swell partly.（2）Automated inequality proving has been considered challenging in the area of automated reasoning for many years.We firstly extend the Successive Difference Substitution （SDS）into parallel mode with integrating parallel computation.By using multiple-level Master-Slave mode,we distribute the branches generated by difference substitution to different slave nodes.Each slave node calculates its own branches independently,while the master node collects the results together and finishes the proof.The efficicncy of parallel successive difference substitution is shown by several big inequalities.We also test the speedup of parallel computation for the VASC conjecture with seven variables.（3）The topological structure of difference substitution is studied in detail.We present the inequalites proved by difference substitution is a finitely generated cone and give the DevSubExp algorithm to calculate the extremal rays of difference substitution cone.Then we show the expansion of this cone by using difference substitution successively.Furthermore, we compare difference substitution with another algorithm Schur Partition,which can partition a ternary positive semi-definite homogeneous symmetric polynomial into a linear combination of five positive semi-definite bases.We show that for any ternary polynomials whose positive semi-definiteness can be proven by Schur Partition,it also can be proven by Difference Substitution.（4）Heilbronn problem for seven points.Heilbronn problem is a classic one in the discrete combinatorial geometry,while the Heilbronn problem for seven points has no whole result.In this thesis,we give a proper method with randomly Monte Carlo search method and interval analysis.Through randomly Monte Carlo search method,we put seven points in the unit square randomly and search the numeric optimal solution by the non-linear programming functions of MATLAB.Although the random search has uncertainty,we try to search million times and get the best results.This method is simple but can be extended for other similar geometry problems easily.Then we use symbolic computation and interval analysis to prove the optimal value and point-distribution graph.According to the problem of five and six points,we transfer the Heilbronn problem for seven points into 456427 non-linear optimization problems.We solve these problems by parallel computation on ten nodes.We give the result of Heilbronn problem for seven points in interval form.（5）Computer Algebra System（CAS）is a fundamental backbone for symbolic computation and automated reasoning.There are many excellent CASs,which can provide good interface and high performance computation for researchers.In this thesis,we firstly introduce the cluster task management software SGE and parallel message passing interface MPI. We also show several different ways to express mathematic symbols in computers.Then we discuss how to build a distributed and hybrid computing environment（HPPCAS）to realize the cooperation of different CASs and achieve higher performance through using external calling communication interface and integrating the parallel library and cluster management software.In HPPCAS,each job is submitted to a queue,asked computational resources by slot attribute and scheduled based on its ticket value,which denote the priority of job.Finally, we verify the efficiency of HPPCAS by the calculation of parallel successive difference substitution.From the above work,we can arrive the result that symbolic computation can benefit from parallel computation in the calculation process.Through parallel computation,it can balance the peak memory consumption to many nodes,alleviate the trouble of memory scarcity.It also distributes the calculative tasks to many nodes,and do calculation concurrently to improve the process quickly and easily.We think parallel computation will make symbolic computation more powerful and mightful.更多还原