Computer algebra: Difference between revisions

Revision as of 13:37, 3 July 2023

Revision as of 13:38, 3 July 2023

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, a large set of [[function (computer science)|routines]] to perform usual operations, like simplification of expressions, [[differentiation (mathematics)|differentiation]] using [[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 54:

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.

Line 81:

==History==

At the beginning of computer algebra, circa 1970, when the long-known [[algorithm]]s were first put on computers, they turned out to be highly inefficient.<ref>{{cite book | 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 |pages=95–113 |doi=10.1007/978-3-7091-7551-4_8 |first1=Erich|last1=Kaltofen|chapter=Factorization of polynomials |series=Computing Supplementa |year=1983 |volume=4 |isbn=978-3-211-81776-6 |s2cid=18352153 }}</ref> Therefore, a large part of the work of the researchers in the field consisted in revisiting classical [[algebra]] in order to make it [[Computable function|effective]] and to discover [[algorithmic efficiency|efficient algorithms]] to implement this effectiveness. A typical example of this kind of work is the computation of [[polynomial greatest common divisor]]s, which is required to simplify fractions. Surprisingly, the classical [[Euclid's algorithm]] 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]].

== See also ==

Line 104:

*{{cite book|first1=Joachim|last1=von zur Gathen|first2=Jürgen|last2=Gerhard|title=Modern computer algebra|edition=2nd|publisher=Cambridge University Press|year=2003|isbn = 0-521-82646-2}}

*{{Cite book | last1 = Geddes | first1 = K. O. | last2 = Czapor | first2 = S. R. | last3 = Labahn | first3 = G. | doi = 10.1007/b102438 | title = Algorithms for Computer Algebra | year = 1992 | bibcode = 1992afca.book.....G | isbn = 978-0-7923-9259-0 | url-access = registration | url = https://archive.org/details/algorithmsforcom0000gedd }}

*{{Cite book | 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 | doi = 10.1007/978-3-7091-7551-4 | title = Computer Algebra: Symbolic and Algebraic Computation | series = Computing Supplementa | volume = 4 | year = 1983 | isbn = 978-3-211-81776-6 | s2cid = 5221892 | editor2-last = Collins | editor3-last = Loos | editor4-last = Albrecht | url-access = registration | url = https://archive.org/details/computeralgebras0000unse }}

{{Computer algebra systems}}