Computer algebra: Difference between revisions

Revision as of 11:24, 4 July 2024

Revision as of 16:33, 6 February 2025

Line 5:

In [[mathematics]] and [[computer science]],<ref>{{Cite web |title=ACM Association in computer algebra |url=https://www.sigsam.org/cca/}}</ref> '''computer algebra''', also called '''symbolic computation''' or '''algebraic computation''', is a scientific area that refers to the study and development of [[algorithm]]s and [[software]] for manipulating [[expression (mathematics)|mathematical expressions]] and other [[mathematical object]]s. Although computer algebra could be considered a subfield of [[scientific computing]], they are generally considered as distinct fields because scientific computing is usually based on [[numerical computation]] with approximate [[floating point number]]s, while symbolic computation emphasizes ''exact'' computation with expressions containing [[variable (mathematics)|variable]]s that have no given value and are manipulated as symbols.

[[Software]] applications that perform symbolic calculations are called ''[[computer algebra system]]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]] for the input/output of mathematical expressions, and a large set of [[function (computer science)|routines]] to perform usual operations, like simplification of expressions, [[differentiation (mathematics)|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.

Line 11:

== 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]]s. Some authors use ''symbolic computation'' for the computer -science aspect of the subject and "''computer algebra"'' for the mathematical aspect.<ref>{{cite conference | first = Stephen M. | last = Watt | date = 2006 | url = http://www.csd.uwo.ca/~watt/pub/reprints/2006-tc-sympoly.pdf | title = Making Computer Algebra More Symbolic (Invited) | conference = Transgressive Computing 2006: A conference in honor of Jean Della Dora, (TC 2006) | pages = 43–49 |isbn=9788468983813 |oclc=496720771}}</ref> 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).<ref>[http://www.sigsam.org SIGSAM official site]</ref>

on Symbolic and Algebraic Manipulation).<ref>[http://www.sigsam.org SIGSAM official site]</ref>

There are several annual conferences on computer algebra, the premier being [[ISSAC]] (International Symposium on Symbolic and Algebraic Computation), which is regularly sponsored by SIGSAM.<ref>{{Cite web |url=http://www.sigsam.org/conferences/index.phtml |title=SIGSAM list of conferences |access-date=2012-11-15 |archive-url=https://web.archive.org/web/20130808052201/http://www.sigsam.org/conferences/index.phtml |archive-date=2013-08-08 |url-status=dead }}</ref>

Line 27 ⟶ 26:

=== 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''.<ref>{{Cite web |title=Lecture 12: Rational Functions and Conversions — Introduction to Symbolic Computation 1.7.6 documentation |url=https://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec12.html |access-date=2024-03-31 |website=homepages.math.uic.edu}}</ref> To obviatealleviate this problem, various methods are used in the representation of the data, as well as in the algorithms that manipulate them.<ref>{{Cite journal |last1=Neut |first1=Sylvain |last2=Petitot |first2=Michel |last3=Dridi |first3=Raouf |date=2009-03-01 |title=Élie Cartan's geometrical vision or how to avoid expression swell |url=https://www.sciencedirect.com/science/article/pii/S0747717108001132 |journal=Journal of Symbolic Computation |series=Polynomial System Solving in honor of Daniel Lazard |volume=44 |issue=3 |pages=261–270 |doi=10.1016/j.jsc.2007.04.006 |issn=0747-7171}}</ref>

==== Numbers ====

The usual numbersnumber systems used in [[numerical computation]] are [[floating point]] numbers and [[integers]] of a fixed, bounded size. Neither of these is convenient for computer algebra, due to expression swell.<ref>Richard Liska [http://kfe.fjfi.cvut.cz/~liska/ca/node53.html#:~:text=is%20a%20common%20phenomenon%20of,dramatically%20as%20the%20calculation%20progresses. Expression swell], from "Peculiarities of programming in computer algebra systems"</ref> Therefore, the basic numbers used in computer algebra are the integers of the mathematicians, commonly represented by an unbounded signed sequence of [[numerical digit|digits]] in some [[radix|base of numeration]], usually the largest base allowed by the [[machine word]]. These integers allow one to define the [[rational number]]s, which are [[irreducible fraction]]s of two integers.

Programming an efficient implementation of the arithmetic operations is a hard task. Therefore, most free [[computer algebra system]]s, and some commercial ones such as [[Mathematica]] and [[Maple (software)|Maple]],<ref>[https://library.wolfram.com/infocenter/Conferences/7518/Macalester_talk.txt "The Mathematica Kernel: Issues in the Design and Implementation"]. October 2006. Retrieved 2023-11-29.</ref><ref>[https://www.maplesoft.com/support/help/AddOns/view.aspx?path=GMP "The GNU Multiple Precision (GMP) Library"]. [[Maplesoft]]. Retrieved 2023-11-29.</ref> use the [[GNU Multiple Precision Arithmetic Library|GMP library]], which is thus a ''de facto'' standard.

Therefore, the basic numbers used in computer algebra are the integers of the mathematicians, commonly represented by an unbounded signed sequence of [[numerical digit|digits]] in some [[radix|base of numeration]], usually the largest base allowed by the [[machine word]]. These integers allow to define the [[rational number]]s, which are [[irreducible fraction]]s of two integers.

Programming an efficient implementation of the arithmetic operations is a hard task. Therefore, most free [[computer algebra system]]s and some commercial ones such as [[Mathematica]] and [[Maple (software)|Maple]],<ref>[https://library.wolfram.com/infocenter/Conferences/7518/Macalester_talk.txt "The Mathematica Kernel: Issues in the Design and Implementation"]. October 2006. Retrieved 2023-11-29.</ref><ref>[https://www.maplesoft.com/support/help/AddOns/view.aspx?path=GMP "The GNU Multiple Precision (GMP) Library"]. [[Maplesoft]]. Retrieved 2023-11-29.</ref> use the [[GNU Multiple Precision Arithmetic Library|GMP library]], which is thus a ''de facto'' standard.

==== Expressions ====

[[File:Cassidy.1985.015.gif|thumb|400px|Representation of the expression {{math|(8 − 6) × (3 + 1)}} as a [[Lisp (programming language)|Lisp]] tree, from a 1985 Master's Thesis<ref>{{cite thesis | type=Master's thesis | url=https://commons.wikimedia.org/wiki/File:The_feasibility_of_automatic_storage_reclamation_with_concurrent_program_execution_in_a_LISP_environment._(IA_feasibilityofaut00cass).pdf | first=Kevin G. |last=Cassidy | title=The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment | institution=Naval Postgraduate School, Monterey/CA | date=Dec 1985 |page=15 |id=ADA165184}}</ref>]]

Except for [[number]]s and [[variable (mathematics)|variables]], every [[Expression (mathematics)|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, 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 expression {{math|''a'' + ''b''}} may be viewed as a program for the addition, with {{math|''a''}} and {{math|''b''}} as parameters. Executing this program consists inof ''evaluating'' the expression for given values of {{math|''a''}} and {{math|''b''}}; 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 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.

Line 49 ⟶ 46:

=== Simplification ===

The raw application of the basic rules of [[derivative|differentiation]] with respect to {{math|''x''}} on the expression {{Math|''a''<mathsup>a^''x''</mathsup>}} gives the result

:<math> x\cdot a^{x-1}\cdot 0 + a^x\cdot \left (1\cdot \log a + x\cdot \frac{0}{a} \right).</math>

A simpler expression than this is generally desired, and simplification is needed when working with general expressions. This simplification is normally done through [[rewriting|rewriting rules]].<ref>{{cite book |last1=Buchberger |first1=Bruno |first2=Rüdiger |last2=Loos |chapter=Algebraic simplification |chapter-url=https://www.risc.jku.at/people/buchberg/papers/1982-00-00-B.pdf | editor1-last = Buchberger | editor1-first = Bruno | editor2-last = Collins | editor2-first = George Edwin | editor3-last = Loos | editor3-first = Rüdiger | editor4-last = Albrecht| editor4-first = Rudolf |title= Computer Algebra: Symbolic and Algebraic Computation|series=Computing Supplementa |year=1983 |volume=4 |pages=11–43 |doi=10.1007/978-3-7091-7551-4_2 |isbn=978-3-211-81776-6 }}</ref> There are several classes of rewriting rules to be considered. The simplest are rules that always reduce the size of the expression, like {{math|''E'' &minus; ''E'' → 0}} or {{math|sin(0) → 0}}. They are systematically applied in computer algebra systems.

A simpler expression than this is generally desired, and simplification is needed when working with general expressions.

This simplification is normally done through [[rewriting|rewriting rules]].<ref>{{cite book |last1=Buchberger |first1=Bruno |first2=Rüdiger |last2=Loos |chapter=Algebraic simplification |chapter-url=https://www.risc.jku.at/people/buchberg/papers/1982-00-00-B.pdf | editor1-last = Buchberger | editor1-first = Bruno | editor2-last = Collins | editor2-first = George Edwin | editor3-last = Loos | editor3-first = Rüdiger | editor4-last = Albrecht| editor4-first = Rudolf |title= Computer Algebra: Symbolic and Algebraic Computation|series=Computing Supplementa |year=1983 |volume=4 |pages=11–43 |doi=10.1007/978-3-7091-7551-4_2 |isbn=978-3-211-81776-6 }}</ref> There are several classes of rewriting rules to be considered. The simplest are rules that always reduce the size of the expression, like {{math|''E'' &minus; ''E'' → 0}} or {{math|sin(0) → 0}}. They are systematically applied in computer algebra systems.

A difficulty occurs with [[associative operation]]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 {{math|''a'' + ''b'' + ''c''}} is represented as {{math|"+"(''a'', ''b'', ''c'')}}. Thus {{math|''a'' + (''b'' + ''c'')}} and {{math|(''a'' + ''b'') + ''c''}} are both simplified to {{math|"+"(''a'', ''b'', ''c'')}}, which is displayed {{math|''a'' + ''b'' + ''c''}}. In the case of expressions such as {{math|''a'' &minus; ''b'' + ''c''}}, the simplest way is to systematically rewrite {{math|&minus;''E''}}, {{math|''E'' &minus; ''F''}}, {{math|''E''/''F''}} as, respectively, {{math|(&minus;1)⋅''E''}}, {{math|''E'' + (&minus;1)⋅''F''}}, {{math|''E''⋅''F''^&minus;1}}. 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 (software)|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 offor the [[distributivity|distributive law]] or [[Trigonometric identity#Product-to-sum and sum-to-product identities|trigonometric identities]]. For example, the distributivitydistributive law allows rewriting <math>(x+1)^4 \rightarrow x^4+4x^3+6x^2+4x+1</math> and <math>(x-1)(x^4+x^3+x^2+x+1) \rightarrow x^5-1.</math> 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 distributivitydistributive 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 (see [[Polynomial factorization]]).

== Mathematical aspects ==