What is the Risch Algorithm

reading corner

Symbolic integration I

Manuel Bronstein
Springer-Verlag, Berlin-Heidelberg-New York, 1997, DM 78.00; öS 569.40; sFr 69.00
2nd edition: Springer-Verlag, Berlin-Heidelberg-New York, 2005, 53.45 euros

ISBN 3-540-60521-5
ISBN 3-540-21493-3

Then come the Reviews of: 1st edition and2nd Edition

Review of the 1st edition

Since the last book Integration in finite terms on this subject in 1948 by J.F. Almost fifty years have passed by RITT, and during this time symbolic integration has been decisively developed. Computer algebra had an important influence on the flourishing of this theory, the requirements of which led to a connection to the algorithmic traditions of mathematics of the last century. From this point of view, the problem to be solved can be formulated as follows: Find an elementary antiderivative for every given elementary function algorithmically or prove (algorithmically) that there cannot be any.

In the first 1905 edition of his book The integration of functions of a single variable suspected G.H. HARDY on page 7 that the problem for the elementary functions would never be solved: Complete answers to these questions have not and probably never will be given.

Interestingly enough, the author replaced this passage in the 2nd edition in 1916 on page 8 with the following sentence: It would be unreasonable to expect complete answers to these questions.

In 1969, R.H. RISCH has been given a decision-making process. Much more work following R.H. However, RISCH were necessary to enable implementations for certain sub-classes of functions in the various computer algebra systems. In addition to the work of B. TRAGER, ROTHSTEIN and others, the author of the present book deserves special mention.

In this book - the first volume in the new Springer series on the subject Algorithms and Computations in Mathematics becomes the algorithmic theory of symbolic integration that has been developed to this day more transcendent Functions fully presented as a math textbook. In addition to the theory, all sections contain the respective algorithms in pseudocode, which can be converted almost directly into executable implementations by any (further) developer of a computer algebra system.

After a brief reminder of the basic algorithms required in computer algebra such as Euclidean algorithm, resultants and square-free factorization of polynomials in the first chapter the algorithmic theory of the integration of rational functions is discussed in detail and with the different variants - of Bernoulli, Hermite, Horowitz-Ostrogradsky, Rothstein-Trager, Lazard-Rioboo-Trager to the latest ideas from Czichowski, who brings Groebner-based techniques into this theory. This level of detail is necessary because the ideas of the theory for the rational functions must be applied to the classes of transcendent functions.

For this purpose, Chapter 3 gives an introduction to the theory of differential bodies with transcendent extensions k(x)(t) of the rational body of functions k(x) as an introduction to the tangent function t : = tan (x) solely through their law of derivation German = t2 + 1 to be able to interpret. This algebraization is the decisive key to solving this problem from analysis and also confirms the naming of the field of computersalgebra.

Chapter 4 provides the necessary tools from valuation theory and thus the properties of the important ones Rothstein-Trager resultants derived.

The core of the book is Chapter 5 on the integration of transcendent functions. With the proof of Liouville's theorem, it contains the decisive structural statement for the form of an elementary integral. The various reduction techniques are initially explained in an overview in Section 5.2 and shown schematically in Figure 5.1 and then elaborated. Depending on the law of derivation - primitive case with Dt in the body (example t : = log (x)), hyperexponential case with Dt a polynomial of degree 1 (example t : = exp (x)) or the hypertangential case with Dt a polynomial of degree 2 (example t : = tan (x)) - the algorithm branches out and sub-algorithms that are adapted to the given situation are required limited Integration, solving the differential equation of RISCH or solving a coupled system of two differential equations in the three cases either recursively reduce the problem to a simpler situation by eliminating t or show the non-existence of an elementary integral at this point.

Chapter 6 is the algorithmic details for solving the Risch differential equation in Chapter 7 the various parametric problems are solved and Chapter 8 is finally devoted to the solution of the coupled differential equations that occur.

In the final chapter, structural statements are proven that are necessary to decide whether new constants arise in the construction of the functional fields by successive adjoint logarithms or exponential functions.

With its exercises and the algorithms given, the book is well suited to serve as a basis for lectures with exercises Symbolic integration, differential algebra and of course to Computer algebra to serve. This monograph on one of the fascinating basic topics of computer algebra should not be missing in any working group. It is also - for example after reading an overview article (e.g. R. KRAUME Symbolic integration im Spektrum der Wissenschaft 3 (1996), pp. 95-98 or An introduction to the computer algebra algorithms for symbolic integration, Wiss. Reports of the FZ Karlsruhe (1996) pp. 69-113 of the undersigned) - of interest for high school or technical college teachers who use computer algebra systems in their teaching who are interested in deepening and background information on the algorithms of a computer algebra system.

We hope that the all-round successful book will be widely distributed, and that the author will soon have the time to follow up with a second part on the theory of the symbolic integration of algebraic functions!

Review: Johannes Grabmeier (Heidelberg) from Computeralgebra-Rundbrief, No. 20 - March 1997

Review of the 2nd editione

Shortly before his death (see obituary on page 37 in the Computeralgebra-Rundbrief, No. 37 - October 2005) the second edition of this monograph on symbolic integration was published. The first edition appeared in 1997 and was discussed in detail by the undersigned in the computer algebra circular number 20 from spring 1997 (see above).

The book is the standard work on the question of how an algorithm can be used to decide whether the antiderivative of an elementary function is elementary again or not. In the first case, this is then also calculated. The Roman one refers to the class of transcendent functions exclusively dealt with in this book.

The nine chapters of the first edition could remain almost unchanged, only minor error corrections - it is difficult to find them at all - have been incorporated. Completely new, however, is Chapter 10 on “Parallel Integration”. Here the author has processed and supplemented ideas by Risch, Norman, Davenport, Trager and others, some of which go back to 1976, in the style of the book. The starting point for this theory is the central theorem of Liouville, which states that the integrand in the case of elementary integrability is in the form

can represent. There are those ui multivariate polynomials in the transcendent field extensions of the constant field, v accordingly a rational function and D the derivation (see (10.1) on page 297). Well be for that ui, for the denominator of v and the degree of the numerator of v made sensible approaches. That happens in parallel! The calculation of the algebraic quantities is then reduced to solving linear systems of equations. If you are successful, you have found an antiderivative very quickly and efficiently, if not, then of course you don't know anything, since the approaches can be wrong. This makes the method a heuristic, which is used very successfully in some computer algebra systems.

Bronstein himself published a Maple implementation with less than 100 lines of code on May 10, 2005. Pmint stands for "Pure Man’s Integrator". Bronstein writes about it

"It is based on recent improvements to a powerful heuristic called parallel integration. While it is not meant to be as complete as the large commercial integrators based on the Risch algorithm, its very small size makes it easy to port to any computer algebra system or library capable of factoring multivariate polynomials. Because it is applicable to special functions (such as Airy, Bessel, Whittaker, Lambert), it is able to compute integrals not handled by the existing integrators. pmint is not meant as a replacement for existing integrators, but either as an extension, or as a cheap and powerful alternative for any computer algebra project. "

My discussion of the 1997 first edition ended with the following wish: "We hope that the all-round successful book will be widely distributed, and that the author will soon have the time to follow a second part on the theory of the symbolic integration of algebraic functions!" The first part of the wish has come true with this new edition and is still valid, the second part can no longer be fulfilled.

Review: Johannes Grabmeier (Deggendorf) from Computeralgebra-Rundbrief, No. 37 - October 2005


Category: Reading corner