changed:
-
<H1 ALIGN=center>REDUCE: Overview</H1>


<!--TOC section Introduction-->

<H2>Introduction</H2><!--SEC END -->

The first version of REDUCE was developed and published by
Anthony C. Hearn about 25 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.<BR>
<BR>
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.<BR>
<BR>
Today REDUCE can be used on a variety of hardware platforms from
personal computers up to advanced workstations and servers.<BR>
<BR>
Although REDUCE is a mature program system, it is extended and updated on
a regular basis.  Access is provided on the REDUCE web server,
http://reduce-algebra.com , as new packages and improvements become available.<BR>
<BR>
In April 2004, version 3.8 of REDUCE was released.  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.<BR>
<BR>
Some examples of Reduce programs are given here in <b>Appendix B</B> ReduceAppendixB.
<BR>
<!--TOC section Problem solving-->

<H2><A NAME="htoc1">1</A>&nbsp;&nbsp;Problem solving</H2><!--SEC END -->

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.<BR>
<BR>
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.
<!--TOC section Data Types, Structures-->

<H2><A NAME="htoc2">2</A>&nbsp;&nbsp;Data Types, Structures</H2><!--SEC END -->

<!--TOC subsection Elementary Expressions-->

<H3><A NAME="htoc3">2.1</A>&nbsp;&nbsp;Elementary Expressions</H3><!--SEC END -->

The central object of REDUCE is the formal expression, which is
built with respect to the common mathematical rules. Elementary items are
<UL><LI>
numbers (integers, rationals, rounded fractionals, real or
complex); the domain can be selected dynamically,
<LI>symbols (names with or without indices)
<LI>functional expressions (names followed by a parameter list)
<LI>operator symbols <B>+,-,*,/,**</B>
<LI>parentheses for precedence control.
</UL>
A symbol here can play the role of an unknown in the mathematical sense,
as well as a placeholder for a value. An expression can be assigned to a
symbol as a value such that later all references to the symbol are
replaced by the assigned value.<BR>
<BR>
Examples of elementary expressions:
<PRE>
    3.1415928      % fraction
    a              % simple variable
    (x+y)**2 / 2   % quadratic expression
    log(u)+log(v)  % function
</PRE>
<!--TOC subsection Aggregates-->

<H3><A NAME="htoc4">2.2</A>&nbsp;&nbsp;Aggregates</H3><!--SEC END -->

There are data structures that collect a number of formal expressions:
<UL><LI>
An <TT>equation</TT> is an object where the operator <B>=</B> takes
highest precedence, with two slots for expressions, the <B>lhs</B> and
<B>rhs</B>:
<PRE>
     p=u**2
</PRE><BR>
<BR>
<LI>A <TT>list</TT> 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:
<PRE>
    {2,3,5,7,11,13,17,19} 
</PRE><BR>
<BR>
<LI>An <TT>array</TT> is a rectangular multidimensional structure; the
elements are identified by integer indices. Elements always have a value,
which defaults to zero.
<PRE>
 array primes(10);
 primes(0):=2;
 for i:=1: 10 do
  primes(i):=nextprime(primes(i-1));
</PRE><BR>
<BR>
<LI>A <TT>matrix</TT> 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 <B>df</B> to construct
a Jacobian
<PRE>
   matrix jac(n,n);
   for i:=1:n do for j:=1:n do
    jac(i,j):=df(f(i),x(j));
</PRE></UL>
<!--TOC section Programming Paradigms-->

<H2><A NAME="htoc5">3</A>&nbsp;&nbsp;Programming Paradigms</H2><!--SEC END -->

For specifying symbolic tasks and algorithms REDUCE offers a set
of different programming paradigms:<BR>
<BR>
<!--TOC subsection Algebraic Desk Calculator-->

<H3><A NAME="htoc6">3.1</A>&nbsp;&nbsp;Algebraic Desk Calculator</H3><!--SEC END -->

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.<BR>
<BR>
Example: Taylor polynomial for <B>x*sin(x)</B>
<PRE>
for i:=0:5 sum 
  sub(x=0,df(x*sin(x),x,i)) * x**i 
            / factorial(i);

    1   4    2
 - ---*X  + X
    6
</PRE>
 
<!--TOC subsection Imperative Algebraic Programming-->

<H3><A NAME="htoc7">3.2</A>&nbsp;&nbsp;Imperative Algebraic Programming</H3><!--SEC END -->

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.<BR>
<BR>
Example: definition of a procedure for expanding a function to a Taylor
polynomial:
<PRE>
procedure tay(u,x,n);
  begin scalar ser,fac;  
    ser:=sub(x=0,u);fac:=1; 
    for i:=1:n do 
    &lt;&lt;u:=df(u,x); fac:=fac*i;   
      ser:=ser+sub(x=0,u)*x**i/fac &gt;&gt;;
    return(ser);  
  end;
</PRE>
A call to this procedure:
<PRE>
tay(x*sin(x),x,5);
</PRE>yields
<PRE>
    1   4    2
 - ---*X  + X
    6
</PRE>
Example: a recursive program for collecting a basis of Legendre
polynomials from the recurrence relation:
<PRE>
    P{n+1,x) = ((2n+1)*x*P(n,x) - n*P(n-1,x))/(n+1)
</PRE>
The infix operator "." adds a new element to the head of a list.
<PRE>
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&gt;=m then ls     % done
  else Legendre_basis_aux(m,x,n+1,
  (((2n+1)*x*first ls - n*second ls)/(n+1))
       . ls);
</PRE>
A call to this procedure
<PRE>
Legendre_basis(3,z);
</PRE>yields
<PRE>
  5   3    3
{---*Z  - ---*Z,
  2        2

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

 Z, 1}
</PRE>
<!--TOC subsection Rule Oriented Programming-->

<H3><A NAME="htoc8">3.3</A>&nbsp;&nbsp;Rule Oriented Programming</H3><!--SEC END -->

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.<BR>
<BR>
Example: Expanding trigonometric functions for combined arguments; the
tilde symbol represents an implicit for--all.
<PRE>
Sin_Cos_rules:=
{sin(~x+~y)=&gt;sin(x)*cos(y) + cos(x)*sin(y),
 cos(~x+~y)=&gt;cos(x)*cos(y) - sin(x)*sin(y)};
</PRE>
Global activation is achieved by
<PRE>
let Sin_Cos_rules;
</PRE>Note: REDUCE has no predefined "knowledge" about these
relations for trigonometric functions, as they can be used as production
rules in either form depending on whether expansion or collection is
required; only the user can define which mode is adequate for his problem.<BR>
<BR>
Using rules, a complete calculus can be implemented; the rule syntax here
is very close to the mathematical notation for multistep cases.<BR>
<BR>
Example: Definition of Hermite polynomials:
<PRE>
operator Hermite;
Hermite_rules:=
{Hermite(0,~x) =&gt; 1,
 Hermite(1,~x) =&gt; 2*x,
 Hermite(~n,~x) =&gt; 2*x*Hermite(n-1,x)
          -2*(n-1)*Hermite(n-2,x)
              when n&gt;1};

let Hermite_rules;
</PRE>
Generation of a Hermite polynomial:
<PRE>
Hermite(4,z);

    4       2
16*Z  - 48*Z  + 12
</PRE>
<!--TOC subsection Symbolic Imperative Programming-->

<H3><A NAME="htoc9">3.4</A>&nbsp;&nbsp;Symbolic Imperative Programming</H3><!--SEC END -->

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.<BR>
<BR>
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.<BR>
<BR>
<!--TOC section Algebraic Evaluation-->

<H2><A NAME="htoc10">4</A>&nbsp;&nbsp;Algebraic Evaluation</H2><!--SEC END -->

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
 <B>a + b = b + a </B>
under the assumption of commutative addition.<BR>
<BR>
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.<BR>
<BR>
A coarse sketch of evaluation is as follows:
<UL><LI>
a symbol with an assigned value is
replaced by the value,
<LI>a call for a known procedure is
replaced by the value produced by the procedure invocation,
<LI>matching rules are applied,
<LI>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,
<LI>a rational function is converted into a form with common
denominator (i.e., a quotient of two polynomials).
</UL>
This is, of course, a highly recursive process, which is applied until no
more transformations are possible.
<!--TOC section Approximations-->

<H2><A NAME="htoc11">5</A>&nbsp;&nbsp;Approximations</H2><!--SEC END -->

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.<BR>
<BR>
The values of transcendental functions with general numeric arguments do
not fall into these domains, even if symbols like <B>pi</B>, <B>e</B>, <B>i</B>
are attached. Nevertheless symbolic computation can be used for fields beyond
classical algebra, for example in the domain of analytic approximations in
numerical mathematics.<BR>
<BR>
<!--TOC subsection Power Series-->

<H3><A NAME="htoc12">5.1</A>&nbsp;&nbsp;Power Series</H3><!--SEC END -->

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.<BR>
<BR>
<!--TOC subsection Rounded Numbers-->

<H3><A NAME="htoc13">5.2</A>&nbsp;&nbsp;Rounded Numbers</H3><!--SEC END -->

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:
<UL><LI>
the mantissa length can be selected
arbitrarily (i.e., selected as a number of decimal digits),
<LI>there is no limit for the exponent and so no
upper or lower limit for the magnitude of a number.
</UL>
Technically, this arithmetic is implemented by an embedding of the
standard (hardware) floating point operations in a software package, which
tries to execute as much as possible in fast hardware and which converts
to software emulation as soon as the hardware limits are passed. Based on
this number domain, attractive algorithms can be implemented, which start
with coarse approximations and then refine the overall precision in an
adaptive style when approaching the desired solution.<BR>
<BR>
<!--TOC subsection Interface for Numerical Programs-->

<H3><A NAME="htoc14">5.3</A>&nbsp;&nbsp;Interface for Numerical Programs</H3><!--SEC END -->

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.
<!--TOC section I/O-->

<H2><A NAME="htoc15">6</A>&nbsp;&nbsp;I/O</H2><!--SEC END -->

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.<BR>
<BR>
For special purposes, additional output forms are available:
<UL><LI>
linear form: the data can be re-used for later
input in REDUCE or another system,
<LI>foreign syntax: the expressions are printed in
the syntax of FORTRAN, C or another programming language
for the direct insertion in numeric codes,
<LI>TeX: indirect formatting as input for the TeX
layout program to be inserted into a publication.
</UL>
Examples for <B>q:=(x+y)**3</B>:<BR>
<BR>
natural (default) output:
<PRE>
      3      2          2    3
Q := X  + 3*X *Y + 3*X*Y  + Y
</PRE>for later re--use:
<PRE>
Q := X**3 + 3*X**2*Y + 3*X*Y**2 + Y**3$
</PRE>as contribution to a FORTRAN source:
<PRE>
      Q=X**3+3.*X**2*Y+3.*X*Y**2+Y**3
</PRE>for a LaTeX document:
<PRE>
\begin{displaymath}
q=x^{3}+3 x^{2} y+3 x y^{2}+y^{3}
\end{displaymath}
</PRE>In addition to direct terminal access, I/O can also be redirected to
files.
<!--TOC section Open System-->

<H2><A NAME="htoc16">7</A>&nbsp;&nbsp;Open System</H2><!--SEC END -->

In contrast to most other symbolic math systems, REDUCE
traditionally is completely open:
<UL><LI>
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.<BR>
<BR>
<LI>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.<BR>
<BR>
<LI>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.<BR>
<BR>
<LI>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.
</UL>
One effect of the liberality of REDUCE is the large number of
application packages written by users. Many of these packages now are now
included in REDUCE or in the REDUCE Network Library.

<BR>
<BR>
<!--TOC section REDUCE Packages-->

<H2><A NAME="htoc17">Appendix A</A>&nbsp;&nbsp;REDUCE Packages</H2><!--SEC END -->

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

<H2><A NAME="htoc18">Appendix B</A>&nbsp;&nbsp;Examples</H2><!--SEC END -->
<p><center><b>
Go to ReduceAppendixB
</b></center></p>

<!--TOC section References-->

<H2>References</H2><!--SEC END -->
<DL COMPACT=compact><DT><A NAME="1"><FONT COLOR=purple>[2]</FONT></A><DD>F. Brackx, D. Constales: Computer Algebra with
LISP and REDUCE, Kluwer, 1991<BR>
<BR>
<DT><A NAME="3"><FONT COLOR=purple>[4]</FONT></A><DD>J.H. Davenport, Y. Siret, E. Tournier: Computer Algebra,
second printing, Academic Press, London, 1989<BR>
<BR>
<DT><A NAME="5"><FONT COLOR=purple>[6]</FONT></A><DD>Anthony C. Hearn: REDUCE User's Manual, Version 3.6,
The Rand Corporation, Santa Monica (CA), 1995<BR>
<BR>
<DT><A NAME="7"><FONT COLOR=purple>[8]</FONT></A><DD>F. W. Hehl, V. Winkelmann, H. Meyer:
REDUCE, ein Kompaktkurs über die Anwendung von Computer-Algebra,
(in German), Springer 1993 <BR>
<BR>
<DT><A NAME="9"><FONT COLOR=purple>[10]</FONT></A><DD>Malcolm MacCallum, Francis Wright:
Algebraic Computing with REDUCE,
Oxford University Press, 1991<BR>
<BR>
<DT><A NAME="11"><FONT COLOR=purple>[12]</FONT></A><DD>Norman MacDonald: REDUCE for physicists,
Institute of Physics Publishing, Bristol, UK, 1994<BR>
<BR>
<DT><A NAME="13"><FONT COLOR=purple>[14]</FONT></A><DD>Gerhard Rayna, REDUCE, Software for Algebraic Computation,
Springer, New York, 1987<BR>
<BR>
<DT><A NAME="15"><FONT COLOR=purple>[16]</FONT></A><DD>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<BR>
<BR>
<DT><A NAME="W"><FONT COLOR=purple>[17]</FONT></A><DD>.-H. Steeb. D. Lewien: Algorithms and Computation with
REDUCE, BI Wissenschaftsverlag, 1992<BR>
<BR>
<DT><A NAME="18"><FONT COLOR=purple>[19]</FONT></A><DD>J. Ueberberg: Einführung in die Computeralgebra
mit REDUCE(in German), BI Wissenschaftsverlag, 1992<BR>
<BR>
<DT><A NAME="20"><FONT COLOR=purple>[21]</FONT></A><DD>REDUCE Network Library, Bibliography,
reduce-library@rand.org, permanently updated
</DL>
This document was produced by:

<PRE>
Konrad-Zuse-Zentrum fuer Informationstechnik
 - Symbolik
Heilbronner Str 10
D 10711 Berlin Wilmersdorf
Germany
</PRE><!--HTMLFOOT-->
<!--ENDHTML-->
<!--FOOTER-->
<HR SIZE=2>
<BLOCKQUOTE><EM>This document was translated from L<sup>A</sup>T<sub>E</sub>X by
</EM><A HREF="http://pauillac.inria.fr/~maranget/hevea/index.html"><EM>H<FONT SIZE=2><sup>E</sup></FONT>V<FONT SIZE=2><sup>E</sup></FONT>A</EM></A><EM>.
</EM></BLOCKQUOTE>

REDUCE: Overview


Introduction

The first version of REDUCE was developed and published by
Anthony C. Hearn about 25 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.  Access is provided on the REDUCE web server,
http://reduce-algebra.com , as new packages and improvements become available.



In April 2004, version 3.8 of REDUCE was released.  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.



  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.

  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.

A symbol here can play the role of an unknown in the mathematical sense,
as well as a placeholder for a value. An expression can be assigned to a
symbol as a value such that later all references to the symbol are
replaced by the assigned value.



Examples of elementary expressions:
    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));


  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;

A call to this procedure:
tay(x*sin(x),x,5);
yields
    1   4    2
 - ---*X  + X
    6

Example: a recursive program for collecting a basis of Legendre
polynomials from the recurrence relation:
    P{n+1,x) = ((2n+1)xP(n,x) - n*P(n-1,x))/(n+1)

The infix operator "." adds a new element to the head of a list.
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);

A call to this procedure
Legendre_basis(3,z);
yields
  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)};

Global activation is achieved by
let Sin_Cos_rules;
Note: REDUCE has no predefined "knowledge" about these
relations for trigonometric functions, as they can be used as production
rules in either form depending on whether expansion or collection is
required; only the user can define which mode is adequate for his problem.



Using rules, a complete calculus can be implemented; the rule syntax here
is very close to the mathematical notation for multistep cases.



Example: Definition of Hermite polynomials:
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;

Generation of a Hermite polynomial:
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.




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

This is, of course, a highly recursive process, which is applied until no
more transformations are possible.

  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.

Technically, this arithmetic is implemented by an embedding of the
standard (hardware) floating point operations in a software package, which
tries to execute as much as possible in fast hardware and which converts
to software emulation as soon as the hardware limits are passed. Based on
this number domain, attractive algorithms can be implemented, which start
with coarse approximations and then refine the overall precision in an
adaptive style when approaching the desired solution.




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.

  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.

Examples for q:=(x+y)**3:



natural (default) output:
      3      2          2    3
Q := X  + 3X Y + 3XY  + Y
for later re--use:
Q := X*3 + 3X*2Y + 3XY2 + Y3$
as contribution to a FORTRAN source:
      Q=X*3+3.X*2Y+3.XY2+Y3
for a LaTeX? document:
\begin{displaymath}
q=x^{3}+3 x^{2} y+3 x y^{2}+y^{3}
\end{displaymath}
In addition to direct terminal access, I/O can also be redirected to
files.

  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.

One effect of the liberality of REDUCE is the large number of
application packages written by users. Many of these packages now are now
included in REDUCE or in the REDUCE Network Library.






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


Go to ReduceAppendixB?


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

This document was produced by:

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




This document was translated from LATEX by
HEVEA.

! Missing $ inserted.
<inserted text> 
                $
l.60 q=x^
         {3}+3 x^{2} y+3 x y^{2}+y^{3}
?