Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
College Algorithms

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/