The Risch Algorithm
Date: 11/30/98 at 06:56:30 From: Robert Macho Subject: Symbolic simplification and integration I am developing an application that should simplify and integrate mathematical functions of one variable. Is there a known algorithm for doing that? Thank you for your answer.
Date: 11/30/98 at 07:55:01 From: Doctor Jerry Subject: Re: Symbolic simplification and integration Hi Robert, Here's a bit of information that I collected some time ago about the Risch algorithm: Elementary functions in the context of algebraic integration theory are rational functions, exponentials, logarithms, algebraic functions (i.e., the solution of a polynomial equation whose coefficients are elementary functions), and trigonometric and hyperbolic functions and their inverses (these are, of course, expressed using exponentials, logarithms and square roots, where the constant field contains i with i^2 + 1 = 0). More algebraically, let K(x) denote the rational function field over the field K. Then the field of the elementary functions can be denoted by: K(x, theta_1, theta_2, ..., theta_n), where the theta_k are either logarithmic, exponential or algebraic over K. (1) theta is logarithmic over K if there exists an element u in K such that D(theta) = D(u)/u ("theta = log(u)"). (2) theta is exponential over K if there exists an element u in K such that D(theta) = theta * D(u) ("theta = exp(u)"). (3) theta is algebraic over K if there exists a polynomial p in F[z] such that P(theta) = 0. Here D is the (algebraic) differentation operator, which is a mapping from K to K such that for all f and g in K: (1) D(f+g) = D(f) + D(g) and (2) D(f*g) = f*D(g) + D(f)*g. These two relations suffice to yield the desired properties of the derivation. We get the usual differentiation if we define D(x):= 1. As an easy example, consider the algebraic field extension R(x,w) of the rational functions over the reals, R(x), where w^2-x = 0. What is the derivative of w? From w^2-x = 0 we get 2*w*D(w)-1 = 0, which yields D(w) = 1/(2*w). Of course, w = sqrt(x). An elementary function f is elementarily integrable, if there exists another elementary function g such that D(g) = f. Examples of not elementarily integrable functions are 1/log(x), exp(x^2) and exp(-x^2). The Risch algorithm decides if an elementary function is elementarily integrable, and returns its integral (if it exists). The algorithm is described (in about 100 pages) in "Algorithms for Computer Algebra" by Keith O. Geddes, Stephen R. Czapor and George Labahn (who were involved in the development of Maple). The Risch algorithm is about twenty or thirty years old. An important part is Liouville's Principle, which dates back to the 19th century. Yours, Clemens Heitzinger - Doctor Jerry, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.