Computer algebra
![]() | This article's lead section contains information that is not included elsewhere in the article. (May 2020) |
In
Computer algebra is widely used to experiment in mathematics and to design the formulas that are used in numerical programs. It is also used for complete scientific computations, when purely numerical methods fail, as in
Terminology
Some authors distinguish computer algebra from symbolic computation using the latter name to refer to kinds of symbolic computation other than the computation with mathematical formulas. Some authors use symbolic computation for the computer science aspect of the subject and "computer algebra" for the mathematical aspect.[2] In some languages the name of the field is not a direct translation of its English name. Typically, it is called calcul formel in French, which means "formal computation". This name reflects the ties this field has with formal methods.
Symbolic computation has also been referred to, in the past, as symbolic manipulation, algebraic manipulation, symbolic processing, symbolic mathematics, or symbolic algebra, but these terms, which also refer to non-computational manipulation, are no longer used in reference to computer algebra.
Scientific community
There is no learned society that is specific to computer algebra, but this function is assumed by the special interest group of the Association for Computing Machinery named SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation).[3]
There are several annual conferences on computer algebra, the premier being
There are several journals specializing in computer algebra, the top one being Journal of Symbolic Computation founded in 1985 by Bruno Buchberger.[5] There are also several other journals that regularly publish articles in computer algebra.[6]
Computer science aspects
Data representation
As
Numbers
The usual numbers systems used in
Therefore, the basic numbers used in computer algebra are the integers of the mathematicians, commonly represented by an unbounded signed sequence of
Programming an efficient implementation of the arithmetic operations is a hard task. Therefore, most free
, which is thus a de facto standard.Expressions
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Cassidy.1985.015.gif/400px-Cassidy.1985.015.gif)
Except for numbers and variables, every mathematical expression may be viewed as the symbol of an operator followed by a sequence of operands. In computer algebra software, the expressions are usually represented in this way. This representation is very flexible, and many things that seem not to be mathematical expressions at first glance, may be represented and manipulated as such. For example, an equation is an expression with "=" as an operator, a matrix may be represented as an expression with "matrix" as an operator and its rows as operands.
Even programs may be considered and represented as expressions with operator "procedure" and, at least, two operands, the list of parameters and the body, which is itself an expression with "body" as an operator and a sequence of instructions as operands. Conversely, any mathematical expression may be viewed as a program. For example, the expression a + b may be viewed as a program for the addition, with a and b as parameters. Executing this program consists in evaluating the expression for given values of a and b; if they are not given any values, the result of the evaluation is simply its input.
This process of delayed evaluation is fundamental in computer algebra. For example, the operator "=" of the equations is also, in most computer algebra systems, the name of the program of the equality test: normally, the evaluation of an equation results in an equation, but, when an equality test is needed, either explicitly asked by the user through an "evaluation to a Boolean" command, or automatically started by the system in the case of a test inside a program, then the evaluation to a Boolean result is executed.
As the size of the operands of an expression is unpredictable and may change during a working session, the sequence of the operands is usually represented as a sequence of either pointers (like in Macsyma)[13] or entries in a hash table (like in Maple).
Simplification
The raw application of the basic rules of differentiation with respect to x on the expression gives the result
A simpler expression than this is generally desired, and simplification is needed when working with general expressions.
This simplification is normally done through rewriting rules.[14] There are several classes of rewriting rules to be considered. The simplest are rules that always reduce the size of the expression, like E − E → 0 or sin(0) → 0. They are systematically applied in computer algebra systems.
A difficulty occurs with
Another difficulty occurs with the
Some rewriting rules sometimes increase and sometimes decrease the size of the expressions to which they are applied. This is the case of
Mathematical aspects
Some fundamental mathematical questions arise when one wants to manipulate
is viewed as a polynomial in and
Equality
There are two notions of equality for mathematical expressions. Syntactic equality is the equality of their representation in a computer. This is easy to test in a program. Semantic equality is when two expressions represent the same mathematical object, as in
It is known from
To test the equality of two expressions, instead of designing specific algorithms, it is usual to put expressions in some canonical form or to put their difference in a normal form, and to test the syntactic equality of the result.
In computer algebra, "canonical form" and "normal form" are not synonymous.[15] A canonical form is such that two expressions in canonical form are semantically equal if and only if they are syntactically equal, while a normal form is such that an expression in normal form is semantically zero only if it is syntactically zero. In other words, zero has a unique representation as an expression in normal form.
Normal forms are usually preferred in computer algebra for several reasons. Firstly, canonical forms may be more costly to compute than normal forms. For example, to put a polynomial in canonical form, one has to expand every product through
History
Human-driven computer algebra
Early computer algebra systems, such as the ENIAC at the University of Pennsylvania, relied on human computers or programmers to reprogram it between calculations, manipulate its many physical modules (or panels), and feed its IBM card reader.[16] Female mathematicians handled the majority of ENIAC programming human-guided computation: Jean Jennings, Marlyn Wescoff, Ruth Lichterman, Betty Snyder, Frances Bilas, and Kay McNulty led said efforts.[17]
Foundations and early applications
In 1960, John McCarthy explored an extension of primitive recursive functions for computing symbolic expressions through the Lisp programming language while at the Massachusetts Institute of Technology.[18] Though his series on "Recursive functions of symbolic expressions and their computation by machine" remained incomplete,[19] McCarthy and his contributions to artificial intelligence programming and computer algebra via Lisp helped establish Project MAC at the Massachusetts Institute of Technology and the organization that later became the Stanford AI Laboratory (SAIL) at Stanford University, whose competition facilitated significant development in computer algebra throughout the late 20th century.
Early efforts at symbolic computation, in the 1960s and 1970s, faced challenges surrounding the inefficiency of long-known algorithms when ported to computer algebra systems.[20] Predecessors to Project MAC, such as ALTRAN, sought to overcome algorithmic limitations through advancements in hardware and interpreters, while later efforts turned towards software optimization.[21]
Historic problems
A large part of the work of researchers in the field consisted of revisiting classical algebra to increase its effectiveness while developing efficient algorithms for use in computer algebra. An example of this type of work is the computation of polynomial greatest common divisors, a task required to simplify fractions and an essential component of computer algebra. Classical algorithms for this computation, such as Euclid's algorithm, proved inefficient over infinite fields; algorithms from linear algebra faced similar struggles.[22] Thus, researchers turned to discovering methods of reducing polynomials (such as those over a ring of integers or a unique factorization domain) to a variant efficiently computable via a Euclidian algorithm.
Algorithms used in computer algebra
- Buchberger's algorithm: finds a Gröbner basis
- Cantor–Zassenhaus algorithm: factor polynomials over finite fields
- Faugère F4 algorithm: finds a Gröbner basis (also mentions the F5 algorithm)
- Gosper's algorithm: find sums of hypergeometric terms that are themselves hypergeometric terms
- Knuth–Bendix completion algorithm: for rewriting rule systems
- Multivariate division algorithm: for polynomialsin several indeterminates
- Pollard's kangaroo algorithm (also known as Pollard's lambda algorithm ): an algorithm for solving the discrete logarithm problem
- Polynomial long division: an algorithm for dividing a polynomial by another polynomial of the same or lower degree
- antiderivatives)
See also
- Automated theorem prover
- Computer-assisted proof
- Computational algebraic geometry
- Computer algebra system
- Differential analyser
- Proof checker
- Model checker
- Symbolic-numeric computation
- Symbolic simulation
- Symbolic artificial intelligence
References
- ^ "ACM Association in computer algebra".
- OCLC 496720771.
- ^ SIGSAM official site
- ^ "SIGSAM list of conferences". Archived from the original on 2013-08-08. Retrieved 2012-11-15.
- ISBN 978-1-56881-159-8.
- ^ SIGSAM list of journals
- ^ "Lecture 12: Rational Functions and Conversions — Introduction to Symbolic Computation 1.7.6 documentation". homepages.math.uic.edu. Retrieved 2024-03-31.
- ISSN 0747-7171.
- ^ Richard Liska Expression swell, from "Peculiarities of programming in computer algebra systems"
- ^ "The Mathematica Kernel: Issues in the Design and Implementation". October 2006. Retrieved 2023-11-29.
- Maplesoft. Retrieved 2023-11-29.
- ^ Cassidy, Kevin G. (Dec 1985). The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment (PDF) (Master's thesis). Naval Postgraduate School, Monterey/CA. p. 15. ADA165184.
- ^ Macsyma Mathematics and System Reference Manual (PDF). Macsyma. 1996. p. 419.
- ISBN 978-3-211-81776-6.
- OCLC 802584470.
- ^ "ENIAC in Action: What it Was and How it Worked". ENIAC: Celebrating Penn Engineering History. University of Pennsylvania. Retrieved December 3, 2023.
- ISSN 1097-3729.
- ISSN 0001-0782.
- ISBN 978-0-12-745040-7.
- ISSN 0747-7171.
- ISSN 0163-5824.
- ISBN 978-3-211-81776-6, retrieved 2023-11-29
Further reading
For a detailed definition of the subject:
- .
For textbooks devoted to the subject:
- ISBN 978-0-12-204230-0.
- von zur Gathen, Joachim; Gerhard, Jürgen (2003). Modern computer algebra (2nd ed.). Cambridge University Press. ISBN 0-521-82646-2.
- Geddes, K. O.; Czapor, S. R.; Labahn, G. (1992). Algorithms for Computer Algebra. ISBN 978-0-7923-9259-0.
- Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf, eds. (1983). Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa. Vol. 4. S2CID 5221892.