Reduce

Einleitung

Die erste Version von REDUCE wurde Ende der sechziger von Anthony C. Hearn entwickelt und publiziert. Ausgangspunkt waren damals die formalen Rechnungen in der Hochenergiephysik (Feynman-Graphen, Wirkungsquerschnitte etc.), die von Hand nur schwer und zeitraubend fehlerfrei durchführbar sind. Obwohl das heutige REDUCE vom Leistungsumfang her mit den damaligen Ansätzen überhaupt nicht mehr vergleichbar ist, stimmt doch die Ausrichtung auf schwierige mathematisch-formale Rechnungen im Bereich der angewandten Mathematik (Natur- und Ingenieurwissenschaften) noch überein, wenn auch mit einem erheblich erweiterten Spektrum.

Heute läuft REDUCE auf einer Vielzahl von Rechnerplattformen, vom DOS Personal Computer bis hinauf zum Cray Supercomputer.

Trotz seines für ein Programmsystem hohen Alters wird REDUCE in einem kontinuierlichen Prozeß ständig weiterentwickelt und erneuert. Mitte 1992 wurde REDUCE in der Version 3.4.1 freigegeben. Information über die verfügbaren Implementierungen erhält man über e-mail, indem man die Botschaft send info-package from info an redlib@elib.zib.berlin.de oder reduce-netlib@rand.org schickt. An diesen Stellen erhält man auch Information über die zahlreichen verfügbaren Anwenderpakete von REDUCE.

Problemlösung

REDUCE ist primär ausgerichtet auf die Lösung mathematischer Probleme im Bereich technisch-wissenschaftlicher Anwendungen, und zwar insbesondere auf größere Probleme mit sehr umfangreichen oder schwierigen formalen Rechnungen. Dementsprechend finden sich zwar in REDUCE durchaus Operatoren, die eine Aufgabe unmittelbar und vollständig lösen, wenn z.B. kleinere Gleichungssysteme zu lösen oder Determinanten (mit numerischen und/oder symbolischen) Elementen zu berechnen sind. Typischer ist jedoch, daß erst eine Kombination von Einzelschritten eine gewünschte Antwort ergibt und deshalb wird bei der Entwicklung von REDUCE vor allem Wert auf die Bereitstellung leistungsfähiger und modularer Operatoren gelegt, die wie Bausteine zum Zusammenstellen einer Problemlösung genutzt werden.

In Einzelfällen kann es sogar erforderlich sein, einen vollständig neuen symbolischen Kalkül einzurichten. REDUCE bietet dafür einen reichen Satz von Schnittstellen auf mehreren Ebenen an, und die Bibliothek enthält zahlreiche Vorbilder.

Datentypen, Strukturen

Elementare Ausdrücke

Das zentrale Objekt in REDUCE ist der formale Ausdruck, der nach den üblichen mathematischen Regeln aufgebaut ist aus

* Zahlen (ganz, rational, gerundet, reell oder komplex),

* Symbolen (Namen, evtl. indiziert),

* Funktionsausdrücken,

* Operationssymbolen +, -, *, /, **,

* Klammern für die Steuerung der Präzedenz.

Ein Symbol kann hierbei die Rolle eines Stellvertreters für einen unbestimmten Wert übernehmen (formale Variable), ihm kann aber auch ein Ausdruck als Wert zugewiesen werden. Im zweiten Falle wird sein Wert immer dann eingesetzt, wenn das Symbol in einem Ausdruck zitiert wird.

Beispiele für elementare Ausdrücke:

 
  3.1415928                           % Bruch
  a                                   % einfache Variable
  (x+y)**2  /  2                      % quadratischer Ausdruck
  log(u)+log(v)                       % Funktionen

Aggregate

Daneben gibt es die Datenstrukturen, die Aggregate von formalen Ausdrücken darstellen:

* Ein Liste ist eine lineare Anordnung von Ausdrücken wie \{2,3,5,7,11,13,17,19\}.

* Ein Array ist eine "rechteckige" mehrdimensionale indizierte Struktur.

* Eine Matrix ist eine Struktur aus Zeilen und Spalten.

Zwischen Matrizen passender Dimension bzw. zwischen Matrizen und Skalaren sind arithmetische Operationen entsprechend den Regeln der linearen Algebra definiert. Daneben können Elemente einer Matrix einzeln wie Arrayelemente angesprochen werden.

Programmierparadigmen

Für die Formulierung von symbolischen Auswertungen und Algorithmen bietet REDUCE verschiedene Paradigmen an.

Algebraischer Tischrechner

Der einfachste Zugang ist, REDUCE wie einen Tischrechner für symbolische oder numerische Formeln zu benutzen. Formeln können miteinander verknüpft, für die spätere Weiterverwendung benannt und mit einer Reihe leistungsfähiger Operatoren wie z.B. Differentiation, Integration, polynomialer GGT, Faktorisierung und vieles mehr, bearbeitet werden. Jede unmittelbar eingegebene Formel wird sofort bearbeitet mit dem Ziel, die bestmögliche Vereinfachung zu finden, und das Resultat wird ausgegeben, sobald es verfügbar ist.

Beispiel: Taylorpolynom für x * sin(x)

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

      $- \frac{1}{6} * X^4 + X^2$

Imperative algebraische Programmierung

Die einzelne Formelauswertung mit sofortiger Resultatausgabe ist nur ein Spezialfall für eine Anweisung aus der REDUCE Programmiersprache. Diese gestattet die Formulierung komplexer Auswertungsaufträge wie bedingte Anweisungen, Anweisungsgruppen, Blöcke, iterative Schleifen (über eine Zählvariable oder über die Elemente einer Liste), bis hin zur Definition von parametrisierten Prozeduren mit lokalen Variablen.

Beispiel: Rekursives Programm für das Erstellen einer Basis aus Legendre-Polynomen nach der Rekursionsformel

 
P_{n+1}(x) = ((2n + 1)xP_n (x) - nP-{n-1}(x)) / (n + 1)
Der infixe Operator "." fügt ein neues Element vorn an eine Liste an.
 
procedure Legendre_basis(m,x) ;
      % Start mit Basis der Ordnung 1
      Legendre_basis_aux(m,x,1,{x,1}) ;

procedure Legendre_basis_aux(m,x,n,ls) ;
      % ls enthält Polynome n, n-1, n-2 $\ldots$

if  n>=m then  ls                   % fertig
else Legendre_basis_aux(m,x,n+1,
(((2n+1)*x*first  ls - n*second  ls) / (n+1))
            .  ls) ;
Ein Aufruf dieser Prozedur:
 
Legendre_basis(3,z) ;

\{ \frac{5}{2} *Z^3 - \frac{3}{2} *Z, \frac{3}{2} *Z^2 - \frac{1}{2}, Z, 1\}

Regelorientierte Programmierung

Globale algebraische Zusammenhänge können in REDUCE mit Hilfe von Regeln deklariert werden. Eine Regel beschreibt, daß formale (Teil)Ausdrücke eines bestimmten Musters durch andere Ausdrücke rekursiv zu ersetzen sind, evtl. unter Berücksichtigung gewisser Einschränkungen. Derartige Regeln lassen sich sowohl global aktivieren, als auch lokal explizit auf ganz bestimmte Auswertungsschritte beschränken.

Es können auch ganze Kalküle auf diese Weise definiert werden, wobei die Regelform der üblichen mathematischen Notation (Fallunterscheidung) recht nahe kommt.

Beispiel: Definition von Hermite-Polynomen basierend auf einer Rekursionsformel:

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

let Hermite_rules;
Erzeugen eines Hermite-Polynoms:
 
Hermite(4,z) ;

16*Z^4  - 48*Z^2  +  12

Symbolische imperative Programmierung

Die bisher beschriebenen Programmiermodi beziehen sich auf eine rein algebraische Interpretation der Daten; dies erlaub eine anwendungsnahe Formulierung mathematischer Zusammenhänge (Regeln) und Auswertungsschritten (Prozeduren). Die Formeln werden für jeden Schritt einzeln intern in die für die Auswertung benötigte Form konvertiert. Bei umfangreichen und zeitaufwendigen Algorithmen kann es zur Einsparung von Rechenzeit sinnvoll sein, die Hin- und Rückkonvertierung der Zwischenergebnisse zu umgehen und direkt auf die internen Routinen von REDUCE zuzugreifen.

Algebraische Auswertung

Die Auswertung von Ausdrücken stellt das Herzstück von REDUCE dar und kann wegen der großen Komplexität hier nur angedeutet werden. Von zentraler Bedeutung bei der maschinellen Bearbeitung von mathematischen Formeln generell ist das Problem der Entscheidbarkeit der Identität zweier Formeln, z.B. die Entscheidung a + b = b + a unter der Annahme einer kommutativen Addition.

Es ist wohlbekannt, daß dieses Problem äquivalent ist mit dem Problem der Erkennung der Null bzw. mit der Existenz eines endlichen Algorithmus für die überführung einer beliebigen Formel in eine äquivalente kanonische Form. Eine universelle kanonische Form gibt es nicht; nur für Teilbereiche wie z.B. Polynome, rationale Funktionen, Ideale sind kanonische Formen bekannt. REDUCE baut deshalb auf einer kanonischen Form für rationale Funktionen (Quotienten von multivariaten Polynomen) auf, bei denen als Variablen (REDUCE: Kerne) sowohl einfache Symbole wie auch Funktionsausdrücke mit beliebig komplexer Parameterstruktur auftreten dürfen. REDUCE versucht, mit geeigneten Regeln möglichst viele der Funktionen in den Bereich der systematischen kanonischen Form einzubeziehen. Für Funktionen, die sich dem generellen algorithmischen Zugriff entziehen (z.B. Wurzeln), wird versucht, mit Hilfe heuristischer Regeln ein akzeptables Verhalten zu erreichen.

Näherungen

Beim Umgang mit symbolischen Ausdrücken wird meist exaktes Rechnen verlangt, insbesondere wenn Algorithmen aus dem Bereich der klassischen Algebra zum Einsatz kommen. Hierfür bietet REDUCE als Zahlbereiche ganze Zahlen beliebiger Länge und - darauf aufbauend - rationale Zahlen, modulare Zahlen (Rechnen im endlichen Restklassenkörper), auf Wunsch um die imaginäre Einheit i zu komplexen Zahlen erweitert.

Mit diesen Zahlen kann beliebig gerechnet werden. Jedoch ist der Auswertung von transzendenten Funktionen dadurch eine Grenze gesetzt, daß ihr Resultat mit Hilfe des aktiven Zahlbereiches (erweitert um Symbole wie \pi, e) exakt dargestellt werden kann.

Rechnerunterstütztes symbolisches Rechnen kann aber auch außerhalb der klassischen Algebra, etwa im Zusammenhang mit Näherungsverfahren der Analysis oder für klassische numerische Mathematik mit Gewinn eingesetzt werden.

Potenzreihen

Für die Ermittlung formaler Näherungen bietet REDUCE Potenzreihen an, und zwar wahlweise abgebrochene Taylorreihen in mehreren Veränderlichen oder, im Falle einer Veränderlichen, Taylorreihen mit variabler Anzahl von Termen. Potenzreihen können einerseits als abstrakte algebraische Objekte aufgefaßt werden, andererseits auch als Näherungen gesuchter Funktionen, z.B. im Kontext von Differentialgleichungen.

Gerundete Zahlen

Auch Gleitkommazahlen sind in REDUCE enthalten, jedoch sind sie gegenüber den üblichen in Hardware realisierten Gleitkommazahlen in zweifacher Hinsicht erweitert:

* die Mantissenlänge ist in beliebiger Größe frei wählbar,

* es gibt keine obere Grenze für den Betrag einer Zahl, d.h. der Exponent ist nicht beschränkt.

Technisch wird dies erreicht, indem die hardwaremäßig angebotenen Gleitkommazahlen in parametrisierte Software eingebettet werden.

Schnittstelle zu externen numerischen Programmen

Einen wichtigen Einsatzbereich der Formelmanipulation bilden die gemischt symbolisch-numerischen Verfahren, wenn z.B. der symbolische Teil formale Eigenschaften einer Aufgabe zur Vorbereitung und Konditionierung eines numerischen Algorithmus umsetzt. Beispiele sind etwa die automatische Herstellung von Jacobi-Matrizen für ODE-Solver oder die Reduktion der Ordnung eines Systems aufgrund formaler Symmetrien. Für die Zusammenarbeit von symbolischen und numerischen Komponenten eines Verfahrens bietet REDUCE hier die Erzeugung kompletter Programme in den Programmiersprachen FORTRAN, PASCAL oder C an.

Ein/Ausgabe

Normalerweise gibt REDUCE Resultate im interaktiven Betrieb auf dem Bildschirm in einer zweidimensionalen Form aus, wobei z.B. Exponenten nach oben gerückt sind und Quotienten wenn möglich mit einem langen Bruchstrich dargestellt werden. Neben dieser an der üblichen mathematischen Notation orientierten Ausgabeform bietet REDUCE weitere spezielle Ausgabeformen an:

* lineare Ausgabeform: die Daten sind zur späteren Wiedergabe in REDUCE oder ein anderes System geeignet,

* Fremdsyntax: die Ausdrücke werden in der Syntax von FORTRAN, C oder einer anderen Programmiersprache ausgegeben zur Einfügung in numerische Codes,

* LaTeX: direkte Aufbereitung der Formeln für die Verwendung in Publikationen.

Beispiele für q:= (x + y)^3:

 
Q := X^3 + 3*X^2 *Y + 3*X*Y^2 + Y^3

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

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

\begin{displaymath}
q=x^\{3\}+3 x^\{2\} y+3 x y^\{2\}+y^\{3\}
\end{displaymath}
Ein- und Ausgabe können auch in Files umgelenkt werden.

Offenes System

Ein Merkmal, das REDUCE von den meisten am Markt erhältlichen Systemen unterscheidet, ist seine durch eine langjährige Tradition untermauerte Offenheit:

* REDUCE ist in einer Sprache RLISP geschrieben, welche die Funktionalität von LISP in einer anwenderfreundlichen Syntax anbietet.

* REDUCE wird traditionell mit allen Quellen (auch für den Umsetzer RLISP nach LISP) ausgeliefert.

* REDUCE ist offen gegenüber anwenderseitigen Erweiterungen, die entweder auf dem algebraischen Niveau anwendernah oder auf dem symbolischen (=LISP) Niveau systemnah vorgenommen werden können.

* Da REDUCE von LISP automatisch die Fähigkeiten zum dynamischen Laden von Programmen, zum inkrementellen Kompilieren und zum Redefinieren von Programmen erbt, ist sogar der Kern von REDUCE gegenüber lokalen änderungen offen.

Die Offenheit von REDUCE hat dazu geführt, daß in den letzten Jahren eine erhebliche Anzahl von Moduln in den verschiedensten Anwendungsbereichen von Anwendern entwickelt wurden, die den Einsatzbereich von REDUCE erheblich erweitern. Diese Pakete sind in einer Bibliothek über Netzzugang abrufbar, siehe [4].

Literatur

 
[ 1]  F. Brackx and D. Constales. Computer Algebra with Lisp and REDUCE, volume 72 
      of Mathematics and Its Applications. Kluwer Academic Publishers, Dordrecht,
      Boston, London, 1991

[ 2]  J.H. Davenport, Y. Siret, and E. Tournier. Computer Algebra: Systems and
      Algorithms for Algebraic Computation. Academic Press, London, 1989

[3]   A.C. Hearn. REDUCE Users Manual, Version 3.4. The Rand Corporation, 
      Santa Monica (CA), 1991

[ 4]  F.W. Hehl, V. Winkelmann, and H. Meyer. Computer-Algebra. Ein Kompaktkurs
      über die Anwendung von REDUCE. Springer-Verlag, Berlin-Heidelberg-New York, 1992

[ 5]  M.A.H. MacCallum and F.J. Wright. Algebraic Computing with REDUCE, volume 1 
      of Lecture Notes from the First Brasilian School on Computer Algebra. 
      Clarendon Press, Oxford, 1991

[ 6]  G. Rayna. Reduce, Software for Algebraic Computation. Springer-Verlag, 
      Berlin-Heidelberg-New York, 1987

[ 7]  D. Stauffer, F.W. Hehl, V. Winkelmann, and J.G. Zabolitzky. 
      Computer Simulation and Computer Algebra - Lectures for Beginners. 
      Springer-Verlag, Berlin-Heidelberg-New York, 1988

[ 8]  W.-H. Steeb and D. Lewien. Algorithms and Computation with Reduce.
      Bibliographisches Institut, Mannheim

[ 9]  J. Ueberberg. Einführung in die Computeralgebra mit Reduce, für 
      Mathematiker, Informatiker und Physiker. Bibliographisches Institut, 
      Mannheim, 1992

[10]  REDUCE network library, bibliography. reduce-library@rand.org, wird 
      laufend ergänzt. 

Author der Beschreibung Herbert Melenk (Berlin)