（系统分析与集成专业论文）并行符号算法若干问题的研究与应用.pdf

摘要 符号计算是数学和计算机领域融合产生的一个新的交叉学科，主要利用计算机严格处 理准确的数学运算，没有舍入误差，因此在许多领域有着非常重要的应用。由于准确计算 需要耗费大量内存和c p u 运算的缘故，符号计算关于复杂问题的计算效率一直不能满足实 用要求，主要表现为计算速度慢和中间表达式膨胀两个问题，严重阻碍问题的求解。另一 方面，随着计算机软硬件普及和技术水平的日益提升，并行计算已经成为高性能计算的核 心力量。利用集群计算机中多个处理器协同工作的计算优势，并行计算不仅可以大幅度加 快问题的求解速度，而且可以平衡计算过程中内存负载。因此，如何将并行计算引入到符 号计算过程中，既能发挥并行计算的优势，又能推广符号计算的应用领域，这是目前在符 号计算和高性能计算领域里的一个非常重要的问题。 本文立足于并行计算和符号计算的基础上，主要讨论符号计算中若干个问题以及并行 化解决方法的研究。本文主要的工作包含以下五点： ( 1 ) 多项式矩阵行列式展开是符号计算中一个很基础的数学运算。我们讨论了将多项 式行列式展开转化为多项式插值的方法。利用多项式插值的思想，将繁杂的行列式展开问 题，转化为大量的数值插值点计算和解线性方程组两个步骤。由于计算量很大，特将并行 计算引入整个计算过程。首先在插值点计算上，由于需要计算的插值点很多，可以在多个 处理器上并行计算插值点，最后将所有的插值点汇总起来。并行计算采用粗粒度方式， 每个处理器独立计算自己的插值点，只需要很少的消息传递。在线性方程组求解上，扩 展了两个变元的b j 街c k p e r e y r a 方法，并且将计算中重点运算部份分配到多个节点同时进 行。将原有的文献 1 3 5 的b j 6 r c k - p e r e y t a 方法的复杂程度下降到o ( 譬) 。通过计算机代数 系统m a p l e ；程序语言实现了以上并行行列式展开方法，并对若干个实际例子进行验证，结 果是非常有效的。并行计算不仅加快插值点的求值计算，而且平衡了单个机器过高的内存 负载，有效克服了中间表达式膨胀的问题。 ( 2 ) 不等式的证明一直是个比较困难的问题。我们讨论了差分代换方法。差分代换方 法使用起来非常简单，但是却能够非常有效证明许多不平凡的不等式。对于某些次数较高 或者变元较多的不等式，其它不等式证明的方法几乎都无法求解，而差分代换却能够化繁 为简，利用简单多项式合并和化简步骤就可以证明不等式。而且整个证明过程是可读的， 容易被读者理解和验证。在连续差分代换方法的基础上，结合并行计算技术，将差分代换 所产生的大量分支不等式分散到多个计算节点上，每个节点独立计算，并将结果汇总到一 起，完成整个不等式的证明。通过若干个实际例子证明了并行差分代换方法是非常有效 的，不仅加快了计算求解速度，而且还能将计算过程中大多项式所引起的内存消耗峰值平 均分配到多个计算节点上，充分克服了符号计算中内存瓶颈的问题，使得求解更加迅速， 且延扩了串行差分代换所证明的不等式范围。 ( 3 ) 差分代换方法的进一步讨论。我们讨论了基于差分代换方法证明的不等式所组成 的集合的拓扑结构，证明了这个集合是一个有限生成锥，并且给出个实用算法用来计算 锥的端点。通过连续差分代换，可以对这个锥进行了扩展，使之能够证明更多的不等式。 我们还比较差分代换和s c h u r 分拆两种不等式证明方法进行比较，证明了能够被s c h u r 分拆 证明的不等式同样可以用差分代换方法来证明，这表明差分代换方法在不等式证明部分可 以替代s c h u r 分拆方法。 ( 4 ) h e i l b r o n n 七点问题。h e i l b r o n n i b - 题是离散组合几何中一个经典的问题，其中七点 的h e i l b r o n n 问题到目前为止还没有一个满意的解决方法。我们给出了一个合理的解决方 法。首先利用蒙特卡罗随机搜索方法，在单位正方形内随意放入七个点后，进行最优化搜 索，利用m a t l a b 自带的非线性规划求解得到的结果是目前为止最好的。虽然随机搜索随意 性很大，但是经过大量重复的取值后，在某种程度上弥补了结果的随机性。这种随机搜索 的方法原理简单，可以推广到其它离散几何问题。接着，利用数值计算和符号计算等工具 证明这个结果是最优的。根据风，风等已知结果，将日7 分成两个大类十五个小类分别进行 讨论，将最终问题转化为4 5 6 4 2 7 个非线性问题求解问题。利用数值计算软件m a t l a b 产生非 线性问题的基本条件，然后结合符号计算中g r 6 b n e 瑾、区间代数等多种方法，求出非线性 问题的形式实解。由于非线性问题个数高达几十万个，计算量很大，所以采用并行计算策 略，在多个计算节点上并发计算，加快问题的求解。由于方程的次数较高，我们的最优结 果是以区间表示的形式实解。 ( 5 ) 计算机代数软件是符号计算的最重要的研究基础。如何高效利用这些计算机代数 软件在集群计算机的基础上协同工作提升符号计算效率，是一个非常重要的问题。集群环 i i 境下计算机代数软件协同工作需要两个基础：集群管理软件和合适的数学表达式表示方 法。首先讨论了集群管理软件s g e 和并行消息通讯库m p i ，分析它们在并行计算和任务管 理调度方面的特性。然后描述了数学表达式在计算机中合理表示的多种方法，分析了它们 相应的优缺点。最后在详细分析异构的计算机代数系统之间通讯调用机制的基础上，提出 了一种高性能计算机代数环境h h p c a s ，综合多种现有的多种计算机代数软件，结合集群 管理软件和并行环境，可以提供高性能计算的计算机代数计算环境，并且通过一个并行差 分代换的实例证明脚鲋s 的准确性和高效性。 通过对四个典型问题的并行化解决方法研究，充分将并行计算和符号计算结合起来， 利用并行计算的并发特点，加速符号计算的求解。同时将符号计算中巨大的数学对象分配 到多个计算节点上，平衡内存消耗峰值，克服中间表达式膨胀问题。而且经过一系列实验 表明，并行计算能够有效加快符号计算的计算速度，扩大符号计算的求解范围，对符号计 算的发展是非常有益的。 关键词：符号计算；并行计算；多项式矩阵行列式；结式；不等式证明；差分代换； h e i l b r o n n 七点问题：s g e ；m p i ；m a t h m l ；m a p l e ；m a t l a b 。 i i i a b s t r a c t s y m b o l i cc o m p u t a t i o ni sg e n e r a t e df r o mm a t h e m a t i c sa n dc o m p u t e rs c i e n c ef i e l da n d h a sb e e na ni n d e p e n d e n ta n dd e v e l o p i n gr e s e a r c hf i e l d u n l i k en u m e r i cc o m p u t a t i o n ，s y m b o l i c c o m p u t a t i o nd o e st h ee x a c ta n dp r e c i s em a t h e m a t i c a lc a l c u l a t i o n so nc o m p u t e r s ot h a ti th a s b e e nu s e di nm a n yd i f f e r e n tf i e l d sw i d e l y h o w e v e r ，d o i n gt h ee x a c tc o m p u t a t i o nc o n s u m e s m u c hm e m o r ya n dc p uc o s t ，s y m b o l i cc o m p u t a t i o nh a sp o o re f f i c i e n c ya n dp e r f e r m a n c ef o r s o m el a r g ea n dc o m p l i c a t e dp r o b l e m s ，i tr e s u l t si ns l o wc a l c u l a t i o na n di m m e d i a t ee x p r e s s i o n s s w e l l s oi ti sn a t u r a lt of i n daq u i c kw a yt oa c c e l e r a t et h ec a l c u l a t i o np e r f o r m a n c e w i t ht h ei m p r o v e m e n to fc o m p u t e rt e c h n o l o g ya n dp r o g r e s si ns c i e n t i f i cr e s e a r c h ，p a r - a l l e lc o m p u t e r ss h o wm o r ea n dm o r ee x c e l l e n c ea n ds u p e r i o r i t y t h r o u g ht h ec o o p e r a t i o n o fm u l t i p l ep r o c e s s o r si nt h ep a r a l l e lc o m p u t e r ，p a r a l l e lc o m p u t a t i o nc a na c c e l e r a t et h ec a l - c u l a t i o na n db a l a n c et h em e m o r yl o a dd u r i n gt h ew h o l ep r o c e s s h e n c e ，h o wt ou t i l i z ea n d i n t e g r a t ep a r a l l e lc o m p u t a t i o nh a sb e c o m eah o t s p o to fr e s e a r c hi ns y m b o l i cc o m p u t a t i o n i nt h i st h e s i s ，w ei n t r o d u c ep a r a l l e lc o m p u t a t i o na n ds y m b o l i cc o m p u t a t i o n ，a n dm a i n l y p r e s e n ts e v e r a lc o m p l e xp r o b l e m sa n dt h e i rp a r a l l e ls o l u t i o n si ns y m b o l i cc o m p u t a t i o n t h e m a i nc o n t e n to ft h i st h e s i si sf o l l o w s ： c o m p u t i n gd e t e r m i n a n t so fp o l y n o m i a lm a t r i c e si sab a s i ca n dc o m m o nm a t h e m a t - i c a lo p e r a t i o n b u tf o rs o m el a r g eo rc o m p l e xp o l y n o m i a lm a t r i c e s ，i ti sd i f f i c u l tt og e tt h e d e t e r m i n a n tb ye x p a n d i n gd i r e c t l y w ei n t r o d u c et h ei n t e r p o l a t i o nm e t h o d ，w h i c hc o n v e r t s t h ep o l y n o m i a lm u l t i p l i c a t i o ne x p a n s i o ni n t op o l y n o m i a li n t e r p o l a t i o n b yu s i n gt h ei n t e r - p o l a t i o nm e t h o d ，w es o l v et h ed e t e r m i n a n to fp o l y n o m i a lm a t r i xi n t ot w os t e p s o n ei s n u m e r i c a lc a l c u l a t i o no ni n t e r p o l a t i o np o i n t ，a n dt h eo t h e ri ss o l v i n gl i n e a re q u a t i o n s d u r - i n gt h ew h o l ep r o c e s s ，w eu s ep a r a l l e lc o m p u t a t i o nt os p e e du pt h ec a l c u l a t i o n i nt h es t e p o fi n t e r p o l a t i o n ，w ea d o p tc o a r s eg r a n u l a r i t yt oc a l c u l a t et h ei n d e p e n d e n ti n t e r p o l a t i o np o i n t o nd i f f e r e n tc o m p u t e r sw i t hf e w e rc o m m u n i c a t i o n sb e t w e e nn o d e s i nt h es e c o n ds t e p ，w ee x - t e n dt h es j 5 r c k - p e r e y r aa l g o r i t h mo ft w ov a r i a b l e st os o l v et h ee q u a t i o n so f 佗v a r i a b l e s w e d i s t r i b u t et h es e r i o u sl o o po fb j 5 r c k - p e r e y r ac o m p u t a t i o nt os e v e r a ln o d e ss ot h a tw em a k e i v t h ec o m p l e x i t yo fb j f r c k - p e r e y r ac o m p u t a t i o nl o w e rt od ( 譬) w ei m p l e m e n tt h ep a r a l l e l s o l u t i o ni nm a p l e ，a n dv a l i d a t ei tb ys o m ee x a m p l e sf r o md i f f e r e n ta r e a 8 t h er e s u l ts h o w s t h a tp a r a l l e lc o m p u t a t i o nc a nn o to n l yq u i c k e nt h ec a l c u l a t i o nb u ta l s oa v o i dt h em e m o r y p r o b l e mo fi m m e d i a t ee x p r e s s i o ns w e l lp a r t l y ( 2 ) a u t o m a t e di n e q u a l i t yp r o v i n gh a sb e e nc o n s i d e r e dc h a l l e n g i n gi nt h ea r e ao fa u t o - m a t e dr e a s o n i n gf o rm a n yy e a r s w ef i r s t l ye x t e n dt h es u c c e s s i v ed i f f e r e n c es u b s t i t u t i o n ( s d s ) i n t op a r a l l e lm o d ew i t hi n t e g r a t i n gp a r a l l e lc o m p u t a t i o n b yu s i n gm u l t i p l e - l e v e l m a s t e r - s l a v em o d e ，w ed i s t r i b u t et h eb r a n c h e sg e n e r a t e db yd i f f e r e n c es u b s t i t u t i o nt od i f f e r - e n ts l a v en o d e s e a c hs l a v en o d ec a l c u l a t e si t so w nb r a n c h e si n d e p e n d e n t l y , w h i l et h em a s t e r n o d ec o l l e c t st h er e s u l t st o g e t h e ra n df i n i s h e st h ep r o o f t h ee f f i c i e n c yo fp a r a l l e ls u c c e s - s i v ed i f f e r e n c es u b s t i t u t i o ni ss h o w nb ys e v e r a lb i gi n e q u a l i t i e s w ea l s ot e s tt h es p e e d u po f p a r a l l e lc o m p u t a t i o nf o rt h ev a s cc o n j e c t u r ew i t hs e v e nv a r i a b l e s ( 3 ) t h et o p o l o g i c a ls t r u c t u r eo fd i f f e r e n c es u b s t i t u t i o ni ss t u d i e di nd e t a i l w ep r e s e n t t h ei n e q u a l i t e sp r o v e db yd i f f e r e n c es u b s t i t u t i o ni saf i n i t e l yg e n e r a t e dc o n ea n dg i v et h e d e v s u b e x pa l g o r i t h mt oc a l c u l a t et h ee x t r e m a lr a y so fd i f f e r e n c es u b s t i t u t i o nc o n e 。t h e n w es h o wt h ee x p a n s i o no ft h i sc o n eb yu s i n gd i f f e r e n c es u b s t i t u t i o ns u c c e s s i v e l y f u r t h e r - m o r e ，w ec o m p a r ed i f f e r e n c es u b s t i t u t i o nw i t ha n o t h e ra l g o r i t h ms c h u rp a r t i t i o n ，w h i c hc a n p a r t i t i o nat e r n a r yp o s i t i v es e m i d e f i n i t eh o m o g e n e o u ss y m m e t r i cp o l y n o m i a li n t oa l i n e a r c o m b i n a t i o no ff i v ep o s i t i v es e m i d e f i n i t eb a s e s w es h o wt h a tf o ra n yt e r n a r yp o l y n o m i a l s w h o s ep o s i t i v es e m i - d e f i n i t e n e s sc a nb ep r o v e nb ys c h u rp a r t i t i o n ，i ta l s oc a nb ep r o v e nb y d i f f e r e n c es u b s t i t u t i o n ( 4 ) h e i l b r o n np r o b l e mf o rs e v e np o i n t s h e i l b r o n np r o b l e mi sa c l a s s i co n ei nt h ed i s c r e t e c o m b i n a t o r i a lg e o m e t r y , w h i l et h eh e i l b r o n np r o b l e mf o rs e v e np o i n t sh a sn ow h o l er e s u l t i n t h i st h e s i s ，w eg i v eap r o p e rm e t h o dw i t hr a n d o m l ym o n t ec a r l os e a r c hm e t h o da n di n t e r v a l a n a l y s i s t h r o u g hr a n d o m l ym o n t ec a r l os e a r c hm e t h o d ，w ep u ts e v e np o i n t si nt h eu n i t s q u a r er a n d o m l ya n ds e a r c ht h en u m e r i co p t i m a ls o l u t i o nb yt h en o n l i n e a rp r o g r a m m i n g f u n c t i o n so fm a t l a b a l t h o u g ht h er a n d o ms e a r c hh a su n c e r t a i n t y , w et r yt os e a r c hm i l l i o n v t i m e sa n dg e tt h eb e s tr e s u l t s t h i sm e t h o di ss i m p l eb u tc a nb ee x t e n d e df o ro t h e rs i m i l a r g e o m e t r yp r o b l e m se a s i l y t h e nw eu s es y m b o l i cc o m p u t a t i o na n di n t e r v a la n a l y s i st op r o v e t h eo p t i m a lv a l u ea n dp o i n t d i s t r i b u t i o ng r a p h a c c o r d i n gt ot h ep r o b l e mo ff i v ea n ds i x p o i n t s ，w et r a n s f e rt h eh e i l b r o n np r o b l e mf o rs e v e np o i n t si n t o4 5 6 4 2 7 n o n - l i n e a ro p t i m i z a t i o n p r o b l e m s w es o l v et h e s ep r o b l e m sb yp a r a l l e lc o m p u t a t i o no nt e nn o d e s w eg i v et h er e s u l t o fh e i l b r o n np r o b l e mf o rs e v e np o i n t si ni n t e r v a lf o r m ( 5 ) c o m p u t e ra l g e b r as y s t e m ( c a s ) i sa f u n d a m e n t a lb a c k b o n ef o rs y m b o l i cc o m p u - t a t i o na n da u t o m a t e dr e a s o n i n g t h e r ea r em a n ye x c e l l e n tc a s s ，w h i c hc a np r o v i d eg o o d i n t e r f a c ea n dh i g hp e r f o r m a n c ec o m p u t a t i o nf o rr e s e a r c h e r s i nt h i st h e s i s ，w ef i r s t l yi n t r o - d u c et h ec l u s t e rt a s km a n a g e m e n ts o f t w a r es g ea n dp a r a l l e lm e s s a g ep a s s i n gi n t e r f a c em p i w ea l s os h o ws e v e r a ld i f f e r e n tw a y st oe x p r e s sm a t h e m a t i cs y m b o l si nc o m p u t e r s t h e nw e d i s c u s sh o wt ob u i l dad i s t r i b u t e da n dh y b r i dc o m p u t i n ge n v i r o n m e n t ( h p p c a s ) t or e a l i z e t h ec o o p e r a t i o no fd i f f e r e n tc a s sa n da c h i e v eh i g h e rp e r f o r m a n c et h r o u g hu s i n ge x t e r n a l c a l l i n gc o m m u n i c a t i o ni n t e r f a c ea n di n t e g r a t i n gt h ep a r a l l e ll i b r a r ya n dc l u s t e rm a n a g e m e n t s o f t w a r e i nh p p c a s , e a c hj o bi ss u b m i t t e dt oaq u e u e ，a s k e dc o m p u t a t i o n a lr e s o u r c e sb y s l o ta t t r i b u t ea n ds c h e d u l e db a s e do ni t st i c k e tv a l u e ，w h i c hd e n o t et h ep r i o r i t yo fj o b f i - n a l l y , w ev e r i f yt h ee f f i c i e n c yo fh p p c a sb yt h ec a l c u l a t i o no fp a r a l l e ls u c c e s s i v ed i f f e r e n c e s u b s t i t u t i o n f r o mt h ea b o v ew o r k ，w ec a na r r i v et h er e s u l tt h a ts y m b o l i cc o m p u t a t i o nc a nb e n e f i tf r o m p a r a l l e lc o m p u t a t i o ni nt h ec a l c u l a t i o np r o c e s s t h r o u g hp a r a l l e lc o m p u t a t i o n ，i tc a nb a l a n c e t h ep e a km e m o r yc o n s u m p t i o nt om a n yn o d e s ，a l l e v i a t et h et r o u b l eo fm e m o r ys c a r c i t y i ta l s o d i s t r i b u t e st h ec a l c u l a t i v et a s k st om a n yn o d e s ，a n dd oc a l c u l a t i o nc o n c u r r e n t l yt oi m p r o v e t h ep r o c e s s q u i c k l ya n de a s i l y w et h i n kp a r a l l e lc o m p u t a t i o nw i l lm a k es y m b o l i cc o m p u t a t i o n m o r ep o w e r f u la n dm i g h t f u l k e yw o r d s ：s y m b o l i cc o m p u a t i o n ；p a r a l l e lc o m p u a t i o n ；d e t e r m i n a n to fp o l y n o m i a l m a t r i x ；r e s u l t a n t ；i n e q u a l i t yp r o v i n g ；d i f f e r e n c es u b s t i t u t i o n ；h e i b r o n np r o b l e mf o r s e v e np o i n t s ；s g e ；m p i ；m a t h m l ；m a p l e ；m a t l a b v i 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，进行的研究工作及取得 的研究成果除文中已经注明引用的内容外，本论文的研究成果不包含任何他人撰写过的 己公开发表或未公开发表的研究成果，对本文所涉及的研究工作做出重要贡献的个人和集 体，均已在文中以明确的方式标明并表示谢意本学位论文原创性声明的法律责任由本人 承担 学位论文作者签名：像庭秀 幽谚年月2 日 学位论文使用授权声明 本人完全了解华东师范大学有关收集、保存、使用学位论文的规定同意如下各项内 容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保留学位论文并向国家主 管部门或其指定机构送交论文的电子版和纸质版，并采用影印、缩印、扫描、数字化和其 他手段保存论文；有权将学位论文用于非赢利目的的少量复制或全部内容用于学术活动并 允许论文进入学校图书馆被查阅：有权将学位论文的内容编入有关数据库进行检索；有权 将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用本规定 学位论文作者签名：7 ；、艮囊 抽亨年月z 日 导师签名： 押多 2 _ 惦月z e t 第一章绪论弟一早瑁了匕 1 1 符号计算与计算机代数 在数学发展的历史长河中，“计算”始终都扮演着非常重要的角色。但是人类的计算 能力往往受制于计算工具，早期的计算主要是靠人的大脑再加上一些简单的计算工具来完 成，计算效率低，可靠性也很差。以公理化命题推导为主要手段的非构造性数学逐渐占据 数学发展的主流。n - - 十世纪中叶，计算机的出现大大地提高了人类的计算能力，从而促 进了以计算为主要目标的构造性数学的迅猛发展，也催生了一个新的分支：计算机数学， 研究在计算机中以实现数学计算的理论与算法为目的的数学分支。研究人员已经开始用计 算机处理一些复杂的数学问题。其中具有开创性的工作是定理自动证明。1 9 5 8 年，美籍逻 辑学家王浩在定理自动证明中取得的重要进展。他的程序在i b m t 0 4 计算机上用不n 5 分钟 的时间证明了数学原理中“命题演算 的全部2 2 0 条定理。1 9 7 6 年6 月，美国伊利诺斯 大学的两位数学家哈肯( w h a k e n ) 和肯尼斯阿佩尔( k a p p l e ) 利用计算机成功证明了 困扰世界数学界长达1 0 0 多年的“四色定理，。这些工作充分表明了计算机处理不平凡数学 问题是切实可行的，特别是计算机数学可以用来解决一些具有大数据量的不易人工求解的 数学问题。计算机数学是一个以构造性数学为核心，以计算机实现为目标，以实用的算法 为研究内容，以实用程序或软件为成果的全新的研究领域。 根据数学工程和研究的主要内容，计算机数学可以分为数值计算和符号计算。数值 计算主要处理的对象是纯数值，例如求函数的值，方程的数值解，被广泛应用到天气预 报、油藏模拟等领域，但是在计算过程中往往根据精度要求对数值进行截断而导致计算 误差 1 1 3 1 。而符号计算侧重于符号在计算机中的表示、推理和运算过程，包括数值、多项 式、函数、几何图形、逻辑公式等。符号计算的最主要特点是整个计算过程都是精确的， 没有舍入误差，因此已广泛应用于计算精度要求高的场合 1 2 3 1 。它有别于通常的数值计 算。虽然数值计算在许多领域内被广泛应用，但是在计算过程中往往舍弃尾数，采用近似 值。而我们知道细微的误差也可能会给后续计算带来很大的影响。最著名的例子是求方 2 0 程兀( z t ) = o 的根。如果对x 的1 9 次项系数做微小扰动，如加上1 0 吨o ，则方程将出现虚 i = l 根。由于数值计算的不精确性和不稳定性，导致计算过程容易出现误差甚至失败，因此准 确计算在某些计算精度高的领域显得非常重要。而符号计算能够完整保证计算过程的准确 性，已经在很多领域内已经广泛应用，如生命科学 4 3 】、汽车、化i 4 4 ，4 5 等。 计算机代数是符号计算的一个基础且重要分支，它以现代计算机为工具，研究可代 数化的数学对象。计算机代数的主要研究内容是符号与代数计算，代数算法的设计分 析、实现及应用构成了计算机代数的主要研究内容。计算机代数统( c o m p u t e ra l g e b r a s y s t e m ，c a s ) 是实现以上基础代数算法的集成软件。利用计算机符号计算系统对交换代 数与代数几何中的可计算问题以及有关应用进行研究，形成了计算代数这个蓬勃发展的新 方向。计算机代数作为新的计算工具除在数学自身，如定理证明与方程求解等方面的应用 外，还在物理、天体力学、化学、生物生态、机械学、机器人设计、计算机视觉、计算机 辅助图形设计、航空航天、编码理论、密码技术等方面有着广泛的应用。 代数计算冗长繁复，传统计算方法费时费力，且易出错，因而不能进行大 规模的计算。计算机代数系统将各种基本的代数理论算法化、程序化后转化为 具体程序。计算机代数通过计算机代数系统进行数学计算1 2 1 。我们熟悉的软件 有：m a t l a b 、m a p l e 、m a t h e m a t i c a 、r e d u c e 、d e r i v e 、m a g m a 、g a p 、a x i o m 。 计算机代数系统的优越性主要在于它能够进行大规模的代数运算。通常我们用笔和纸进行 代数运算只能处理符号较少的算式，当算式的符号上升到百位数后，手工计算便成为可能 而不可行的事，主要原因在于做大量符号运算时，很容易出错，并且缺乏足够的耐心。当 算式的符号个数上升到四位数后，手工计算便成为不可能的事，这时用计算机代数系统进 行运算就可以做到准确、快捷、有效。 近2 0 年来，利用符号计算的研究领域的主要突破性工作有：b u c h b e r g e r 关于多变多项 式理想的g r 6 b n e r 基理论 6 0 1 。这一理论是计算交换代数和计算代数几何的核心和许多应 用的基础。在这一领域的重要理论还有：吴方法和各种方程组三角化方法；著名的l l l 算 法，它在多项式分解和密码学中起着重要作用；分解大整数的椭圆曲线算法e c m ；处理实 闭域理论的柱型代数分解方法c a d ；求解多变多项式方程组数值解的同伦方法h p c ；计算 多项式方程组解的个数的多面体方法和同伦法等等。 此外，一批专业化的符号计算学术机构已在世界各地纷纷成立，如奥地s u j o h a n n e s k e p l e r 大学的r i s c l i n z 符号计算研究所，中国科学院数学机械化研究中心等等，培养了 2 一批符号计算的研究人员。一些符号计算软件m a p l e 、m a t h e m a t i c a 、m a g m a 等被研 制出来，并且已经在数学与工程领域被广泛使用。同时，符号计算计算机代数方向已出 版了专门的国际学术刊物“j o u r n a lo fs y m b o l i cc o m p u t a t i o n ，专门刊登了这方面的论 文；s p r i n g e r 的丛书“l e c t u r en o t e si nc o m p u t e rs c i e n c e ”中陆续出版了不少计算机代数 的专集；自2 0 世纪9 0 年代起，已陆续出版了计算交换代数、计算代数几何、算法代数等方 面的专著f 3 0 ，4 9 ，8 0 ，8 1 ，2 0 ，4 6 ，2 1 ，1 6 】。另外，国际上每年组织召开多个和符号计算相关 的国际会议，其中最主要的是由a c m 支持的i s s a c ( i n t e r n a t i o n a ls y m p o s i u mo ns y m b o l i c a n da l g e b r a i cc o m p u t a t i o n ) 会议。还有，在亚洲范围内召开的a s c m ( a s i a ns y m p o s i u mo f t e c h n o l o g yo nm a t h e m a t i c s ) 和a t c m ( a s i a nt e c h n o l o g yc o n f e r e n c ei nm a t h e m a t i c s ) 也已经 成为符号计算领域重要的学术盛会。 从1 9 8 0 年以来，解( 微分) 代数多项式方程组已成为国际符号计算界的热点，其主要 方法是g 硒6 佗e 堪方法和吴方法，其中吴方法是我国著名数学家吴文俊先生创立的。在我 国，“数学机械化”是吴先生在七十年代末就开始倡导的一个研究领域 2 1 】，是符号计算 研究的重要内容。吴方法是数学机械化的核心方法。数学机械化是脑力劳动机械化在数学 科学的学术实践。数学机械化不仅是数学研究的实质性进展，也为很多高科技问题的解决 提供了有力的工具。正如吴先生所论述：不论是机器代替体力劳动，或者是计算机代替某 种脑力劳动，其所以成为可能，关键在于所需代替的劳动已经“机械化”，要求在运算和 证明过程中，每前进一步之后，都有一个确定的、必须选择的下一步，这样沿着一条有规 律的刻板的道路，一直达到结论f 2 1 】j 应用吴先生的特征列方法已在许多高科技领域获得 了一批理论成果，解决了尖端技术产业中的许多实际问题。其中包括曲面造型，机器人 位置分析、几何设计、计算机视觉、智能c a d 、信息安全和数字图象的高速高保真传输 等 2 1 ，1 9 】。 1 2 并行计算 当代科学技术的快速发展对大规模科研和工程计算提出极高的具有挑战性的要求。虽 然计算机处理器已经按照摩尔定律每十八个月翻一番的速度增长，但是还是无法满足大规 模问题和复杂系统的实际计算要求。研究人员开始寻求一种利用多个处理器进行协同并行 3 计算以提高计算效率的方法，将一个大的问题分解成许多个小的子任务，并将这些子任务 映射到各个独立的处理器工作。这种方法就是并行计算方法。并行计算的最大优点就是利 用计算任务执行并发性，节省整体计算时间，提高计算效率。 并行计算通常将一个大的任务分解若干个小的子任务并分配给其它处理器协同执行， 即执行“d i v i d e c o n q u e r ”策略 3 2 ，3 5 】。在这个过程中，粒度，即子任务的具体大小，是 非常重要的。通常并行计算方法主要解决两种任务。第一类是在串行计算机上需要运行很 长时间的任务。并行计算可以利用分解策略将大任务分解成若干个较小的子任务，并在多 个处理器上同时进行子任务的执行。这类任务的主要瓶颈是处理器的计算速度。第二类是 在单台串行计算机上无法计算的任务。无法计算的主要原因是单台计算机的内存容量有 限，无法同时容纳计算所需要的数据量。虽然某些虚拟内存解决方法可以在一定程度上缓 解内存紧张需