This is documentation for Mathematica 4, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)
Wolfram Research, Inc.

Numerical and Related FunctionsOutput and Interfacing

A.9.5 Algebra and Calculus

Polynomial manipulation

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

FilledSmallCircle Factoring over algebraic number fields is done by finding a primitive element over the rationals and then using Trager's algorithm.

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

FilledSmallCircle The internal code for Factor exclusive of general polynomial manipulation is about 250 pages long.

FilledSmallCircleFactorSquareFree works by finding a derivative and then iteratively computing GCDs.

FilledSmallCircleResultant uses either explicit subresultant polynomial remainder sequences or modular sequences accompanied by the Chinese Remainder Theorem.

FilledSmallCircleApart uses either a version of the Padé technique or the method of undetermined coefficients.

FilledSmallCirclePolynomialGCD and Together usually use modular algorithms, including Zippel's sparse modular algorithm, but in some cases use subresultant polynomial remainder sequences.

FilledSmallCircle For multivariate polynomials the Chinese Remainder Theorem together with sparse interpolation are also used.

Symbolic linear algebra

FilledSmallCircleRowReduce, LinearSolve and NullSpace are based on Gaussian elimination.

FilledSmallCircleInverse uses cofactor expansion and row reduction. Pivots are chosen heuristically by looking for simple expressions.

FilledSmallCircleDet uses direct cofactor expansion for small matrices, and Gaussian elimination for larger ones.

FilledSmallCircleMatrixExp finds eigenvalues and then uses Putzer's method.

FilledSmallCircle 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

FilledSmallCircle For linear equations Gaussian elimination and other methods of linear algebra are used.

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

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

FilledSmallCircle For systems of polynomial equations, Solve constructs a Gröbner basis.

FilledSmallCircleSolve and GroebnerBasis use an efficient version of the Buchberger algorithm.

FilledSmallCircle For non-polynomial equations, Solve attempts to change variables and add polynomial side conditions.

FilledSmallCircle The code for Solve is about 500 pages long.

Simplification

FilledSmallCircleFullSimplify automatically applies about 40 types of general algebraic transformations, as well as about 400 types of rules for specific mathematical functions.

FilledSmallCircle Generalized hypergeometric functions are simplified using about 70 pages of Mathematica transformation rules. These functions are fundamental to many calculus operations in Mathematica.

FilledSmallCircleFunctionExpand uses an extension of Gauss's algorithm to expand trigonometric functions with arguments that are rational multiples of .

FilledSmallCircleSimplify and FullSimplify cache results when appropriate.

FilledSmallCircle When assumptions specify that variables are real, methods based on cylindrical algebraic decomposition are used to deduce what transformations can be applied.

FilledSmallCircle For general polynomial inequalities, a version of the Collins algorithm is used with McCallum's improved projection operator. For strict inequalities, Strzebonski's method is used. For linear inequalities, methods based on either the simplex algorithm or the Loos-Weispfenning linear quantifier elimination algorithm are used.

FilledSmallCircle When assumptions involve equations among polynomials, Gröbner basis methods are used.

FilledSmallCircle For non-algebraic functions, a database of relations is used to determine the domains of function values from the domains of their arguments. Polynomial-oriented algorithms are used whenever the resulting domains correspond to semi-algebraic sets.

FilledSmallCircle For integer functions, several hundred theorems of number theory are used in the form of Mathematica rules.

Differentiation and integration

FilledSmallCircle Differentiation uses caching to avoid recomputing partial results.

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

FilledSmallCircle For other indefinite integrals, heuristic simplification followed by pattern matching is used.

FilledSmallCircle The algorithms in Mathematica cover all of the indefinite integrals in standard reference books such as Gradshteyn-Ryzhik.

FilledSmallCircle Definite integrals that involve no singularities are mostly done by taking limits of the indefinite integrals.

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

FilledSmallCircleIntegrate uses about 500 pages of Mathematica code and 600 pages of C code.

Differential equations

FilledSmallCircle Systems of linear equations with constant coefficients are solved using matrix exponentiation.

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

FilledSmallCircle Higher-order linear equations are solved using Abramov and Bronstein algorithms.

FilledSmallCircle Linear equations with polynomial coefficients are solved in terms of special functions by using Mellin transforms.

FilledSmallCircle When possible, nonlinear equations are solved by symmetry reduction techniques. For first-order equations classical techniques are used; for second-order equations and systems integrating factor and Bocharov techniques are used.

FilledSmallCircle The algorithms in Mathematica cover most of the ordinary differential equations in standard reference books such as Kamke.

FilledSmallCircle For partial differential equations, separation of variables and symmetry reduction are used.

FilledSmallCircleDSolve uses about 300 pages of Mathematica code and 200 pages of C code.

Sums and products

FilledSmallCircle Polynomial series are summed using Bernoulli and Euler polynomials.

FilledSmallCircle Series involving rational and factorial functions are summed using Adamchik techniques in terms of generalized hypergeometric functions, which are then simplified.

FilledSmallCircle Series involving polygamma functions are summed using integral representations.

FilledSmallCircle Dirichlet and related series are summed using pattern matching.

FilledSmallCircle For infinite series, d'Alembert and Raabe convergence tests are used.

FilledSmallCircle The algorithms in Mathematica cover at least 90% of the sums in standard reference books such as Gradshteyn-Ryzhik.

FilledSmallCircle Products are done primarily using pattern matching.

FilledSmallCircleSum and Product use about 100 pages of Mathematica code.

Series and limits

FilledSmallCircleSeries works by recursively composing series expansions of functions with series expansions of their arguments.

FilledSmallCircle Limits are found from series and using other methods.

Numerical and Related FunctionsOutput and Interfacing