REDUCE: Overview

Introduction

The first version of REDUCE was developed and published by Anthony C. Hearn over 40 years ago. The starting point was a class of formal computations for problems in high energy physics (Feynman diagrams, cross sections etc.), which are hard and time consuming if done by hand. Although the facilities of the current REDUCE are much more advanced than those of the early versions, the direction towards big formal computations in applied mathematics, physics and engineering has been stable over the years, but with a much broader set of applications.

Like symbolic computation in general, REDUCE has profited by the increasing power of computer architectures and by the information exchange made available by recent network developments. Spearheaded by A.C. Hearn, several groups in different countries take part in the REDUCE development, and the contributions of users have significantly widened the application field.

Today REDUCE can be used on a variety of hardware platforms from personal computers up to advanced workstations and servers.

Although REDUCE is a mature program system, it is extended and updated on a regular basis. Free access is provided on the open source REDUCE web site, http://reduce-algebra.sourceforge.net , as new packages and improvements become available.

Information regarding the available implementations can be obtained from the REDUCE web server. This server also provides copies of REDUCE documentation, as well as a bibliography of papers referencing the system.

Some examples of Reduce programs are given here in Appendix B ReduceAppendixB?.

RemoteWikiURL?: http://reduce-algebra.sourceforge.net

  \begin{reduce}
   REDUCE commands
  \end{reduce}

1  Problem solving

The primary domain of REDUCE is the solution of large scale formal problems in mathematics, science and engineering. REDUCE offers a number of powerful operators which often give an immediate answer to a given problem, e.g. solving a linear equation system or computing a determinant (with symbolic entries, of course). More typical however are relatively complicated applications where only the combination of several evaluation steps leads to the desired result. Consequently the development of REDUCE primarily is oriented towards a collection of powerful tools, which enable problem solving by combination.

In some cases even complete new algorithmic bases will be required for problem solving. REDUCE supports this by various interfaces to all levels of symbolic evaluation, and the modules of REDUCE and of the REDUCE Network Library demonstrate by example how this technique is to be used.

2  Data Types, Structures

2.1  Elementary Expressions

The central object of REDUCE is the formal expression, which is built with respect to the common mathematical rules. Elementary items are

• numbers (integers, rationals, rounded fractionals, real or complex); the domain can be selected dynamically,
• symbols (names with or without indices)
• functional expressions (names followed by a parameter list)
• operator symbols +,-,,/,*
• parentheses for precedence control.

    3.1415928      % fraction
    a              % simple variable
    (x+y)**2 / 2   % quadratic expression
    log(u)+log(v)  % function

2.2  Aggregates

There are data structures that collect a number of formal expressions:

• An equation is an object where the operator = takes highest precedence, with two slots for expressions, the lhs and rhs:

       p=u**2
  

  
  
  
• A list is a linear sequence of expressions, where each of the members is elementary or itself an aggregate. There are operations for construction, join, decomposition and reordering of lists:

      {2,3,5,7,11,13,17,19} 
  

  
  
  
• An array is a rectangular multidimensional structure; the elements are identified by integer indices. Elements always have a value, which defaults to zero.

   array primes(10);
   primes(0):=2;
   for i:=1: 10 do
    primes(i):=nextprime(primes(i-1));
  

  
  
  
• A matrix is a named structure of rows and columns, whose elements are identified by two positive integers. For matrices with compatible dimensions and for matrices and scalars there are operations corresponding to the laws of linear algebra. E.g. using the derivative operator df to construct a Jacobian

     matrix jac(n,n);
     for i:=1:n do for j:=1:n do
      jac(i,j):=df(f(i),x(j));
  

3  Programming Paradigms

For specifying symbolic tasks and algorithms REDUCE offers a set of different programming paradigms:

3.1  Algebraic Desk Calculator

Using REDUCE as a desk calculator for symbolic and numeric expressions is the simplest approach. Formulas can be entered, combined, stored and processed by a set of powerful operators like differentiation, integration, polynomial GCD, factorization etc. Any formula will be processed immediately with the objective of finding its most complete simplification, and the result will be presented on the screen as soon as available.

Example: Taylor polynomial for x*sin(x)

for i:=0:5 sum 
  sub(x=0,df(xsin(x),x,i))  x**i 
            / factorial(i);

4    2
 - ---*X  + X
    6

3.2  Imperative Algebraic Programming

Evaluation of a single formula with the immediate output of the result is a special case of a statement of the REDUCE programming language, which, from a syntactical standpoint, is part of the ALGOL family. This programming language allows the user to code complicated evaluation sequences such as conditionals, groups, blocks, iterations controlled by counters or list structures, and the definition of complete parameterized procedures with local variables.

Example: definition of a procedure for expanding a function to a Taylor polynomial:

procedure tay(u,x,n);
  begin scalar ser,fac;  
    ser:=sub(x=0,u);fac:=1; 
    for i:=1:n do 
    <<u:=df(u,x); fac:=faci;   
      ser:=ser+sub(x=0,u)x**i/fac >>;
    return(ser);  
  end;

tay(x*sin(x),x,5);

    1   4    2
 - ---*X  + X
    6

    P{n+1,x) = ((2n+1)xP(n,x) - n*P(n-1,x))/(n+1)

procedure Legendre_basis(m,x);
  % Start with basis of order 1
   Legendre_basis_aux(m,x,1,{x,1});

procedure Legendre_basis_aux(m,x,n,ls);
    % ls contains polynomials n, n-1, n-2 ...
  if n>=m then ls     % done
  else Legendre_basis_aux(m,x,n+1,
  (((2n+1)xfirst ls - n*second ls)/(n+1))
       . ls);

Legendre_basis(3,z);

  5   3    3
{---Z  - ---Z,
  2        2

2    1
 ---*Z  - ---,
  2        2


 Z, 1}

3.3  Rule Oriented Programming

In REDUCE, global algebraic relations can be formulated with rules. A rule links an algebraic search pattern to a replacement pattern, sometimes controlled by additional conditions. Rules can be activated (and deactivated) globally, or they can be invoked with a limited scope for single evaluations. So the user has an arbitrary precise control over the algebraic simplification.

Example: Expanding trigonometric functions for combined arguments; the tilde symbol represents an implicit for--all.

Sin_Cos_rules:=
{sin(~x+~y)=>sin(x)cos(y) + cos(x)sin(y),
 cos(~x+~y)=>cos(x)cos(y) - sin(x)sin(y)};

let Sin_Cos_rules;

operator Hermite;
Hermite_rules:=
{Hermite(0,~x) => 1,
 Hermite(1,~x) => 2x,
 Hermite(~n,~x) => 2xHermite(n-1,x)
          -2(n-1)*Hermite(n-2,x)
              when n>1};

let Hermite_rules;

Hermite(4,z);

2
16Z  - 48Z  + 12

3.4  Symbolic Imperative Programming

The paradigms described so far give access to the REDUCE facilities at the top level. They enable a compact programming close to the application problem. No knowledge about the internal data structures is necessary, since REDUCE converts data automatically to the formats needed locally for each evaluation step. On the other hand, such frequent conversions are time consuming and so for very large problems it might be desirable to keep intermediate results in the internal form in order to avoid the conversion overhead. Here the ``symbolic'' mode of REDUCE can be used, which allows the access to internal data structures and procedures directly with the same syntax as in top level programming.

Of course, this level of programming requires some knowledge about LISP and about internal REDUCE structures. However, it enables the implementation of algorithms with the highest possible efficiency.

4  Algebraic Evaluation

The evaluation of expressions is the heart of REDUCE. Because of its great complexity, it is only briefly touched on here. One central problem in automatic formula manipulation is the detection of identity between objects, e.g. the confirmation a + b = b + a under the assumption of commutative addition.

It is well known that this problem is equivalent to the problem of recognizing that an expression is zero, in other words to the existence of an algorithm for the transformation of a formula into an equivalent canonical normal form. Unfortunately there is no universal canonical form; only for subcases, for example polynomials, rationals, and ideals, are canonical forms known. Therefore REDUCE evaluation is based on a canonical form for rational functions (i.e., quotients of multivariate polynomials), where symbols or function expressions play the role of variables (REDUCE: kernels). REDUCE attempts to tranform as many functions as possible into the canonical form by applying additional heuristic rules.

A coarse sketch of evaluation is as follows:

• a symbol with an assigned value is replaced by the value,
• a call for a known procedure is replaced by the value produced by the procedure invocation,
• matching rules are applied,
• polynomials are expanded recursively using a lexicographic order of variables (kernels): a multivariate polynomial is a polynomial in its highest variable with decreasing exponents, where the coefficients are polynomials in the remaining variables,
• a rational function is converted into a form with common denominator (i.e., a quotient of two polynomials).

5  Approximations

In the domain of symbolic computation, mostly exact arithmetic is used, especially with algorithms from the classical Computer Algebra. That aspect is supported by REDUCE with arbitrarily long integer arithmetic and, built on top of that, rational and modular (p-adic) numbers.

The values of transcendental functions with general numeric arguments do not fall into these domains, even if symbols like pi, e, i are attached. Nevertheless symbolic computation can be used for fields beyond classical algebra, for example in the domain of analytic approximations in numerical mathematics.

5.1  Power Series

Power series are a valuable tool for the formal approximation of functions, e.g. in the area of differential equations. REDUCE supports several types of power series, among them univariate Taylor series with variable order and multivariate Taylor series with fixed order.

5.2  Rounded Numbers

For several decades, floating point numbers have been recognized as a useful tool for numerical computations, although they do not possess most of the algebraic properties of numbers. In REDUCE they are incorporated as "rounded numbers" which, when compared to classical floating point numbers (e.g. in the IEEE view) they offer interesting additional properties:

• the mantissa length can be selected arbitrarily (i.e., selected as a number of decimal digits),
• there is no limit for the exponent and so no upper or lower limit for the magnitude of a number.

5.3  Interface for Numerical Programs

A field of growing importance for symbolic computation is the use of algorithms of mixed symbolic-numeric type, when for example a symbolic calculation carries out formal transformations on an equation system for control or conditioning of a numerical solver. Examples are the automatic programming of Jacobians for ODE solvers, or the reduction of the order of a system by exploiting formal symmetries. By the cooperation of symbolic and numeric components, REDUCE offers several facilities for the generation of partial or complete programs in languages such as FORTRAN or C. As automatically generated programs tend to flood the target compilers, REDUCE also provides for the optimization of the numeric code.

6  I/O

In interactive mode, REDUCE normally prints results in a two dimensional ``mathematical'' form, where exponents are raised, quotients are printed with denominator below numerator, and matrices are represented as rectangular blocks. The output can be influenced by a variety of switches, e.g. for reordering or collecting of terms.

For special purposes, additional output forms are available:

• linear form: the data can be re-used for later input in REDUCE or another system,
• foreign syntax: the expressions are printed in the syntax of FORTRAN, C or another programming language for the direct insertion in numeric codes,
• TeX?: indirect formatting as input for the TeX? layout program to be inserted into a publication.

      3      2          2    3
Q := X  + 3X Y + 3XY  + Y

Q := X*3 + 3X*2Y + 3XY2 + Y3$

      Q=X*3+3.X*2Y+3.XY2+Y3

7  Open System

In contrast to most other symbolic math systems, REDUCE traditionally is completely open:

• REDUCE is written in a language RLISP, which incorporates the functionality of LISP in a user friendly syntax. At the same time RLISP is the language of application.
  
  
• Traditionally REDUCE is delivered with all sources. So the algorithmic basis is visible to any user. Even the REDUCE translator (compiling RLISP to LISP) is delivered as source code.
  
  
• Any internal REDUCE function and data structure can be accessed by the user directly (in symbolic style programming). Most of the REDUCE implementations contain a LISP compiler, such that the user can produce very efficient modules. REDUCE can be integrated into other (LISP-) packages as an algebraic engine.
  
  
• REDUCE inherits automatically from LISP the facility of dynamic loading of modules, of incremental compilation and dynamic function redefinition. Even the kernel of REDUCE is open for local modification. Obviously this is a dangerous feature where system integrity is concerned, but, on the other hand, an innovative user finds a rich testbed here.

Appendix A  REDUCE Packages

State: late 1993.

• ALGINT integration for functions involving roots (James H. Davenport)
  
  
• ARNUM algebraic numbers (Eberhard Schrüfer)
  
  
• ASSIST useful utilities for various applications (Hubert Caprasse)
  
  
• AVECTOR vector algebra (David Harper)
  
  
• CALI computational commutative algebra (Hans-Gert Graebe)
  
  
• CAMAL calculations in celestial mechanics (John Fitch)
  
  
• CHANGEVAR transformation of variables in differential equations (G. Üçoluk)
  
  
• COMPACT condensing of expressions with polynomial side relations (Anthony C. Hearn)
  
  
• CRACK solving overdetermined systems of PDEs? or ODEs? (Andreas Brand, Thomas Wolf)
  
  
• CVIT Dirac gamma matrices (V.Ilyin, A.Kryukov, A.Rodionov, A.Taranov)
  
  
• DESIR differential equations and singularities (C. Dicrescenzo, F. Richard-Jung, E. Tournier)
  
  
• EXCALC calculus for differential geometry (Eberhard Schrüfer)
  
  
• FIDE code generation for finite difference schemes (Richard Liska)
  
  
• GENTRAN code generation in FORTRAN, RATFOR, C (Barbara Gates)
  
  
• GNUPLOT display of functions and surfaces (Herbert Melenk)
  
  
• GROEBNER computation in multivariate polynomial ideals (Herbert Melenk, H.Michael Möller, Winfried Neun)
  
  
• HEPHYS high energy physics (Anthony C. Hearn)
  
  
• IDEALS arithmetic for polynomial ideals (Herbert Melenk)
  
  
• INVSYS involutive polynomial systems (Alexey Zharkov)
  
  
• LAPLACE Laplace and inverse Laplace transform (C. Kazasov et al.)
  
  
• LIE functions for the classification of real n-dimensional Lie algebras (Carsten, Franziska Schöbel)
  
  
• LIMITS finding limits (Stanley L. Kameny)
  
  
• LININEQ linear inequalities and linear programming (Herbert Melenk)
  
  
• NUMERIC solving numerical problems using rounded mode (Herbert Melenk)
  
  
• ODESOLVE ordinary differential equations (Malcolm MacCallum? et al.)
  
  
• ORTHOVEC calculus for scalar and vector quantities (J.W. Eastwood)
  
  
• PHYSOP additional support for non-commuting quantities (Mathias Warns)
  
  
• PM general algebraic pattern matcher (Kevin McIsaac?)
  
  
• REACTEQN manipulation of chemical reaction systems (Herbert Melenk)
  
  
• RLFI, TRI TeX? and LaTeX? output (Richard Liska, Ladislav Drska, Werner Antweiler)
  
  
• ROOTS roots of polynomials (Stanley L. Kameny)
  
  
• SCOPE optimization of numerical programs (J. A. van Hulzen)
  
  
• SPDE symmetry analysis for partial differential equations (Fritz Schwarz)
  
  
• SPECFN special functions (Chris Cannam et al.)
  
  
• SPECFN2 special special functions (Victor Adamchik, Winfried Neun)
  
  
• SUM sum and product of series (Fuji Kako)
  
  
• SYMMETRY symmetry-adapted bases and block diagonal forms of symmetric matrices (Karin Gatermann)
  
  
• TAYLOR multivariate Taylor series (Rainer Schöpf)
  
  
• TPS univariate Taylor series with indefinite order (Alan Barnes, Julian Padget)
  
  
• WU Wu algorithm for polynomial systems (Russell Bradford)

Appendix B  Examples

References

[2]

F. Brackx, D. Constales: Computer Algebra with LISP and REDUCE, Kluwer, 1991

[4]

J.H. Davenport, Y. Siret, E. Tournier: Computer Algebra, second printing, Academic Press, London, 1989

[6]

Anthony C. Hearn: REDUCE User's Manual, Version 3.6, The Rand Corporation, Santa Monica (CA), 1995

[8]

F. W. Hehl, V. Winkelmann, H. Meyer: REDUCE, ein Kompaktkurs über die Anwendung von Computer-Algebra, (in German), Springer 1993

[10]

Malcolm MacCallum, Francis Wright: Algebraic Computing with REDUCE, Oxford University Press, 1991

[12]

Norman MacDonald: REDUCE for physicists, Institute of Physics Publishing, Bristol, UK, 1994

[14]

Gerhard Rayna, REDUCE, Software for Algebraic Computation, Springer, New York, 1987

[16]

D.Stauffer, F.W.Hehl, N.Ito, V.Winkelmann, J.G.Zabolitzky: Computer Simulation and Computer Algebra, Lectures for Beginners, third enlarged edition, Springer 1993

[17]

.-H. Steeb. D. Lewien: Algorithms and Computation with REDUCE, BI Wissenschaftsverlag, 1992

[19]

J. Ueberberg: Einführung in die Computeralgebra mit REDUCE(in German), BI Wissenschaftsverlag, 1992

[21]

REDUCE Network Library, Bibliography, reduce-library@rand.org, permanently updated

Konrad-Zuse-Zentrum fuer Informationstechnik
 - Symbolik
Heilbronner Str 10
D 10711 Berlin Wilmersdorf
Germany

This document was translated from L^AT_EX by H^EV^EA.

1: int(sin x,x);