Content deleted Content added
JsfasdF252 (talk | contribs) No edit summary |
m Open access bot: url-access updated in citation with #oabot. |
||
| (44 intermediate revisions by 31 users not shown) | |||
Line 2:
{{Lead extra info|date=May 2020}}
[[File:RischIntegration.PNG|thumb|500px|[[Symbolic integration]] of the [[algebraic function]] {{math|1=''f''(''x'') = {{sfrac|''x''|{{sqrt|''x''<sup>4</sup> + 10''x''<sup>2</sup>
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
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
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>
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>
There are several journals specializing in computer algebra, the top one being ''[[Journal of Symbolic Computation]]'' founded in 1985 by [[Bruno Buchberger]].<ref>{{cite book |title=Computer Algebra and Symbolic Computation: Mathematical Methods |url=https://archive.org/details/computeralgebras00cohe_792 |url-access=limited |last=Cohen |first=Joel S. | date = 2003 |publisher=AK Peters
== Computer science aspects ==
=== 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
==== Numbers ====
The usual
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.▼
▲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)]], 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
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
Even programs may be considered and represented as expressions with operator
This process of delayed evaluation is fundamental in computer algebra. For example, the operator
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 [[Pointer (computer programming)|pointers]] (like in [[Macsyma]])<ref>{{Cite book |url=https://people.eecs.berkeley.edu/~fateman/macsyma/docs/refman16.pdf |title=Macsyma Mathematics and System Reference Manual |publisher=[[Macsyma]] |year=1996 |pages=419}}</ref> or entries in a [[hash table]] (like in [[Maple (software)|Maple]]).
=== Simplification ===
The raw application of the basic rules of [[derivative|differentiation]] with respect to {{math|''x''}} on the expression {{Math|''a''<
:<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
▲This simplification is normally done through [[rewriting|rewriting rules]].<ref>Buchberger, Bruno, and Rüdiger Loos. "[https://www.risc.jku.at/people/buchberg/papers/1982-00-00-B.pdf Algebraic simplification]." Computer algebra. Springer, Vienna, 1982. 11-43.</ref> 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 {{math|''E'' − ''E'' → 0}} or {{math|sin(0) → 0}}. They are systematically applied in computer algebra systems.
▲The first 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''}}. What about {{math|''a'' − ''b'' + ''c''}}? To deal with this problem, the simplest way is to rewrite systematically {{math|−''E''}}, {{math|''E'' − ''F''}}, {{math|''E''/''F''}} as, respectively, {{math|(−1)⋅''E''}}, {{math|''E'' + (−1)⋅''F''}}, {{math|''E''⋅''F''<sup>−1</sup>}}. 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.
Some rewriting rules sometimes increase and sometimes decrease the size of the expressions to which they are applied. This is the case
▲A second difficulty occurs with the [[commutativity]] 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]] 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 (software)|Maple]], the [[hash function]] 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]] or [[Trigonometric identity#Product-to-sum and sum-to-product identities|trigonometric identities]]. For example, the distributivity 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 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]]).
== Mathematical aspects ==
:<math>(\sin(x+y)^2+ \log(z^2-5))^3</math>
is viewed as a polynomial in <math>\sin(x+y)</math> and <math>\log(z^2-5)</math>.
=== Equality ===
There are two notions of equality for [[expression (mathematics)|mathematical expressions]].
:<math> (x+y)^2=x^2+2xy+y^2.</math>
It is known from [[Richardson's theorem]] that there may not exist an algorithm that decides
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.
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
==History==
=== Human-driven computer algebra ===
Early computer algebra systems, such as the [[ENIAC]] at the [[University of Pennsylvania]], relied on [[Computer (occupation)|human computers]] or programmers to reprogram it between calculations, manipulate its many physical modules (or panels), and feed its IBM card reader.<ref>[http://www.seas.upenn.edu/about-seas/eniac/operation.php "ENIAC in Action: What it Was and How it Worked"]. ''ENIAC: Celebrating Penn Engineering History''. University of Pennsylvania. Retrieved December 3, 2023.</ref> Female mathematicians handled the majority of ENIAC programming human-guided computation: [[Jean Bartik|Jean Jennings]], [[Marlyn Meltzer|Marlyn Wescoff]], [[Ruth Teitelbaum|Ruth Lichterman]], [[Betty Holberton|Betty Snyder]], [[Frances Spence|Frances Bilas]], and [[Kathleen Antonelli|Kay McNulty]] led said efforts.<ref>{{Cite journal |last=Light |first=Jennifer S. |date=1999 |title=When Computers Were Women |url=https://muse.jhu.edu/article/33396 |journal=Technology and Culture |language=en |volume=40 |issue=3 |pages=455–483 |doi=10.1353/tech.1999.0128 |issn=1097-3729|url-access=subscription }}</ref>
=== Foundations and early applications ===
In 1960, [[John McCarthy (computer scientist)|John McCarthy]] explored an extension of [[Primitive recursive function|primitive recursive functions]] for computing symbolic expressions through the [[Lisp (programming language)|Lisp]] programming language while at the [[Massachusetts Institute of Technology]].<ref>{{Cite journal |last=McCarthy |first=John |date=1960-04-01 |title=Recursive functions of symbolic expressions and their computation by machine, Part I |journal=Communications of the ACM |volume=3 |issue=4 |pages=184–195 |doi=10.1145/367177.367199 |issn=0001-0782|doi-access=free }}</ref> Though his series on "Recursive functions of symbolic expressions and their computation by machine" remained incomplete,<ref>{{Cite book |last=Wexelblat |first=Richard L. |title=History of programming languages |date=1981 |publisher=Academic press |others=History of programming languages conference, Association for computing machinery |isbn=978-0-12-745040-7 |series=ACM monograph series |___location=New York London Toronto}}</ref> McCarthy and his contributions to artificial intelligence programming and computer algebra via Lisp helped establish [[MIT Computer Science and Artificial Intelligence Laboratory|Project MAC]] at the Massachusetts Institute of Technology and the organization that later became the [[Stanford University centers and institutes|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.<ref>{{Cite journal |date=1985-03-01 |title=Symbolic Computation (An Editorial) |url=https://www.sciencedirect.com/science/article/pii/S0747717185800250 |journal=Journal of Symbolic Computation |volume=1 |issue=1 |pages=1–6 |doi=10.1016/S0747-7171(85)80025-0 |issn=0747-7171|url-access=subscription }}</ref> Predecessors to Project MAC, such as [[ALTRAN]], sought to overcome algorithmic limitations through advancements in hardware and interpreters, while later efforts turned towards software optimization.<ref>{{Cite journal |last=Feldman |first=Stuart I. |date=1975-11-01 |title=A brief description of Altran |url=https://dl.acm.org/doi/10.1145/1088322.1088325 |journal=ACM SIGSAM Bulletin |volume=9 |issue=4 |pages=12–20 |doi=10.1145/1088322.1088325 |issn=0163-5824}}</ref>
=== Historic problems ===
A large part of the work of researchers in the field consisted of revisiting classical [[algebra]] to increase its [[Computable function|effectiveness]] while developing [[Algorithmic efficiency|efficient algorithms]] for use in computer algebra. An example of this type of work is the computation of [[Polynomial greatest common divisor|polynomial greatest common divisors]], a task required to simplify fractions and an essential component of computer algebra. Classical algorithms for this computation, such as [[Euclidean algorithm|Euclid's algorithm]], proved inefficient over infinite fields; algorithms from [[linear algebra]] faced similar struggles.<ref>{{Citation |last=Kaltofen |first=E. |title=Factorization of Polynomials |date=1983 |url=http://link.springer.com/10.1007/978-3-7091-7551-4_8 |work=Computer Algebra |series=Computing Supplementa |volume=4 |pages=95–113 |editor-last=Buchberger |editor-first=Bruno |access-date=2023-11-29 |place=Vienna |publisher=Springer Vienna |doi=10.1007/978-3-7091-7551-4_8 |isbn=978-3-211-81776-6 |editor2-last=Collins |editor2-first=George Edwin |editor3-last=Loos |editor3-first=Rüdiger |editor4-last=Albrecht |editor4-first=Rudolf|url-access=subscription }}</ref> 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 Euclidean algorithm.
== Algorithms used in computer algebra ==
{{excerpt|List of algorithms|Computer algebra}}
== See also ==
* [[Automated theorem prover]]
Line 88 ⟶ 94:
* [[Computational algebraic geometry]]
* [[Computer algebra system]]
* [[Differential analyser]]
* [[Proof checker]]
* [[Model checker]]
Line 99 ⟶ 106:
== Further reading ==
For a detailed definition of the subject:
*
For textbooks devoted to the subject:
*{{cite book |first1=James H. |last1=Davenport |author1-link=James H. Davenport |first2=Yvon |last2=Siret |first3=Èvelyne |last3=Tournier |title=Computer
*{{cite book |first1=Joachim |last1=von zur Gathen |first2=Jürgen |last2=Gerhard |title=Modern computer algebra |edition=
*{{Cite
*{{Cite
{{Computer algebra systems}}
{{Computer science}}
{{Areas of mathematics
{{Authority control}}
| |||