This article'slead sectioncontains information that is not included elsewhere in the article. If this information is appropriate for the lead, it should also be included in the article's body. Relevant discussion may be found on thetalk page.(May 2020) (Learn how and when to remove this message)

Inmathematics andcomputer science,^[1]computer algebra, also calledsymbolic computation oralgebraic computation, is a scientific area that refers to the study and development ofalgorithms andsoftware for manipulatingmathematical expressions and othermathematical objects. Although computer algebra could be considered a subfield ofscientific computing, they are generally considered as distinct fields^{[according to whom?]} because scientific computing is usually based onnumerical computation with approximatefloating point numbers, while symbolic computation emphasizesexact computation with expressions containingvariables that have no given value and are manipulated as symbols.

Software applications that perform symbolic calculations are calledcomputer algebra systems, with the termsystem alluding to the complexity of the main applications that include, at least, a method to represent mathematical data in a computer, a userprogramming language (usually different from the language used for the implementation), a dedicated memory manager, auser interface for the input/output of mathematical expressions, and a large set ofroutines to perform usual operations, like simplification of expressions,differentiation using thechain 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 inpublic key cryptography, or for somenon-linear problems.

Some authors distinguishcomputer algebra fromsymbolic computation, using the latter name to refer to kinds of symbolic computation other than the computation with mathematicalformulas. Some authors usesymbolic computation for the computer-science aspect of the subject andcomputer 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 calledcalcul formel in French, which means "formal computation". This name reflects the ties this field has withformal methods.

Symbolic computation has also been referred to, in the past, assymbolic manipulation,algebraic manipulation,symbolic processing,symbolic mathematics, orsymbolic algebra, but these terms, which also refer to non-computational manipulation, are no longer used in reference to computer algebra.

There is nolearned society that is specific to computer algebra, but this function is assumed by thespecial interest group of theAssociation for Computing Machinery namedSIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation).^[3]

There are several annual conferences on computer algebra, the premier beingISSAC (International Symposium on Symbolic and Algebraic Computation), which is regularly sponsored by SIGSAM.^[4]

There are several journals specializing in computer algebra, the top one beingJournal of Symbolic Computation founded in 1985 byBruno Buchberger.^[5] There are also several other journals that regularly publish articles in computer algebra.^[6]

Asnumerical software is highly efficient for approximatenumerical computation, it is common, in computer algebra, to emphasizeexact 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 calledexpression swell.^[7] To alleviate this problem, various methods are used in the representation of the data, as well as in the algorithms that manipulate them.^[8]

The usual number systems used innumerical computation arefloating point numbers andintegers of a fixed, bounded size. Neither of these is convenient for computer algebra, due to expression swell.^[9] Therefore, the basic numbers used in computer algebra are the integers of the mathematicians, commonly represented by an unbounded signed sequence ofdigits in somebase of numeration, usually the largest base allowed by themachine word. These integers allow one to define therational numbers, which areirreducible fractions of two integers.

Programming an efficient implementation of the arithmetic operations is a hard task. Therefore, most freecomputer algebra systems, and some commercial ones such asMathematica andMaple,^[10][11] use theGMP library, which is thus ade facto standard.

Except fornumbers andvariables, everymathematical expression may be viewed as the symbol of an operator followed by asequence 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, anequation may be considered as an expression with "=" as its leading operator, and 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 expressiona +b may be viewed as a program for the addition, witha andb as parameters. Executing this program consists ofevaluating the expression for given values ofa andb; if they are not given any values, then the result of the evaluation is simply its input.

This process of delayed evaluation is fundamental in computer algebra. For example, the operator "=" of equation 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 eitherpointers (like inMacsyma)^[13] or entries in ahash table (like inMaple).

The raw application of the basic rules ofdifferentiation with respect tox on the expressiona^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 throughrewriting rules.^[14] There are several classes of rewriting rules to be considered. The simplest are rules that always reduce the size of the expression, likeE −E → 0 orsin(0) → 0. They are systematically applied in computer algebra systems.

A difficulty occurs withassociative 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, thata +b +c is represented as"+"(a,b,c). Thusa + (b +c) and(a +b) +c are both simplified to"+"(a,b,c), which is displayeda +b +c. In the case of expressions such asa −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 thecommutativity of addition and multiplication. The problem is to quickly recognize thelike 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. InMaple, ahash 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 for thedistributive law ortrigonometric identities. For example, the distributive law allows rewriting${\displaystyle (x+1{)}^4\to x^4+4x^3+6x^2+4x+1}$ and${\displaystyle (x-1)(x^4+x^3+x^2+x+1)\to 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 distributive law, 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 (seePolynomial factorization).

Some fundamental mathematical questions arise when one wants to manipulatemathematical expressions in a computer. We consider mainly the case of themultivariaterational fractions. This is not a real restriction, because, as soon as theirrational functions appearing in an expression are simplified, they are usually considered as new indeterminates. For example,

${\displaystyle (\sin (x+y{)}^2+\log (z^2-5){)}^3}$

is viewed as a polynomial in${\displaystyle \sin (x+y)}$ and${\displaystyle \log (z^2-5)}$.

There are two notions of equality formathematical 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 fromRichardson'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 thepolynomials andrational fractions.

To test the equality of two expressions, instead of designing specific algorithms, it is usual to put expressions in somecanonical form or to put their difference in anormal form, and to test the syntactic equality of the result.

In computer algebra, "canonical form" and "normal form" are not synonymous.^[15] Acanonical form is such that two expressions in canonical form are semantically equal if and only if they are syntactically equal, while anormal 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 thedistributive law, 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 the use of a canonical form impractical.

Early computer algebra systems, such as theENIAC at theUniversity of Pennsylvania, relied onhuman 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, andKay McNulty led said efforts.^[17]

In 1960,John McCarthy explored an extension ofprimitive recursive functions for computing symbolic expressions through theLisp programming language while at theMassachusetts 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 establishProject MAC at the Massachusetts Institute of Technology and the organization that later became theStanford AI Laboratory (SAIL) atStanford 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 asALTRAN, sought to overcome algorithmic limitations through advancements in hardware and interpreters, while later efforts turned towards software optimization.^[21]

A large part of the work of researchers in the field consisted of revisiting classicalalgebra to increase itseffectiveness while developingefficient algorithms for use in computer algebra. An example of this type of work is the computation ofpolynomial greatest common divisors, a task required to simplify fractions and an essential component of computer algebra. Classical algorithms for this computation, such asEuclid's algorithm, proved inefficient over infinite fields; algorithms fromlinear algebra faced similar struggles.^[22] Thus, researchers turned to discovering methods of reducing polynomials (such as those over aring of integers or aunique factorization domain) to a variant efficiently computable via a Euclidean algorithm.

• 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

For a detailed definition of the subject:

• Buchberger, Bruno (1985)."Symbolic Computation (An Editorial)"(PDF).Journal of Symbolic Computation.1 (1):1–6.doi:10.1016/S0747-7171(85)80025-0.

For textbooks devoted to the subject:

• Davenport, James H.; Siret, Yvon; Tournier, Èvelyne (1988).Computer Algebra: Systems and Algorithms for Algebraic Computation. Translated from the French by A. Davenport and J. H. Davenport. Academic Press.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.Bibcode:1992afca.book.....G.doi:10.1007/b102438.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.doi:10.1007/978-3-7091-7551-4.ISBN 978-3-211-81776-6.S2CID 5221892.

• Computer algebra

• Articles with short description
• Short description is different from Wikidata
• Wikipedia introduction cleanup from May 2020
• All pages needing cleanup
• Articles covered by WikiProject Wikify from May 2020
• All articles covered by WikiProject Wikify
• All articles with specifically marked weasel-worded phrases
• Articles with specifically marked weasel-worded phrases from September 2025
• Articles with excerpts