A.9.5 Algebra and Calculus
For univariate polynomials, Factor uses a variant of the Cantor-Zassenhaus algorithm to factor modulo a prime, then uses Hensel lifting and recombination to build up factors over the integers.
Factoring over algebraic number fields is done by finding a primitive element over the rationals and then using Trager's algorithm.
For multivariate polynomials Factor works by substituting appropriate choices of integers for all but one variable, then factoring the resulting univariate polynomials, and reconstructing multivariate factors using Wang's algorithm.
The internal code for Factor exclusive of general polynomial manipulation is about 250 pages long.
FactorSquareFree works by finding a derivative and then iteratively computing GCDs.
Resultant uses either explicit subresultant polynomial remainder sequences or modular sequences accompanied by the Chinese Remainder Theorem.
Apart uses either a version of the Padé technique or the method of undetermined coefficients.
PolynomialGCD usually uses modular algorithms, including Zippel's sparse modular algorithm, but in some cases uses subresultant polynomial remainder sequences.
Symbolic linear algebra
RowReduce, LinearSolve and NullSpace are based on Gaussian elimination.
Inverse uses cofactor expansion and row reduction. Pivots are chosen heuristically by looking for simple expressions.
Det uses direct cofactor expansion for small matrices, and Gaussian elimination for larger ones.
MatrixExp finds eigenvalues and then uses Putzer's method.
Zero testing for various functions is done using symbolic transformations and interval-based numerical approximations after random numerical values have been substituted for variables.
Exact equation solving
For linear equations Gaussian elimination and other methods of linear algebra are used.
Root objects representing algebraic numbers are usually isolated and manipulated using validated numerical methods. With ExactRootIsolation->True, Root uses for real roots a continued fraction version of an algorithm based on Descartes' rule of signs, and for complex roots the Collins-Krandick algorithm.
For single polynomial equations, Solve uses explicit formulas up to degree four, attempts to reduce polynomials using Factor and Decompose, and recognizes cyclotomic and other special polynomials.
For systems of polynomial equations, Solve constructs a Gröbner basis.
Solve and GroebnerBasis use an efficient version of the Buchberger algorithm.
For non-polynomial equations, Solve attempts to change variables and add polynomial side conditions.
The code for Solve is about 500 pages long.
FullSimplify automatically applies about 40 types of general algebraic transformations, as well as about 100 types of rules for specific mathematical functions.
Generalized hypergeometric functions are simplified using about 70 pages of Mathematica transformation rules. These functions are fundamental to many calculus operations in Mathematica.
For indefinite integrals, an extended version of the Risch algorithm is used whenever both the integrand and integral can be expressed in terms of elementary functions, exponential integral functions, polylogarithms and other related functions.
For other indefinite integrals, heuristic simplification followed by pattern matching is used.
The algorithms in Mathematica cover all of the indefinite integrals in standard reference books such as Gradshteyn-Ryzhik.
Definite integrals that involve no singularities are mostly done by taking limits of the indefinite integrals.
Many other definite integrals are done using Marichev-Adamchik Mellin transform methods. The results are often initially expressed in terms of Meijer G functions, which are converted into hypergeometric functions using Slater's Theorem and then simplified.
Integrate uses about 500 pages of Mathematica code and 600 pages of C code.
Linear equations with constant coefficients are solved using matrix exponentiation.
Second-order linear equations with variable coefficients whose solutions can be expressed in terms of elementary functions and their integrals are solved using the Kovacic algorithm.
Linear equations with polynomial coefficients are solved in terms of special functions by using Mellin transforms.
When possible, nonlinear equations are solved by symmetry reduction techniques. For first-order equations classical techniques are used; for second-order equations and systems Bocharov techniques are used.
For partial differential equations, separation of variables and symmetry reduction are used.
DSolve uses about 300 pages of Mathematica code and 200 pages of C code.
Sums and products
Polynomial series are summed using Bernoulli and Euler polynomials.
Series involving rational and factorial functions are summed using Adamchik techniques in terms of generalized hypergeometric functions, which are then simplified.
Series involving polygamma functions are summed using integral representations.
Dirichlet and related series are summed using pattern matching.
For infinite series, d'Alembert and Raabe convergence tests are used.
The algorithms in Mathematica cover at least 90% of the sums in standard reference books such as Gradshteyn-Ryzhik.
Products are done primarily using pattern matching.
Sum and Product use about 100 pages of Mathematica code.
Series and limits
Series works by recursively composing series expansions of functions with series expansions of their arguments.
Limits are found from series and using other methods.