← Back
Home › Systems › Numerical and mathematical computing

computer-algebra

computer algebra system

Mathematica, SymPy

SystemTechniques · 4Primitives · 11 computer-algebra Term rewritingcompilers · medium: Rewrite systems with pattern matching, confluence and termination ordersGroebner basesnumerics · medium: Buchberger and F4 algorithms for polynomial ideals; solving polynomial systemsPolynomial gcd factorizationnumerics · medium: Polynomial GCD (subresultant, modular) and factorization (Berlekamp, Zassenhaus)Symbolic integrationnumerics · medium: Rule-based and Risch-style antiderivatives, Hermite reduction for rational functionsUnificationcompilers · low: First-order unification with union-find and occurs check; basis of type inference and logic programmingHash consingdata-structures · low: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximalBig integer arithmeticnumerics · low: Multi-limb integer arithmetic (256-bit and up): carries, Karatsuba, Montgomery and Barrett reductionNumber theoretic transformnumerics · low: FFT over finite fields for exact polynomial and big-integer multiplicationE graphscompilers · low: Equality saturation: e-graphs compactly hold many equivalent programs, then extract the cheapestPratt parsingcompilers · low: Table-driven expression parsing with one loop and a numeric binding power per operator; the compact core of precedence handling in hand-written parsers.›Fast Fourier transformnumerics · low: Computes the DFT in O(n log n) by recursively splitting into even and odd halves; the basis of fast convolution and spectral methods.›Interval arithmeticnumerics · low: Rigorous bounds with outward rounding; root isolation and robust geometric testsTree pattern matchingcompilers · low: Matching AST patterns with metavariablesFinite field arithmeticnumerics · low: Prime-field and extension-field arithmetic (Montgomery form, Goldilocks, BabyBear), vectorizedSparse matrices (CSR)numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›