Computer algebra
Software applications that perform symbolic calculations are called computer algebra systems, with the term system alluding to the complexity of the main applications that include, at least, a method to represent mathematical data in a computer, a user programming language (usually different from the language used for the implementation), a dedicated memory manager, a user interface for the input/output of mathematical expressions, and a large set of routines to perform usual operations, like simplification of expressions, differentiation using the chain rule, polynomial factorization, indefinite integration, etc.
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 public key cryptography, or for some non-linear problems.
Typically, it is called calcul formel in French, which means "formal computation".
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).
Such an exact representation implies that, even when the size of the output is small, the intermediate data generated during a computation may grow in an unpredictable way.
[9] Therefore, the basic numbers used in computer algebra are the integers of the mathematicians, commonly represented by an unbounded signed sequence of digits in some base of numeration, usually the largest base allowed by the machine word.
Therefore, most free computer algebra systems, and some commercial ones such as Mathematica and Maple,[10][11] use the GMP library, which is thus a de facto standard.
Except for numbers and variables, every mathematical expression may be viewed as the symbol of an operator followed by a sequence of operands.
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, 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.
The standard way to deal with associativity is to consider that addition and multiplication have an arbitrary number of operands; that is, that a + b + c is represented as "+"(a, b, c).
Thus a + (b + c) and (a + b) + c are both simplified to "+"(a, b, c), which is displayed a + b + c. In the case of expressions such as a − b + c, the simplest way is to systematically rewrite −E, E − F, E/F as, respectively, (−1)⋅E, E + (−1)⋅F, E⋅F−1.
In Maple, a hash function is designed for generating collisions when like terms are entered, allowing them to be combined as soon as they are introduced.
This saves memory and speeds up computation by avoiding repetition of the same operations on identical expressions.
For the distributive law, the computer function that applies this rewriting rule is typically called "expand".
This is not a real restriction, because, as soon as the irrational functions appearing in an expression are simplified, they are usually considered as new indeterminates.
Accordingly, (semantic) equality may be tested only on some classes of expressions such as the polynomials and rational fractions.
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.
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] 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.
[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.
[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 Euclidean algorithm.
