何谓CA

计算机代数（Computer Algebra，简称CA）是计算机科学百花园中的一枝新蕾，它又称为计算机公式处理或符号处理等。它与通常大家所熟悉的数值计算不同，数值计算的目的是在于更有效地使用计算机，以求得各类数学问题的满足一定精度的数值解；而CA蹙研究使用计算机对公式直接进行处理的理论、算法和系统的计算机科学的一个分支，利用CA系统可以获得对公式的处理结果或各类数学问题的解析解。由于它不仅可广泛地应用于电路理论、自动控制系统、定理自动证明、人工智能、生物学、化学、天体力学、广义相对论等各个领域，而且对于数学和物理学等理论研究也产生了深刻的影响，从而在国际上受到了高度的重视，但在我国CA的研究和应用还不够普遍，是值得我们充分重视和急起直追的一个方向。

CA的处理对象是数学公式，例如：数学表达式的化简，多项式因式分解，求两个多项式的最大公因式，符号地进行矩阵代数运算，求代数方程组的解的公式，求函数的微分与不定积分，求微分方程或积分方程的解析解，证明数学恒等式等，从而使计算机的应用领域超过了数值计算的传统范畴，开辟了把计算机应用于非数值计算的新天地。CA是一门数学理论和计算机技术紧密结合、综合性较强的学科，有关CA的理论涉及到数学的许多分支，特别是数论、近世代数等离散数学的领域。这些数学分支虽然原属于纯粹数学，抽象性较强，但它们一旦与计算机技术相结合，便又重新焕发出青春，产生了强大的生命力。将抽象代数应用于计算机科学，还必须要研究使用计算机进行公式处理的各种有效算法，需要掌握程序设计语言、数据结构、编译技术、算法设计与分析等知识。为了实现公式的计算机处理，目前已从研究局部的、个别的课题，发展到研究计算机公式处理系统，例如REDUCE2，SCRATCHPAD等系统已实际使用。借助于这些系统解决了许多实际应用课题，展现出光辉灿烂的前景。

CA的发展

利用计算机进行公式处理的尝试，最早可追溯到1953年，凯利曼安（H. G. Kahrimanian）和诺兰（J. Nolan）首先使用数字计算机进行微分解析运算。六十年代初，麻省理工学院的赛（SAING）和邢（SIN）在计算上做了不定积分的实验，从而使大学低年级中90%以上的积分问题可以用计算机来求解。在日本，自1969年以后，渡邊隼郎以常微分方程为对象的研究取得了新的成果。

自1971年开始，每五年召开一次国际会议，专门交流CA方面的研究成果，其间，欧洲还另行召开了两次国际会议，一次是1974年在斯德哥尔摩召开的，另一次是在马赛召开的。第二届世界性的国际会议在纽约召开。然而，当时要想探索公式处理的奥秘，必须要使用高速的、具有巨大存贮容量的大型计算机。

首先破除这个传统概念的是默马思（Mumath）（1978），他使用超小型的微型计算机进行公式处理，取得了预想不到的巨大成功，此后，许多人使用小型或微型计算机进行公式处理均取得了成果，如日本的渡邊隼郎对微分方程的公式处理颇有成效；法国的佩雷夫（P. Painleve）对特殊函数的研究成果在物理学中获得了具体应用、美国数学家英斯（hoe）对佩雷夫的方法又进行了某些修正。因此，自1978年开始，CA迅速地实用化、大众化。这一点从1979年召开的欧洲国际会议录可以清楚地看出，会上讨论的中心议题就是如何使用小型计算机进行公式处理的问题。

CA之所以自1978年以后逐渐走上实用化，究其原因，首先是因为微电子技术的发展，提供了集成电路及廉价的大容量存贮器，从而使计算机的速度和容量大幅度提高，这对于公式处理是十分必要的；其次是高效率算法的研究与开发以及经验的积累。这样，CA作为计算机科学中的新分支期待着人们去进一步开发。

CA的实例

下面给出一些近年来在计算机代数方面研究开发的实例和典型系统。

实例1   1980年8月，在贝克莱的加利福尼亚大学，召开了第四届国际数学教育学会议（IVICME），会上有七省理工学院的MACSMY在VAX-11/780计算机上实现的VAXYMA公式处理系统的演示和介绍。借助于该系统可以进行数的素因数分析，求函数的微分和不定积分，多项式的因式分解，函数在某点的泰勒（Taylor）展开，公式变形，范德蒙特（Vandermonde）行列式的展开，根据罗德林斯（Rodrignes）公式求勒让德（Legendre）多项式，解常微分方程组及求拉普拉斯变换和反变换等。上述这些公式处理均只需几十至几百毫秒便可以完成，如果由人来处理的话，即使花费几百倍的时间恐怕也难以完成。

实例2   公式处理是麻省理工学院最早着手进行研究的，而近年来以诺曼（Norman）为首的剑桥大学小组把它用于天体力学，首先获得了实际效果。特别是他们应用基于P进制展开的亨塞（Hensel）引理，使得整系数多项式的因式分解获得了较大的进展。对于木定积分，包含有二层根号形式的例子也已成功。当使用先求函数的不定积分再用牛顿 - 莱布尼兹公式计算定积分时，系统还能处理积分路径内部包含极点的情况，避免了人工计算时也常常会发生的错误。此外，系统还能够判定给出的两个初等函数是否相等。

实例3   几何定理的机械证明。关于初等几何定理的机械证明，1960年日本的西村敏夫曾做过一些研究。最近，我国中国科学院系统科学研究所的吴文俊教授做了许多出色的工作，受到了国际上的赞誉。如果是笛卡尔坐标几何，从原理上讲初等几何的全部定理应该都能用公式处理来证明。实际上，泰斯基（Tarski）等人已经证明：对于希尔伯特公理系统，能够不使用顺序公理的定理是可判定的，并已由薛登堡（Seidenberg）给出了可实行的算法。此外，若把真伪不明的命题作为几何定理机械证明系统的输入，则可以判定该命题的真伪，从而对于新定理的发现提供了可能性，日本的一松信于1980年6月提出的关于帕斯卡（Pascal）六边形的“新定理”，就是用这种方法发现的。

实例4   REDUCE2系统。这是一个比较成熟、功能较齐备的公式处理系统，它作为一种计算机代数语言与通常的数值计算用的ALGOL，FORTRAN语言等有很大的区别。

首先，REDUCE2可以进行位意位整数的准确运算，并可用两个整数相除来表示有理数，故也可以进行有理数的准确运算。对于变量，不仅有整型和实型，而且还有纯量型，对于纯量型的变量，能以符号数学表达式为其值。变量也可以不经说明而使用，在赋值前为自由状态并称为未定元，以变量名自身为其值；在赋值后为受束状态并为受束元，以赋予的表达式为其值。含有未定元的表达式是一个符号数学表达式，不含未定元的表达式的结果是一个数。因此，未定元是REDUCE2的关键性概念之一。

另外，REDUCE2具有微分运算符DF和积分运算符INT，用来计算函数的微分和不定积分。例如：若要计算

REDUCE2的程序由命令构成，计算机执行REDUCE2命令。命令可以是：表达式或者是赋值语句、条件语句、循环语句、转向语句、复合语句、返回语句等后接结束符组成，也可以是常态命令。在常态命令中，代换命令十分重要，它是贮存公式变换规则的工具，因此它是关键的命令之一。

公式处理系统（例如REDUCE2）是提供给用户使用的工具，其功能的实现是由于在利用大量的数学理论的基础上，研究了各种公式处理算法，从而构成了公式处理语言的编译程序。这样，我们可以利用计算机推导公式，摆脱了公式演绎的手工操作，使计算机的应用进入了一个崭新的时代。

CA的应用

应用在CA中起着重要的作用。许多系统解决了大量的应用课题，许多系统又在解决应用课题的过程中得到完善和提高。

CA的应用领域繁多。从射影几何那样的纯粹数学到机器人手臂运动那样的技术科学；从化学元素的微量分析到天体力学中星球轨道的宏观计算等等，CA系统都做出了杰出的贡献，目前已经建立了许多CA系统，并且功能越来越完备，使用越来越方便，可靠性越来越提高。例如，苏联MIR-2型计算机上的ANALITIK系统，发现了格拉斯坦（Gradshteyn）和吕齐克（Ryzhik）积分表苏联较新版本中的若干印刷错误，下面，我们举一些在各个领域成功地应用CA的具有代表性的例子。

生物学和化学以前是较少使用计算机的领域，而近来使用系统MACSYMA成功地完成了生物学中当RNA按特殊配对规律排列时它的次级结构的分析；在化学中，对蛋白质序列中各种氨基酸之间关系的统计研究，需要符号地处理树，这类研究也属于这一领域；在有机化学中，CA可以应用于对WLN（Wiswerser Linear Notation）码的线性表示法的译码技术。

物理学是较早地应用CA的领域，经常使用的系统有REDUCE2、SCHOONSCNIP和ASHMEDAI等。为了适应高能物理研究的需要，人们要在原系统中再增加一些软件包，以扩大狄拉克代败、模型匹配和多项式的处理能力。其中微扰级数的展开、费曼积分的计算和狄拉克矩阵的处理等大量的公式推导和计算的各个步骤都可由计算机来实现。以上运算，即使在比较复杂的情况下，也只需要几分钟便可完成。然而，如果手工来计算的话，除非极简单的情况，几乎是不可能的。

在天体力学中，有一个应用CA的经典例子广为流传，这就是关于月球轨道的计算。在计算中需要考虑地球的非球性、黄道的倾斜以及太阳的影响等许多物理效应，仅仅是描述物理体系的哈密尔顿量就需要书写许多页，而每一项需要多达600个变换。在1867年，狄劳奈（Delaunay）发表了他的计算结果，这是他花费了20年的时间用手工完成的。最近，狄普里特（Deprit）等人利用罗姆（Rom）的CA系统在小型计算机上对此进行了复算，仅用了20小时，结果表明，狄劳奈给出的结果直到第九级都是正确的，只有在第七级上有一个例外，这不仅表明了CA的威力，而且也是对狄劳奈所付出的艰辛劳动的一种称颂，这种方法还可以推广到人造卫星的轨道计算和地球重力场物理模型的研究等天体力学的其他领域。

在广义相对论中广泛地使用着许多CA系统，例如ALTRAN、FORMAC、SYMBAL、REDUCE、MACSYMA、CAMAL、ALAM、LAM、CLAM和SHEEP等。这些系统在计算度规张量、黎曼张量、里西张量和里西标量、爱因斯坦张量等方面发挥着重要的作用。如果我们要考虑对角度规或者非对角度规，在一个四维空间里的里西张量，几乎有一万个对角项和多达一万三千个非对角项。显然，在这个领域如果没有CA系统将会何等的困难。

在数学这个领域中，CA的应用和理论工作是密切结合在一起在数论的研究中很早就已经使用CA系统了，这是因为数论中的计算问题往往需要进行冗长的推导。例如，一个实代数数的连分数展开的计算，在实代数域中的有理运算和符号的确定，在实代数域中最大序模的确定以及一个方程的可分域的伽罗华群的构成等。最近，挪威的伯杰（Bergen）大学制定了一个雄心勃勃的计划，试图利用MACSYMA系统研究在射影几何中应用CA的可行性，霍姆（Holme）的报告表明，在这方面的研究已经获得了进展。此外，在特殊函数、常微分方程、有限代数、有限域、环和群等研究领域，使用CA系统为辅助工具也十分普遍。其中毛勒（Maurer）还试图开发一些工具来向大学生讲授近世代数。

对于计算机科学自身而言，也广泛地应用了CA的方法和定理。例如，古德（Good）利用中国孙子剩余定理来计算离散傅利叶变换（DFT），并由威诺格拉德（Winograd）推广到n（n不是一个质数的幂）点的情况。孙子剩余定理对于代数编码理论的研究也十分有用，可以用来研究处理密码字。此外，CA还可以应用于程序正确性的证明，伦敦（London）和缪叟（Musser）等人基于归纳断言利用REDUCE系统实现了一个交互程序验证系统。有人还利用MACSYMA系统来分析计算机联机系统的可靠性。

目前，计算机代数的理论和系统虽然已取得了迅速的进展和广泛的应用，但是与理想的程度还相差甚远。特别是在国内研究工作尚不够普遍，更缺乏可供实用的系统。展望未来，前程似锦。人们正致力于研究出使用简单化的更加实用的公式处理系统。赫恩（Hearn）曾提出了“个人代数机器”（“Personal algebra machine”）的设想。如果能解决高速地进行公式处理的专用装置的话，计算机代数的理论和方法必将会更迅速的发展，并将在各个领域结出硕果。