計算機代數

本页使用了标题或全文手工转换
维基百科,自由的百科全书
用计算机代数系统公理代数函数进行符号积分

数学计算机科学中,[1]计算机代数符号计算代数计算,是研究、开发用于操作表达式数学对象算法软件的科学领域。这通常被视为是运算科学的一个子领域,但运算科学一般基于近似浮点数数值计算,而符号计算则使用含变量的表达式进行精确计算,其中变量没有赋值。 执行符号计算的软件系统称为计算机代数系统,“系统”暗示了软件的复杂性,其中至少包括一种在计算机中表示数学数据的方法、一种编程语言(通常异于用于实现的语言)、一种专门的内存管理器、一套供输入输出表达式的用户界面、一大套用于通常运算的子程序,如表达式简化、能实现链式法则多项式因式分解不定积分等等的求导算法。

计算机代数被广泛用于数学实验、设计数值程序所用的公式。纯数值方法失效时,计算机代数也可用于完整的科学计算,这见于公开密钥加密和一些非线性问题。

术语

有些学者区分“计算机代数”(computer algebra)与“符号计算”(symbolic computation),后者指数学公式计算之外的符号计算。有人则用“符号计算”表示计算机科学方面的内容,而用“计算机代数”表示数学方面的内容。[2]

科学界

目前还没有计算机代数领域的专门学会,这一职能由计算机协会的特别兴趣小组(special interest group)SIGSAM承担。[3]

计算机代数领域有多个年会,最重要的是由SIGSAM定期主办的ISSAC(符号与代数计算国际研讨会)。[4]

有几种专门研究计算机代数的期刊,其中最重要的一种是由Bruno Buchberger于1985年创办的《符号计算》(Journal of Symbolic Computation)。[5]其他一些期刊也定期发表计算机代数方面的文章。[6]

计算机科学

数据表示

由于数值软件在进行数值计算时的效率很高,因此在计算机代数中,通常用精确数据进行精确计算。这意味着即使输出规模很小,计算过程的中间数据也可能不可预测地增长,这种行为称为表达式膨胀(expression swell)。为解决这问题,数据表示和处理算法中有各种各样的方法。

数字

数值计算最常用的数字系统是浮点数和大小固定的整数。由于表达式膨胀,这些系统都不便于计算机代数。[7]

因此,计算机代数使用的基数是数学整数,通常用某个底数(一般是机器允许的最大底数)的无界有符序列表示。从整数可以定义有理数

为高效算术运算编程是一项艰巨的任务,因此大多数免费的计算机代数系统和商业系统,如MathematicaMaple都使用GMP库,它也因此成为事实上的标准。

表达式

表达式(8 − 6) × (3 + 1)LISP树形式,来自1985年的一篇硕士论文。[8]

数字变量外,每个表达式都可看做是跟着操作数序列的算符。在计算机代数软件中,表达式通常都这样表示,许多看似不是表达式的东西都可以这样表示和操作,非常灵活。例如,方程是以“=”为算符的表达式,矩阵可表为以“矩阵”为算符、行为操作数的表达式。

连程序也可以看做是以“过程”为算符、含至少两个操作数(参数列表与内容)的表达式,内容也是以“正文”为算符、以指令为操作数的表达式。反过来,表达式也可以看成程序:a + b可看做加法运算程序,参数是ab。执行这个程序即对给定值的ab表达式求值;若无给定值,则求值结果就是输入。

这种“延迟求值”在计算机代数中是最基本的。例如,等式中的“=”也是等式检验程序的名称:通常,等式求值结果仍是等式,但进行检验时,无论是用户通过“求布尔值”命令提出明确要求,还是系统在程序内部启动的自动检验,都会执行求值为布尔值的结果。

由于表达式操作数的规模无法预测,而且在过程中可能变化,因此操作数序列通常用指针序列(如Macsyma)或哈希表元素序列(如Maple)。

简化

在表达式上直接应用关于x求导基本规则,可得

一般来说,我们需要比这更简单的表达式,需要简化。

这一般通过重写逻辑完成。[9]有几类重写逻辑值得考虑,最简单的是总要缩减表达式,例如EE → 0sin(0) → 0。它们被系统地用于计算机代数系统。

加法、乘法这种有结合律的运算的混合会带来困难。处理结合运算的标准方法是,考虑其操作数是任意的,即将a + b + c表示为"+"(a, b, c)。因此a + (b + c)(a + b) + c 都能简化为"+"(a, b, c),展示为a + b + c。对于ab + c这样的表达式,最简单的办法是系统地将EEFE/F分别改写为(−1)⋅EE + (−1)⋅FEF−1。换句话说,表达式的内部表示中,数字的表示没有减法、除法或一元负号。

加法和乘法的交换律也是一个难点。问题在于如何快速识别同类项。对很长的和或积来说,测试每对项的成本都很高。Macsyma排序了和与积的操作数,将同类项放在连续位置上,这样就可以轻松检测出来。Maple则使用了散列函数,输入同类项时会产生碰撞,由此可以立即合并。这样,计算中多次出现的子式就能被立即识别,并只储存一次,这样就避免了重复操作,从而节省内存并加快计算速度。

部分重写规则有时会增加表达式的大小,有些会减小,例如分配律三角恒等式。具体来说,分配律允许。这类重写规则没有很好的决策方式,一般交给用户决定。实现分配的计算机函数通常叫做“展开”,反向则是“因式分解”,需要一种非平凡算法,因此是计算机代数系统的一个关键功能。

数学

在计算机中处理表达式时会出现一些基本数学问题。我们主要考虑多元有理函数,这不是严格的限制,因为表达式中出现的无理函数一旦被简化,通常都会被视为新的不定项,例如

视为组成的多项式。

等式

表达式而言,有两种等价关系。语法相等指在计算机中的表示相等,这在程序中很容易测试;语义相等指两个表达式表示相同的数学对象,如

理查森定理可知,若表达式中允许指数或对数,便可能不存在算法可判断代表数字的的两式是否语义相等。因此,只能对多项式有理函数等部分表达式进行(语义)等价测试。

要测试两式是否登记爱,通常都不用特别设计算法,而是将表达式置于某个规范形中,或将差置于标准形中,再测试结果的语义等价。

在计算机代数中,“规范形”与“标准形”不是同义词。[10]“规范形”(canonical form)是指只有语法相等时才语义相等;“标准形”(normal form)是指只有语法上为0时,才在语义上为0.换句话说,0在标准形表达式中有唯一形式。

标准形是计算机代数的首选,有以下几个原因。首先,规范形的计算成本可能更高。例如,求多项式规范形必须要展开每个积,而标准形不需要(下详)。其次,与含根式的表达式类似,规范形(如果存在)取决于一些任意的选择,对于独立计算的两式可能是不同的。这就使得规范形的使用变得不切实际。

历史

计算机代数起源于约1970年,当人们首次将闻名已久的算法应用于计算机时发现其效率非常低。[11]因此,研究者的主要工作是重新应用经典代数,以使其生效,并构造实现它们的高效算法。一个典型例子是计算多项式最大公约数,是简化分式必须的。令人惊讶的是,经典的辗转相除法对无穷域上的多项式效率很低,因此需要开发新的算法。线性代数的经典算法也如此。

另见

参考文献

  1. ^ ACM Association in computer algebra. [2023-09-16]. (原始内容存档于2023-07-30). 
  2. ^ Watt, Stephen M. Making Computer Algebra More Symbolic (Invited) (PDF). Transgressive Computing 2006: A conference in honor of Jean Della Dora, (TC 2006): 43–49. 2006 [2023-09-16]. ISBN 9788468983813. OCLC 496720771. (原始内容存档 (PDF)于2022-05-26). 
  3. ^ SIGSAM official site. [2023-09-16]. (原始内容存档于2023-08-16). 
  4. ^ SIGSAM list of conferences. [2012-11-15]. (原始内容存档于2013-08-08). 
  5. ^ Cohen, Joel S. Computer Algebra and Symbolic Computation: Mathematical Methods有限度免费查阅,超限则需付费订阅. AK Peters. 2003: 14. ISBN 978-1-56881-159-8. 
  6. ^ SIGSAM list of journals. [2023-09-16]. (原始内容存档于2013-09-28). 
  7. ^ Richard Liska Expression swell页面存档备份,存于互联网档案馆), from "Peculiarities of programming in computer algebra systems"
  8. ^ Cassidy, Kevin G. The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment (PDF) (学位论文). Naval Postgraduate School, Monterey/CA: 15. Dec 1985. ADA165184. 
  9. ^ Buchberger, Bruno; Loos, Rüdiger. Algebraic simplification (PDF). Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf (编). Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa 4. 1983: 11–43 [2023-09-16]. ISBN 978-3-211-81776-6. doi:10.1007/978-3-7091-7551-4_2. (原始内容存档 (PDF)于2022-01-20). 
  10. ^ Davenport, J. H.; Siret, Y.; Tournier, É. Computer Algebra: Systems and Algorithms for Algebraic Computation. Academic. 1988. ISBN 0-12-204230-1. OCLC 802584470. 
  11. ^ Kaltofen, Erich. Factorization of polynomials. Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf (编). Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa 4. 1983: 95–113. ISBN 978-3-211-81776-6. S2CID 18352153. doi:10.1007/978-3-7091-7551-4_8. 

阅读更多

For a detailed definition of the subject:

For textbooks devoted to the subject: