

last edited 10 years ago by Bill Page 
1 2 3 4 5 6 7 8 9 10 12  
Editor: page
Time: 2007/09/12 00:24:24 GMT7 

Note: 
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://reducealgebra.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> 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> Data Types, Structures</H2><!SEC END > <!TOC subsection Elementary Expressions> <H3><A NAME="htoc3">2.1</A> 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> 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(i1)); </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> 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> 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> 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 <<u:=df(u,x); fac:=fac*i; ser:=ser+sub(x=0,u)*x**i/fac >>; 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(n1,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, n1, n2 ... if n>=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> 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 forall. <PRE> 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)}; </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) => 1, Hermite(1,~x) => 2*x, Hermite(~n,~x) => 2*x*Hermite(n1,x) 2*(n1)*Hermite(n2,x) when n>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> 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> 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> 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 (padic) 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> 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> 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> Interface for Numerical Programs</H3><!SEC END > A field of growing importance for symbolic computation is the use of algorithms of mixed symbolicnumeric 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> 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 reused 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 reuse: <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> 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> 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 (HansGert 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. RichardJung, 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 ndimensional 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 noncommuting 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 symmetryadapted 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> 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 ComputerAlgebra, (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, reducelibrary@rand.org, permanently updated </DL> This document was produced by: <PRE> KonradZuseZentrum 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://reducealgebra.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.
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
3.1415928 % fraction a % simple variable (x+y)**2 / 2 % quadratic expression log(u)+log(v) % function
There are data structures that collect a number of formal expressions:
p=u**2
{2,3,5,7,11,13,17,19}
array primes(10); primes(0):=2; for i:=1: 10 do primes(i):=nextprime(primes(i1));
matrix jac(n,n); for i:=1:n do for j:=1:n do jac(i,j):=df(f(i),x(j));
For specifying symbolic tasks and algorithms REDUCE offers a set
of different programming paradigms:
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
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 6Example: 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(n1,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});A call to this procedureprocedure Legendre_basis_aux(m,x,n,ls); % ls contains polynomials n, n1, n2 ... 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);yields
5 3 3 {Z  Z, 2 2
 2 1 *Z  , 2 2
Z, 1}
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 forall.
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.
operator Hermite; Hermite_rules:= {Hermite(0,~x) => 1, Hermite(1,~x) => 2x, Hermite(~n,~x) => 2xHermite(n1,x) 2(n1)*Hermite(n2,x) when n>1};Generation of a Hermite polynomial:let Hermite_rules;
Hermite(4,z);
 2 16Z  48Z + 12
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.
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:
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 (padic)
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.
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.
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:
A field of growing importance for symbolic computation is the use of algorithms of mixed symbolicnumeric 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.
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:
3 2 2 3 Q := X + 3X Y + 3XY + Yfor later reuse:
Q := X*3 + 3X*2Y + 3XY2 + Y3$as contribution to a FORTRAN source:
Q=X*3+3.X*2Y+3.XY2+Y3for 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.
In contrast to most other symbolic math systems, REDUCE traditionally is completely open:
State: late 1993.
KonradZuseZentrum fuer Informationstechnik  Symbolik Heilbronner Str 10 D 10711 Berlin Wilmersdorf Germany
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.
! Missing $ inserted. <inserted text> $ l.60 q=x^ {3}+3 x^{2} y+3 x y^{2}+y^{3} ?