Computer Algebra of Polynomials and Rational Functions
Computer Algebra of Polynomials and Rational Functions
复制标题
多项式和有理函数的计算机代数
DOI：
10.1080/00029890.1973.11993365
复制
发表时间：
1973
影响因子：
0.5
通讯作者：
G. Collins
中科院分区：
文献类型：
--
作者：
G. Collins
1.导论.计算机程序现在可用于执行许多重要的代数过程的兴趣和实用的纯数学家和应用数学家。此外，许多有趣的数学问题出现在开发和分析的算法中使用这样的程序。作为一名数学家出身的计算机科学家，他为实现计算机代数能力的现状做出了贡献，并对数学问题感兴趣，这些问题的解决方案将有助于进一步的进步，我希望在这篇简短的综述文章中，能传授我对这一问题的一些知识，并将我对这一问题的热情传递给其他数学家。我将讨论的计算机代数主要是多项式和有理函数，原因如下。首先，分配的空间不允许我更雄心勃勃。其次，这是这个主题中我唯一真正具有权威性的部分。第三，这是主体中最为人所知的部分，也是其他部分最依赖的部分。我将关注多项式和有理函数在几个变量，主要是与合理的整数系数，但这也将导致考虑的合理数系数和有限域系数;代数数系数将得到一些提及，作为一个先进的课题，目前的研究。将被考虑的多项式和有理函数的操作包括加、减、乘和除的”算术”操作。我将在第3节中展示，也许会让读者感到惊讶，当目标是设计和分析最优算法时，甚至多项式算术也是不平凡和有趣的。有理函数上的算术运算的算法需要多项式gcd（最大公约数）计算的有效算法。过去七年的研究表明，多项式的”欧几里德算法”有许多版本，其效率差异很大。此外，在过去的四年中，“模块化”多项式gcd算法已经设计出来，这取决于使用中国剩余定理，这是数量级快于任何非模块化的欧几里德算法。
1. Introduction. Computer programs are now available for performing many important algebraic processes of interest and utility to pure and applied mathematicians. Also, many interesting mathematical problems arise in the development and analysis of algorithms for use in such programs. As a mathematician-turned-computerscientist who has contributed to realizing the current state of computer algebra capabilities and who is intrigued with the mathematical problems whose solutions will contribute to further progress, I hope in this brief survey article to impart some of my knowledge a bout this subject and to transmit some of my enthusiasm for it to other mathematicians.1 he kind of computer algebra I will discuss is concerned mainly with polynomials and rational functions, for the following reasons. First, the allotted space does not permit me to be more ambitious. Second, this is the only part of the subject in which I can really be authoritative. Third, this is the part of the subject about which the most is known and on which other parts most depend. I shall be concerned with polynomials and rational functions in several variables, primarily with rational integer coefficients, but this will also lead to consideration of rational number coefficients and finite field coefficients; algebraic number coefficients will receive some mention as an advanced topic of current research. Operations on polynomials and rational functions which will be considered include the" arithmetic" operations of addition, subtraction, multiplication and division. I shall show in Section 3, perhaps to the reader's surprise, that even polynomial arithmetic is non-trivial and interesting when the objective is to design and analyze optimal algorithms.Algorithms for the arithmetic operations on rational functions require an efficient algorithm for polynomial gcd (greatest common divisor) calculation. Research over the last seven years has revealed that there are numerous versions of the" Euclidean algorithm" for polynomials which differ dramatically in their efficiency. Also, within the last four years," modular" polynomial gcd algorithms have been devised, which depend on use of the Chinese remainder theorem, and which are orders of magnitudes faster than any of the non-modular Euclidean algorithms.