Content deleted Content added
→See also: Comparison of TeX editors Tag: Reverted |
m Open access bot: url-access updated in citation with #oabot. |
||
| (One intermediate revision by one other user not shown) | |||
Line 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 alleviate 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|url-access=subscription }}</ref>
==== Numbers ====
Line 77:
=== 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 ==
Line 92:
* [[Automated theorem prover]]
* [[Computer-assisted proof]]
* [[Computational algebraic geometry]]
* [[Computer algebra system]]
| |||