# Computer algebra Computer algebra — symbolic computation — is the branch of [[Computer_science]] and [[Computational_mathematics]] that manipulates mathematical expressions *exactly*, as structured symbols, rather than approximately, as floating-point numbers. Where numerical software returns 0.333333, a computer algebra system returns 1/3; where a solver samples a [[Differential_equation]], a symbolic engine may return its closed form. The field runs on [[Algorithm|algorithms]] from [[Abstract_algebra]] — greatest common divisors, factorization over a [[Field_(mathematics)|field]], Gröbner bases — implemented in [[Mathematical_software]] whose lineage runs from MIT's Macsyma (1968) through Maple (early 1980s) and Mathematica (1988) to the open-source SageMath (2005). Its constraints are equally fundamental: intermediate expressions can swell exponentially, key problems sit near the hardness ceilings of the [[Theory_of_computation]], and by Richardson's theorem (1968) some symbolic questions are outright undecidable — honest limits on what any [[Artificial_intelligence|symbolic reasoner]] can promise. ## Exact objects, exact arithmetic The base layer is arbitrary-precision arithmetic: integers grow to any length, rationals never round, and algebraic numbers travel with their minimal polynomials over the ground [[Field_(mathematics)|field]]. Fast multiplication makes this affordable — Karatsuba (1962) cut the classical n² bit cost to about n¹·⁵⁸⁵, Schönhage–Strassen (1971) reached O(n log n log log n) via fast [[Fourier_analysis|Fourier]] convolution, and Harvey–van der Hoeven (2019) closed the gap at O(n log n). These kernels, tuned to cache and word size on real [[Computer_architecture|hardware]], are the same big-integer engines that power [[Cryptography|RSA key generation]]. On top sit exact polynomials, matrices over rings ([[Linear_algebra]] without rounding), truncated power series from [[Calculus]], and symbolic [[Tensor|tensors]] — each with [[Algorithmic_efficiency|complexity]] budgets that the [[Algorithm|algorithm]] designer must respect, because exactness makes every wasted digit permanent. ## The classical engine: gcd, factorization, and swell Run Euclid's [[Algorithm|algorithm]] naively on two integer polynomials and the coefficients explode — the canonical *intermediate expression swell*, where a one-line answer hides behind pages of intermediate fractions. The cure is modular arithmetic: compute images modulo many primes, in small finite [[Field_(mathematics)|fields]], and reassemble by the Chinese remainder theorem (Brown, 1971), a strategy with the flavor of redundant encoding in [[Error_detection_and_correction]]. Factorization follows the same arc: Berlekamp (1967) factors polynomials over finite fields in polynomial time; Hensel lifting raises the result to the integers; and the LLL lattice-reduction algorithm (1982) — a [[Discrete_geometry|geometry-of-numbers]] tool that also breaks knapsack [[Cryptography|cryptosystems]] — made rational factorization provably polynomial. The lesson generalizes across [[Computational_mathematics]]: compute where arithmetic is cheap, then transport the answer back. ## Deciding the doable: Risch, Zeilberger, Tarski, Richardson Symbolic computation's proudest results are *decision procedures*. The Risch algorithm (1969) decides whether an elementary antiderivative exists — settling in finite time what tables and intuition once guessed at, and explaining why ∫e^(−x²)dx has no elementary form. Gosper's algorithm (1978) does the same for hypergeometric summation, and Zeilberger's creative telescoping (about 1990) proves binomial identities automatically, a working fragment of automated mathematics. Tarski showed the [[First-order_logic|first-order theory]] of the reals admits quantifier elimination — every polynomial ∃/∀ question over ℝ is decidable — with Collins's cylindrical algebraic decomposition (1975) as the practical, doubly exponential engine used in verified [[Control_theory|control design]]. Against these stands Richardson's theorem (1968): once expressions may contain sin, exp, |·| and π, deciding whether an expression equals zero is undecidable — a permanent boundary inherited from the [[Theory_of_computation]] and [[Logic]]. ## Gröbner bases and the price of generality Buchberger's Gröbner bases (1965) reduce questions about systems of polynomial equations — membership, elimination, solving — to a completed set of divisors under a monomial order, making the ideal–variety dictionary of [[Algebraic_geometry]] executable. The worst case is fearsome: ideal membership is EXPSPACE-hard (Mayr–Meyer, 1982) with doubly exponential degree growth, so no [[Algorithmic_efficiency|complexity]] guarantee protects the general user. Practice is kinder. Faugère's F4/F5 refinements (1999, 2002) and tuned implementations dispatch structured systems daily: forward and inverse kinematics in [[Robotics]], steady states of mass-action [[Ordinary_differential_equation|ODE]] networks in [[Systems_biology]], symbolic transfer-function manipulation for [[Linear_time-invariant_system|LTI]] models in [[Control_theory]], and polynomial [[Mathematical_optimization|optimization]] via sums of squares. The pattern is constant: exponential in principle, workable on the structured instances science actually asks. ## Lineages: from SAINT to Sage The field is nearly as old as [[Artificial_intelligence]] itself. Slagle's SAINT (1961) did freshman integration as a heuristic search; Veltman's Schoonschip (1963) automated the [[Tensor|tensor]] algebra of particle physics and helped earn a Nobel Prize; Macsyma (MIT, 1968) and REDUCE (late 1960s) proved general-purpose symbolic [[Computer_programming|programming]] viable. Maple (Waterloo, early 1980s) and Mathematica (1988) carried computer algebra to the desktop, growing handbook literatures — [[Victor_Aladjev]]'s volumes on both systems among them — while specialized engines went deeper: GAP (mid-1980s) for [[Group_theory]], Singular and Macaulay2 for [[Algebraic_geometry]], PARI for number theory. SageMath (2005) federated dozens of these behind one open interface, and symbolic kernels now sit quietly inside [[Simulation]] toolchains, generating exact Jacobians and code for [[Engineering_mathematics|engineering]] models. ## What exactness buys the sciences Symbolic computation earns its keep where approximation would blur the object of interest. In [[General_relativity]], curvature computations that consumed months by hand are routine [[Tensor]] algebra; in celestial mechanics, the 1970 machine re-derivation of Delaunay's twenty-year hand expansion of lunar motion confirmed it almost error-free — the founding audit of symbolic [[Simulation]]. Exact linear-system solving over ℚ certifies results that floating point can only suggest, a [[Correctness_(computer_science)|correctness]] guarantee prized in computer-assisted proofs. Symbolic differentiation coexists with the automatic differentiation that trains [[Neural_network_(machine_learning)|neural networks]] — the two are cousins, not twins, since autodiff evaluates derivatives without ever building the swollen expression tree. And in the classroom and the lab alike, computer algebra is [[Applied_mathematics]] made tangible: a place where the theorems of [[Abstract_algebra]] compile and run. **On the spine:** [[Computational_mathematics]] · [[Abstract_algebra]] · [[Algorithm]] · [[Algebraic_geometry]] · [[Mathematical_software]]. ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Computer_algebra) : [Wikitube](https://en.wikitube.io/wiki/Computer_algebra) ## Previous hub tags Hubs: `Systems`. Portals: [[PORTAL_Systems]], [[PORTAL_Graph_theory]], [[PORTAL_Decision_theory]], [[PORTAL_Information_theory]], [[PORTAL_Control_theory]]. --- *Repopulated 2026-08-12 · redlink fill · 0 deletions.*