REDUCE: OverviewIntroductionThe 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 You can use REDUCE on this website by writing:\begin{reduce} REDUCE commands \end{reduce}in comments or by first login and then edit. The results of the computation will be displayed when you click Preview or Save. New version of reduce was installed on 17 Sep 2023. It is built using csl from Reduce-svn6547-src.tar.gz at http://reduce-algebra.sourceforge.net 1 Problem solvingThe 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, Structures2.1 Elementary ExpressionsThe central object of REDUCE is the formal expression, which is built with respect to the common mathematical rules. Elementary items are
Examples of elementary expressions: 3.1415928 % fraction a % simple variable (x+y)**2 / 2 % quadratic expression log(u)+log(v) % function 2.2 AggregatesThere are data structures that collect a number of formal expressions:
3 Programming ParadigmsFor specifying symbolic tasks and algorithms REDUCE offers a set of different programming paradigms:3.1 Algebraic Desk CalculatorUsing 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); 1 4 2 - ---*X + X 6 3.2 Imperative Algebraic ProgrammingEvaluation 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(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 3 2 1 ---*Z - ---, 2 2 Z, 1} 3.3 Rule Oriented ProgrammingIn 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); 4 2 16Z - 48Z + 12 3.4 Symbolic Imperative ProgrammingThe 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 EvaluationThe 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:
5 ApproximationsIn 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 SeriesPower 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 NumbersFor 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:
5.3 Interface for Numerical ProgramsA 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/OIn 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:
natural (default) output: 3 2 2 3 Q := X + 3X Y + 3XY + Yfor later re--use: 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: 7 Open SystemIn contrast to most other symbolic math systems, REDUCE traditionally is completely open:
Appendix A REDUCE PackagesState: late 1993.
Appendix B ExamplesReferences
Konrad-Zuse-Zentrum fuer Informationstechnik - Symbolik Heilbronner Str 10 D 10711 Berlin Wilmersdorf Germany This document was translated from LATEX by HEVEA. ... --achearn, Fri, 13 Feb 2009 11:55:42 -0800 reply
|