Content deleted Content added
adding a list of algorithms used in computer algebra |
No edit summary |
||
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 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 21:
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 |isbn=978-1-56881-159-8 |page=[https://archive.org/details/computeralgebras00cohe_792/page/n33 14] }}</ref> There are also several other journals that regularly publish articles in computer algebra.<ref>[http://www.sigsam.org/journals.phtml SIGSAM list of journals]</ref>
== Computer science aspects ==
Line 31:
==== Numbers ====
The usual numbers systems used in [[numerical computation]] are [[floating point]] numbers and [[integers]] of a fixed bounded size.
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 ====
Line 88:
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 |url=https://dl.acm.org/doi/10.1145/367177.367199 |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}}</ref> Predecessors to Project MAC, such as [[ALTRAN]], sought to
=== 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]],
== Algorithms used in computer algebra ==
| |||