Computer algebra: Difference between revisions

Revision as of 16:33, 6 February 2025

Latest revision as of 13:11, 23 May 2025

(3 intermediate revisions by 3 users 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 60:

Some fundamental mathematical questions arise when one wants to manipulate [[expression (mathematics)|mathematical expressions]] in a computer. We consider mainly the case of the [[Multivariate polynomial|multivariate]] [[rational fraction]]s. This is not a real restriction, because, as soon as the [[irrational function]]s appearing in an expression are simplified, they are usually considered as new indeterminates. For example,

:<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]]. '''Syntactic equality''' is the equality of their representation in a computer. This is easy to test in a program. ''Semantic equality'' is when two expressions represent the same mathematical object, as in

:<math> (x+y)^2=x^2+2xy+y^2.</math>

Line 72:

In computer algebra, "canonical form" and "normal form" are not synonymous.<ref>{{cite book |last1=Davenport |first1=J. H. |last2=Siret |first2=Y. |last3=Tournier |first3=É. |title=Computer Algebra: Systems and Algorithms for Algebraic Computation |publisher=Academic |date=1988 |isbn=0-12-204230-1 |oclc=802584470 }}</ref> A ''canonical form'' is such that two expressions in canonical form are semantically equal if and only if they are syntactically equal, while a ''normal form'' is such that an expression in normal form is semantically zero only if it is syntactically zero. In other words, zero has a unique representation as an expression in normal form.

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 every product through the [[distributivity|distributive law]], while it is not necessary with a normal form (see below). Secondly, it may be the case, like for expressions involving radicals, that a canonical form, if it exists, depends on some arbitrary choices and that these choices may be different for two expressions that have been computed independently. This may make impracticable the use of a canonical form impractical.

==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 ==