Data representation

As numerical software is highly efficient for approximate numerical computation, it is common, in computer algebra, to emphasize exact computation with exactly represented data. 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. This behavior is called expression swell. To obviate this problem, various methods are used in the representation of the data, as well as in the algorithms that manipulate them.

Expressions

Representation of the expression (8 − 6) × (3 + 1) as a Lisp tree, from a 1985 Master's Thesis.^[10]

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)^[11] 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 ${\displaystyle a^{x}}$ gives the result

${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).}$

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.^[12] 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 associative operations like addition and multiplication. 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⁻¹. In other words, in the internal representation of the expressions, there is no subtraction nor division nor unary minus, outside the representation of the numbers.

Another difficulty occurs with the commutativity of addition and multiplication. The problem is to quickly recognize the like terms in order to combine or cancel them. Testing every pair of terms is costly with very long sums and products. To address this, Macsyma sorts the operands of sums and products into an order that places like terms in consecutive places, allowing easy detection. 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 allows subexpressions that appear several times in a computation to be immediately recognized and stored only once. This saves memory and speeds up computation by avoiding repetition of the same operations on identical expressions.

Some rewriting rules sometimes increase and sometimes decrease the size of the expressions to which they are applied. This is the case of distributivity or trigonometric identities. For example, the distributivity law allows rewriting ${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$ and ${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.}$ As there is no way to make a good general choice of applying or not such a rewriting rule, such rewriting is done only when explicitly invoked by the user. For the distributivity, the computer function that applies this rewriting rule is typically called "expand". The reverse rewriting rule, called "factor", requires a non-trivial algorithm, which is thus a key function in computer algebra systems (see Polynomial factorization).

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

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}.}$

It is known from Richardson's theorem that there may not exist an algorithm that decides whether two expressions representing numbers are semantically equal if exponentials and logarithms are allowed in the expressions. 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.

In computer algebra, "canonical form" and "normal form" are not synonymous.^[13] 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 distributivity, while it is not necessary with a normal form (see below). Secondly, it may be the case, like for expressions involving radicals, that a canonical form, if it exists, depends on some arbitrary choices and that these choices may be different for two expressions that have been computed independently. This may make impracticable the use of a canonical form.

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.^[14] 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.^[15]

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.^[16] Though his series on "Recursive functions of symbolic expressions and their computation by machine" remained incomplete,^[17] 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.^[18] Predecessors to Project MAC, such as ALTRAN, sought to overcame algorithmic limitations through advancements in hardware and interpreters, while later efforts turned towards software optimization.^[19]

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, provided inefficient over infinite fields; algorithms from linear algebra faced similar struggles.^[20] 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.