Computer algebra: Difference between revisions

Revision as of 16:20, 29 November 2023

Revision as of 23:53, 3 December 2023

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]].

=== 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}}</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 |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}}</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 overcame 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]], provided 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 |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}}</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 Euclidian algorithm.

== See also ==