TheInfoList

In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
and
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of computation, automation, a ...
, computer algebra, also called symbolic computation or algebraic computation, is a scientific area that refers to the study and development of
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

s and
software Software is a collection of instructions Instruction or instructions may refer to: Computing * Instruction, one operation of a processor within a computer architecture instruction set * Computer program, a collection of instructions Music * I ...

for manipulating
mathematical expressions In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed formula, well-formed according to rules that depend on the context. Mathematical symbols can designate numbers (constant (mathematics ...
and other
mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical proofs ...
s. Although computer algebra could be considered a subfield of
scientific computing Computational science, also known as scientific computing or scientific computation (SC), is a field that uses advanced computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes th ...
, they are generally considered as distinct fields because scientific computing is usually based on
numerical computation (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 The square root of 2, or the one-half power of 2, written in mathematics as \sqrt or 2^, is the positive algebraic number that, when multiplied by itself, equals t ...
with approximate
floating point number In computing, floating-point arithmetic (FP) is arithmetic using formulaic representation of real numbers as an approximation to support a trade-off between range and precision. For this reason, floating-point computation is often used in system ...
s, while symbolic computation emphasizes ''exact'' computation with expressions containing variables that have no given value and are manipulated as symbols.
Software Software is a collection of instructions Instruction or instructions may refer to: Computing * Instruction, one operation of a processor within a computer architecture instruction set * Computer program, a collection of instructions Music * I ...

applications that perform symbolic calculations are called ''
computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software Mathematical software is software used to mathematical model, model, analyze or calculate numeric, symbolic or geometric data. It is a type of applica ...

s'', 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 In the industrial design Industrial design is a process of design A design is a plan or specification for the construction of an object or system or for the implementation of an activity or process, or the result of that plan or specificati ...
for the input/output of mathematical expressions, a large set of routines to perform usual operations, like simplification of expressions,
differentiation Differentiation may refer to: Business * Differentiation (economics), the process of making a product different from other similar products * Product differentiation, in marketing * Differentiated service, a service that varies with the identity o ...
using chain rule,
polynomial factorization In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
,
indefinite integration In calculus, an antiderivative, inverse derivative, primitive function, primitive integral or indefinite integral of a function (mathematics), function is a differentiable function whose derivative is equal to the original function . This can ...
, 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 Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys KEYS (1440 AM broadcasting, AM) is a radio station serving the Corpus Christi, Texas, Corpus Christi, Texas area with a talk radio, talk ...
, or for some
non-linear In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
problems.

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
formula In , a formula is a concise way of expressing information symbolically, as in a mathematical formula or a . The informal use of the term ''formula'' in science refers to the . The plural of ''formula'' can be either ''formulas'' (from the mos ...

s. Some authors use ''symbolic computation'' for the computer science aspect of the subject and "computer algebra" for the mathematical aspect. 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 In computer science, specifically software engineering and hardware engineering, formal methods are a particular kind of mathematically rigorous techniques for the formal specification, specification, development and formal verification, verificati ...
. 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 A learned society (; also known as a learned academy, scholarly society, or academic association) is an organization that exists to promote an discipline (academia), academic discipline, profession, or a group of related disciplines such as the ...
that is specific to computer algebra, but this function is assumed by the special interest group of the
Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society A learned society (; also known as a learned academy, scholarly society, or academic association) is an organization that exists to promote an discipl ...
named
SIGSAMSIGSAM is the Association for Computing Machinery, ACM Special Interest Group on Symbolic and Algebraic Manipulation. It publishes the ''ACM Communications in Computer Algebra'' and often sponsors the ''International Symposium on Symbolic and Algebra ...
(Special Interest Group on Symbolic and Algebraic Manipulation). There are several annual conferences on computer algebra, the premier being
ISSACIssac may refer to: Given name * Issac Blakeney (born 1992), American football wide receiver * Issac Booth (born 1971), American football player * Issac Ryan Brown (born 2005), American child actor and singer * Issac Delgado (born 1962), Cuban-Spani ...
(International Symposium on Symbolic and Algebraic Computation), which is regularly sponsored by SIGSAM. There are several journals specializing in computer algebra, the top one being
Journal of Symbolic Computation The ''Journal of Symbolic Computation'' is a Peer review, peer-reviewed monthly scientific journal covering all aspects of symbolic computation published by Academic Press and then by Elsevier. It is targeted to both mathematicians and computer sci ...
founded in 1985 by
Bruno Buchberger Bruno Buchberger (born 22 October 1942) is Professor of Computer Mathematics at Johannes Kepler University in Linz Linz (; ; cs, Linec) is the capital of Upper Austria and List of cities and towns in Austria, third-largest city in Austria. In ...

. There are also several other journals that regularly publish articles in computer algebra.

Computer science aspects

Data representation

As
numerical software (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 is four sexagesimal Sexagesimal, also known as base 60 or sexagenary, is a numeral system with 60 (number), sixty as its radix, base. It originated with the ancient ...
is highly efficient for approximate
numerical computation (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 The square root of 2, or the one-half power of 2, written in mathematics as \sqrt or 2^, is the positive algebraic number that, when multiplied by itself, equals t ...
, 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.

Numbers

The usual numbers systems used in
numerical computation (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 The square root of 2, or the one-half power of 2, written in mathematics as \sqrt or 2^, is the positive algebraic number that, when multiplied by itself, equals t ...
are
floating point In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and soft ...
numbers and
integers An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power ...

of a fixed bounded size. None of these is convenient for computer algebra, due to expression swell. 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 , usually the largest base allowed by the
machine word In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and softwa ...
. These integers allow to define the
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s, which are
irreducible fraction An irreducible fraction (or fraction in lowest terms, simplest form or reduced fraction) is a fraction A fraction (from Latin ', "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday Engli ...
s of two integers. Programming an efficient implementation of the arithmetic operations is a hard task. Therefore, most free
computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software Mathematical software is software used to mathematical model, model, analyze or calculate numeric, symbolic or geometric data. It is a type of applica ...

s and some commercial ones such as
Mathematica Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning Machine learning (ML) is the study of computer algorithms that can improve automatically through experi ...

and
Maple (software) Maple is a symbolic and numeric computing environment as well as a multi-paradigm programming language Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple p ...
, use the GMP library, which is thus a ''de facto'' standard.

Expressions

Except for
number A number is a mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deduct ...

s and variables, every
mathematical expression In mathematics, an expression or mathematical expression is a finite combination of Glossary of mathematical symbols, symbols that is well-formed formula, well-formed according to rules that depend on the context. Mathematical symbols can desig ...
may be viewed as the symbol of an operator followed by a
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

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 may be viewed as a program for the addition, with and as parameters. Executing this program consists in ''evaluating'' the expression for given values of and ; if they do not have any value—that is they are indeterminates—, 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 0 or 1 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 Pointer may refer to: Places * Pointer, Kentucky * Pointers, New Jersey * Pointers Airport, Wasco County, Oregon, United States * The Pointers, a pair of rocks off Antarctica People with the name * Pointer (surname), a surname (including a list of ...
(like in
Macsyma Macsyma (; "Project MAC's SYmbolic MAnipulator") is one of the oldest general-purpose computer algebra systems still in wide use. It was originally developed from 1968 to 1982 at MIT's Project MAC. In 1982, Macsyma was licensed to Symbolics and be ...
) or entries in a
hash table In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and ...
(like in
Maple ''Acer'' is a genus Genus /ˈdʒiː.nəs/ (plural genera /ˈdʒen.ər.ə/) is a taxonomic rank In biological classification In biology, taxonomy () is the scientific study of naming, defining (Circumscription (taxonomy), circumscr ...
).

Simplification

The raw application of the basic rules of
differentiation Differentiation may refer to: Business * Differentiation (economics), the process of making a product different from other similar products * Product differentiation, in marketing * Differentiated service, a service that varies with the identity o ...

with respect to on the expression $a^x$ gives the result :$x\cdot a^\cdot 0 + a^x\cdot \left \left(1\cdot \log a + x\cdot \frac \right\right).$ Such a complicated expression is clearly not acceptable, and a procedure of simplification is needed as soon as one works with general expressions. This simplification is normally done through rewriting rules. There are several classes of rewriting rules that have to be considered. The simplest consists in the rewriting rules that always reduce the size of the expression, like or . They are systematically applied in computer algebra systems. The first difficulty occurs with
associative operation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
s 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 is represented as . Thus and are both simplified to , which is displayed . What about ? To deal with this problem, the simplest way is to rewrite systematically , , as, respectively, , , . 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. A second difficulty occurs with the
commutativity In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

of addition and multiplication. The problem is to recognize quickly the like terms in order to combine or cancel them. In fact, the method for finding like terms, consisting of testing every pair of terms, is too costly for being practicable with very long sums and products. For solving this problem,
Macsyma Macsyma (; "Project MAC's SYmbolic MAnipulator") is one of the oldest general-purpose computer algebra systems still in wide use. It was originally developed from 1968 to 1982 at MIT's Project MAC. In 1982, Macsyma was licensed to Symbolics and be ...
sorts the operands of sums and products with a function of comparison that is designed in order that like terms are in consecutive places, and thus easily detected. In
Maple ''Acer'' is a genus Genus /ˈdʒiː.nəs/ (plural genera /ˈdʒen.ər.ə/) is a taxonomic rank In biological classification In biology, taxonomy () is the scientific study of naming, defining (Circumscription (taxonomy), circumscr ...
, the
hash function A hash function is any function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical ...

is designed for generating collisions when like terms are entered, allowing to combine them as soon as they are introduced. This design of the hash function allows also to recognize immediately the expressions or subexpressions that appear several times in a computation and to store them only once. This allows not only to save some memory space but also to speed up computation, by avoiding repetition of the same operations on several 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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
or
trigonometric identities In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. For example, the distributivity law allows rewriting $\left(x+1\right)^4 \rightarrow x^4+4x^3+6x^2+4x+1$ and $\left(x-1\right)\left(x^4+x^3+x^2+x+1\right) \rightarrow x^5-1.$ As there is no way to make a good general choice of applying or not such a rewriting rule, such rewritings are done only when explicitly asked for by the user. For the distributivity, the computer function that applies this rewriting rule is generally 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 In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
).

Mathematical aspects

In this section we consider some fundamental mathematical questions that arise as soon as one wants to manipulate
mathematical expressions In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed formula, well-formed according to rules that depend on the context. Mathematical symbols can designate numbers (constant (mathematics ...
in a computer. We consider mainly the case of the multivariate
rational fraction In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...
s. This is not a real restriction, because, as soon as the
irrational function In mathematics, a rational function is any function (mathematics), function which can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the poly ...
s appearing in an expression are simplified, they are usually considered as new indeterminates. For example, :$\left(\sin\left(x+y\right)^2+ \log\left(z^2-5\right)\right)^3$ is viewed as a polynomial in $\sin\left(x+y\right)$ and $\log\left(z^2-5\right)$

Equality

There are two notions of equality for
mathematical expressions In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed formula, well-formed according to rules that depend on the context. Mathematical symbols can designate numbers (constant (mathematics ...
. The syntactic equality is the equality of the expressions which means that they are written (or represented in a computer) in the same way. Being trivial, the syntactic equality is rarely considered by mathematicians, although it is the only equality that is easy to test with a program. The ''semantic equality'' is when two expressions represent the same mathematical object, like in :$\left(x+y\right)^2=x^2+2xy+y^2.$ It is known from Richardson's theorem that there may not exist an algorithm that decides if two expressions representing numbers are semantically equal, if exponentials and logarithms are allowed in the expressions. Therefore, (semantical) equality may be tested only on some classes of expressions such as the
polynomial In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...

s and
rational fraction In algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In ...
s. To test the equality of two expressions, instead of designing specific algorithms, it is usual to put expressions in some ''
canonical form In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
'' or to put their difference in a ''normal form'', and to test the syntactic equality of the result. Unlike in usual mathematics, "canonical form" and "normal form" are not synonymous in computer algebra. 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 by expressions 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 by
distributivity In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
every product, 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.

History

At the beginning of computer algebra, circa 1970, when the long-known
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

s were first put on computers, they turned out to be highly inefficient. Therefore, a large part of the work of the researchers in the field consisted in revisiting classical
algebra Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. In its most ge ...

in order to make it
effective Effectiveness is the capability of producing a desired result or the ability to produce desired output. When something is deemed effective, it means it has an intended or expected outcome, or produces a deep, vivid impression. Etymology The origi ...
and to discover efficient algorithms to implement this effectiveness. A typical example of this kind of work is the computation of
polynomial greatest common divisor In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factorization, factor of both the two original polynomials. This concept is analogous to the gre ...
s, which is required to simplify fractions. Surprisingly, the classical
Euclid's algorithm In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
turned out to be inefficient for polynomials over infinite fields, and thus new algorithms needed to be developed. The same was also true for the classical algorithms from
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mat ...
.

*
Automated theorem prover Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoningIn computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its comput ...
*
Computer-assisted proofA computer-assisted proof is a mathematical proof that has been at least partially generated by computer. Most computer-aided proofs to date have been implementations of large Proof by exhaustion, proofs-by-exhaustion of a mathematical theorem. The ...
* Computational algebraic geometry *
Computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software Mathematical software is software used to mathematical model, model, analyze or calculate numeric, symbolic or geometric data. It is a type of applica ...

*
Proof checker An interactive proof session in CoqIDE, showing the proof script on the left and the proof state on the right. In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of i ...
*
Model checker In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algor ...
* Symbolic-numeric computation * Symbolic simulation *
Symbolic artificial intelligence Symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence Artificial intelligence (AI) is intelligence demonstrated by machines, unlike the natural intelligence human intelligence, displayed by ...