计算机代数(ComputerAlgebra)在很多时候又被广义地理解为“符号计算”(SymbolicComputation),成为与“数值计算”(NumericalComputation)相对的概念.“符号”的运算在这里代替了“数”的运算.这是一种智能化的计算.符号可以代表整数、有理数、实数和复数,也可以代表多项式、函数,还可以代表数学结构,如集合、群、环、代数等.我们在学习和研究中用笔和纸进行的数学运算多为符号运算.
利用计算机代数,我们可以完成许多不可思议的事情,例如可以对代数方程组进行精确的求解,对多项式进行因子分解,对复杂代数表达式进行化简归约,对函数进行符号积分(求出原函数),对微分方程求出精确解等.
传统的代数计算冗长繁杂,而现代的计算机技术为大型的符号计算提供了可能性.关键的问题就在于如何把抽象的代数理论算法化,使其高效地处理形形色色的代数问题.强大的计算机代数系统不仅是各类工程技术的助手,对纯粹科学研究也起着不可忽略的推动作用.
经过数十年的发展,在国外已经形成了诸如WolframResearch1, Maplesoft2 等巨型的商业软件公司,其产品具有可观的经济效益;其他一些研究者的专用系统开发也具有了相当的规模.然而,在我们国内,科学软件领域则远远落后于发达国家,能够与国外产品相抗衡的通用计算机代数系统还暂时没有出现.而另一方面,国内对科学软件的需求量却是巨大的,昂贵的进口产品意味着大量的科研、工程经费的无奈外流.从某种意义上来说,对国外系统的依赖对国家信息安全也有着潜在的威胁.
在我们看来,造成这种状况的原因一方面是由于科学软件的复杂性,另一方面则反映了国内创新能力的缺乏.就这一点来说,国内的大环境是一个很重要的因素:
盗版冲击.在国内盗版软件获取容易,而大型的科学软件开发却需要长期、大量的投入,
. 其复杂程度及难以预料的经济前景使得企业少有问津;知识结构缺欠.在中国往往出现这种情况:软件写得顺手的人,未必有很强的科学计算
. 背景,而科学背景强的人又没有较高的计算机和软件水平,这使得科学软件的开发难以进行;
少有“不切实际的幻想”.由于科学软件的复杂程度,企业少有问津,单独的科研人员也
. 不得不认为完成这样一件工作是“不切实际的幻想”.然而我们回顾WolframResearch,Maplesoft,Mathworks等大公司的发展道路,无不是从一个人或几个人的的微薄之力逐渐发展到现在令人赞叹的规模.或许“不切实际的幻想”正是创新氛围的一个绝佳体现吧!
尽管我们力量渺小,但对这种状况也不愿意置若罔闻.清华大学作为一所综合性大学,众多学子具有较强综合能力,也理应在此领域有所作为.我们利用自身的数学基础与应用背景,整理出一份较为完整的计算机代数理论文档,进行较为完整的系统设计,并实现一个计算机代数系统核心maTHμ1 .希望在此过程中也能开阔我们的眼界,提高我们自身的理论和技术水平,为更进一步的工作打下良好基础.
这本《计算机代数系统的数学原理》,作为maTHμ系统的理论文档,是maTHμ项目组成员通过近一年半时间集体整理撰写的成果.计算机代数理论方面的中文文献稀缺.即使在英文文献中,能够足以支撑一个通用计算机代数系统的系统论述也较为少见,更多的内容散见在专著、博士论文及专业期刊中.花大力气整理文档的初衷十分简单:理论不清,则后续的设计与开发阶段根本无法进行,更何况计算机代数理论本身就复杂而相互交织.举例来说,求微分方程的符号解需要符号积分的支持,而有理函数符号积分需要借助精确线性代数、多项式因子分解、代数方程组求解等算法,其中Z[x]上的多项式因子分解依赖有限域上的因子分解,从而需要数论中模算法的支持,而数论算法又建立在任意精度的快速运算上.
本书包含高精度运算,数论,数学常数,精确线性代数,多项式,方程求解,符号极限,符号求和,符号积分,微分方程符号解等十个大部分,涵盖了构建计算机代数系统的最基础也是最重要的内容.整个书稿的内容组织也大体符合构建计算机代数系统的逻辑顺序.许多内容是第一次被系统地整理出现在中文文献中,在一些领域也追踪到了最新进展.其中第1,5,14,15章由张翔撰写,第2~4,16,17章由李超撰写,第6章由张龙撰写,第7~13 章由阮威撰写. 李超负责统筹全书并撰写了附录.
本书中大部分算法都有理论推导,努力做到了自成体系并力求阐明各种方法背后的想法.对于若干深刻的结果(如Hilbert零点定理,Liouville定理,Lie-Kolchin定理等),鉴于篇幅和目的,我们选择只给出相关参考文献而略去了严格证明.
本书中的部分算法已经在maTHμ1.0版的内核中实现.计算机代数系统maTHμ项目在2009年清华大学第二十七届“挑战杯”课外学术科技竞赛中,经过4轮评审,最终在344件作品中脱颖而出,获得了特等奖的第一名.2009年11月,项目代表清华大学参加了两年一度的全
国“挑战杯”竞赛并获特等奖.项目未来的长期发展规划也已经得到了学校的大力支持.项目团队感受到了来自各方的鼓励与期望,希望能踏实地继续努力工作.在理论文档部分,除了继续丰富与完善呈现在这里的内容,其他一些我们认为同样重要的主题也正在整理中,包括初等与特殊函数的任意精度计算、组合函数、代数函数积分、更一般的符号求和理论、表达式化简等.
两年过去,maTHμ从无到有,一路走来.项目团队最为欣慰的事莫过于看着我们的“幻想”正一点点变为现实.作者感谢maTHμ项目指导老师饶辉和法国教授JacquesPeyri`ere对项目的精心指导.感谢清华大学数学科学系李建国,白峰杉,李津,扈志明等老师,校团委阳波老师,校科创中心及校科协对项目提供的支持.感谢中科院数学机械化实验室李子明老师的有益讨论.清华大学数学科学系卢旭光老师和清华大学出版社刘颖老师在本书出版过程中付出了辛勤劳动,在此一并表示感谢.
maTHμ Project Group maTHmU@gmail. com
2009年11月17日于清华园