Literatur zur Vorlesung Computeralgebra

Kapitel 1: Einführung in REDUCE

Die Hauptreferenz ist natürlich das Handbuch [Hea]; es liegt als TEX-Datei vor und kann von Mitgliedern der Universität frei kopiert werden. Als praktische Ergänzung dazu empfehlen sich die on line Lektionen von D. Stoutemayer, die innerhalb von REDUCE mit in less i aufgerufen werden können, wobei i = 1, …, 7.

Als einführendes Buch, das teilweise auch im Handbuch undokumentierte Elemente von REDUCE erläutert, ist vor allem [MW] zu empfehlen; außerdem auch das nicht ganz so weit gehende Buch [Ray], dem noch die Version 3.2 von REDUCE zugrunde liegt, die den Datentyp Liste noch nicht kennt und daher beispielsweise bei SOLVE, FACTORIZE eine andere Form der Ergebnisrückgabe verwendet. Spezieller und weitgehend disjunkt zum Vorlesungsstoff ist das Buch [BC], das vor allem die Funktionen des zugrundeliegenden Standard LISP-Systems beschreibt; es behandelt auch einige Anwendungen von REDUCE auf mathematische Probleme. [HWM] schließlich ist eine elementare Einführung in deutscher Sprache, benutzt aber bereits die neuere Version 3.4, die beispielsweise für LET-Regeln eine erweiterte Syntax hat gegenüber der in der Vorlesung behandelten Version 3.3. Auf den vor kurzem gelieferten HP-Rechnern der Mathematik wird diese Version installiert werden.

Kapitel 2: Grundlegende Algorithmen

Die Algorithmen für Grundrechenarten und ggT mit Zahlen beliebiger Länge oder Polynomen findet man in vielen der besseren Programmierlehrbüchern, etwa in [Kn], §4.3 und §4.4, oder in [AHU], Kapitel 8. In den meisten Lehrbüchern der Computeralgebra sind sie ebenfalls zu finden (wenn auch weniger ausführlich und weniger vollständig als etwa in [Kn]); dort wird auch genauer auf die Darstellung der Daten eingegangen. Standardlehrbücher der Computeralgebra sind etwa [DST] oder [Ak], außerdem der Sammelband [BCL].

Algebraische Grundlagen wie den chinesischen Restesatz und die eindeutige Primzerlegung in Polynomringen endlich vieler Veränderlicher findet man in allen gängigen Lehrbüchern der Algebra; hier sollten Sie die Bücher benutzen, die Sie (hoffentlich) parallel zur Algebra gelesen haben. Modulararithmetiken werden auch in [Kn], §4.3.2 behandelt. [Li], [Mi] und [NQ] sind Bücher, die speziell die algebraischen Grundlagen der Computeralgebra behandeln, von denen jedoch keines über Polynome in einer Veränderlichen hinausgeht.

Montgomerys Trick zur Beschleunigung der modularen Multiplikation wurde veröffentlicht in [Mo], der Unmöglichkeitssatz von Richardson in [Ri]. Die in der Vorlesung skizzierte Verschärfung dieses Satzes benutzt die negative Lösung des zehnten Hilbertschen Problems, die etwa in [DMR] beschrieben wird. (Einige Kopien sind noch übrig von einem früheren Seminar.) Mit diesem Ergebnis und zusammen mit [Ri] ist der Beweis der Verallgemeinerung eine einfache Übungsaufgabe.

Kapitel 3: Modulare Methoden

§1 ggT in ℤ[X]: Die dazu benötigten Schranken findet man beispielsweise in [Mi], Kapitel 4, §§3+4; den Algorithmus und die Aufwandsabschätzung in [DST], §4.1.1. §2 ggT in R[X, Y]: [DST], §4.1.2. §3 Resultanten: Diese werden in den meisten Algebralehrbüchern behandelt. Für die Resultantenberechnung à la Euklid, siehe [DST], A.4. §4 Sonstige Möglichkeiten: [DST], §4.1.3

Kapitel 4: Faktorisierung von Polynomen

§1 Quadratfreie Zerlegung: [Mi], §6.3 §2 Berlekamps Algorithmus: [Mi], §6.4; [Kn], §4.6.2; [Ak], §6.2 §3 Das Henselsche Lemma: Algebralehrbücher, [Mi], Kap. 7; [Ak], §6.3 §4 Faktorisierung von Polynomen mehrerer Veränderlicher: [W], [DST], §4.2.3

Kapitel 5: Standardbasen von Polynomidealen und ihre Anwendungen

§1 Standardbasen §2 Existenz von Standardbasen und der Hilbertsche Nullstellensatz §3 Buchbergers Algorithmus zur Berechnung von Standardbasen §4 Lösung nichtlinearer Gleichungssysteme

Zu §§1–3 siehe vor allem [CLO], Kapitel 2; für das gesamte Kapitel außerdem [DST], §3.1.

Kapitel 6: Semialgebraische Geometrie und Robotik

§1 Polynomgleichungen in ℝ[X]: [Mi], §5.4 und [BR], §§1.1.1+2; außerdem [Ak], Kapitel 7. §2 Semialgebraische Mengen: [BR], §1.5, §§2.1+2, [AB] §3 Anwendungen in der Robotik: [BR], Anhang D; [Can], [AB].

[AB] D.S. Arnon, B. Buchberger: Algorithms in real algebraic geometry, Academic Press, 1988

Dieses Buch ist ein Sonderdruck der Hefte 1 und 2 von Band 5 des Journal of Symbolic Computation und besteht aus dreizehn Originalarbeiten zur algorithmischen algebraischen Geometrie. In mehreren dieser Arbeiten werden Algorithmen vorgestellt, die sowohl die zylindrische Zerlegung als auch deren Anwendungen in der Robotik deutlich schneller liefern als die in der Vorlesung vorgestellte Methode. Ein Algorithmus von Grigor’ev gibt sogar – bei Verzicht auf eine vollständige Lösung – in subexponentieller Zeit ein für viele Anwendungen ausreichendes Bild einer semialgebraischen Menge.

[AHU] Aho/Hopcroft/Ullman: The design and Analysis of Computer Algorithms, Addison-Wesley 1974.

Eines der Standardlehrbücher des Programmierens; für Mathematiker interessante Algorithmen werden vor allem in den Kapiteln 6–8 behandelt.

[Ak] A. Akritas: Elements of Computer Algebra with Applications, Wiley, 1989

Grundlegenden Algorithmen der Computeralgebra, außerdem vor allem verschiedene Algorithmen zur ggT-Berechnung für Polynome mit Subresultantenmethoden. Diese Methoden sind zwar der in der Vorlesung behandelten modularen Methode unterlegen, erlauben aber große Vereinfachungen bei der Berechnung von Sturmschen Ketten, die hier ebenfalls behandelt werden. Weitere Themen sind die symbolische Lösung von linearen Gleichungssystemen, Kodierungstheorie, Kryptographie, Faktorisierung von Polynomen in ℤ[X].

[BC] F. Brackx, D. Constales: Computer Algebra with LISP and RE-DUCE – An introduction to computer-aided pure mathematics, Kluwer 1991

Beginnt mit einer sehr ausführlichen Beschreibung des in der Vorlesung nicht behandelten Standard LISP, einem für REDUCE als Implementierungssprache definierten Minimal-LISP. Sodann werden die Sprachelemente von REDUCE behandelt, danach noch einige ausführlichere Beispiele für Anwendungen von REDUCE auf mathematische Probleme. Ausführlich beschrieben wird dabei insbesondere die Berechnung von Standardbasen für Polynomideale und die Implementierung von Unterprogrammen für die dreidimensionale Euklidische Geometrie.

[BCL] Buchberger/Collins/Loos: Computer Algebra – Symbolic and Algebraic Computation, Springer 1982, 1983 ist ein Klassiker; hier werden in Beiträgen verschiedener Autoren viele der Grundtechniken der Computeralgebra vorgestellt, die auch heute noch in fast allen Systemen angewandt werden. In den verschiedenen Beiträgen zu diesem Buch, einem Sonderband der Zeitschrift Computing, sind zu fast allen Themen der Vorlesung Ergänzungen zu finden, darüber hinaus zahlreiche Literaturhinweise, die durch ihr Alter keinesfalls uninteressant geworden sind.

[BR] R. Benedetti, J.-J. Risler: Real algebraic and semi-algebraic sets, Hermann 1990

Lehrbuch der semialgebraischen Geometrie im Hinblick auf Anwendungen im CAD. Obwohl das Buch so weit wie möglich auf Technik verzichtet, sind alle Sätze vollständig bewiesen. Algorithmische Aspekte werden ebenfalls angeschnitten, stehen aber nicht im Vordergrund.

[Can] J.F. Canny: The Complexity of Robot Motion Planning, MIT Press, Reihe ACM doctoral dissertation award, 1988

Anwendung der semialgebraischen Geometrie und Computeralgebra auf das Problem der Bewegungsplanung von Robotern in eimem Raum mit Hindernissen; dazu werden auch neue Algorithmen zur Bestimmung der Geometrie einer semialgebraischen Menge eingeführt, die deutlich besser sind als die vorher bekannten (und die ihrerseits inzwischen wieder durch kürzlich erschienene Arbeiten anderer Autoren verbessert wurden; siehe dazu etwa [AB]).

[CLO] D. Cox, J. Little, D. O’Shea: Ideals, varieties, and algorithms, Springer, Reihe Undergraduate texts in Mathematics, 1992

Lehrbuch der algebraischen Geometrie unter algorithmischen Apekten; als undergraduate text setzt dieses Buch sehr viel weniger voraus als die üblichen Lehrbücher der algebraischen Geometrie; es ist allerdings sehr breit geschrieben.

[DMR] M. Davis, Y. Matijasevič, J. Robinson: Hilbert’s tenth problem. Diophantine equations: positive aspects of a negative solution in Mathematical developments arising from Hilbert problems, Proc. Symp. Pure Math. 28 (1976), 323–378

Überblick über die Ergebnisse, die zur negativen Lösung des zehnten Hilbertschen Problems führten: Es ist nicht möglich, einen Algorithmus zu finden, der entscheidet, ob ein Polynom mehrerer Veränderlicher über den ganzen Zahlen eine ganzzahlige Lösung hat, da jede rekursiv aufzählbare Menge als eine solche Lösungsmenge geschrieben werden kann. Für einige gängige mathematische Probleme wird dies explizit vorgeführt.

[DST] Davenport/Siret/Tournier: Computer Algebra – Systems and algorithms for algebraic computation, Academic Press, 1988

Das Buch beginnt mit einer Einführung in das Computeralgebrasystem MAC-SYMA (und endet mit einem Anhang über REDUCE), danach werden Probleme der Darstellung und grundlegende Algorithmen behandelt, später dann theoretisch anspruchsvollere Verfahren. Beweise fehlen oft; ansonsten ist das Buch als allgemeine Einführung in die Computeralgebra und für einen Überblick sehr zu empfehlen.

[Hea] A.C. Hearn: REDUCE user’s manual version 3.3, Rand publication CP78

Die fast vollständige Beschreibung von REDUCE.

[HWM] Hehl/Winkelmann/Meyer: Computeralgebra – Ein Kompaktkurs über die Anwendung von REDUCE, Springer 1992

Leicht zu lesende Einführung in REDUCE 3.4.

[Kn] D.E. Knuth: The Art of Computer Programming; vol. 2: Seminumerical Algorithms, Addison-Wesley 1981

Kapitel 4 dieses Standardwerks behandelt ausführlich die Algorithmen zum Rechnen mit ganzen Zahlen beliebiger Länge und mit Polynomen, einschließlich modularer Methoden und der Faktorisierung. Alle Algorithmen werden exakt präsentiert, bewiesen und analysiert.

[Li] J.D. Lipson: Elements of algebra and algebraic computing, Addison-Wesley, 1981

Diese Buch wendet sich vor allem an Informatiker und ist daher sehr elementar und sehr breit geschrieben. Es behandelt die einfachsten Grundlagen der Algebra bis etwa hin zum Polynomring einer Veränderlichen mit Schwerpunkt auf den algebraischen Grundlagen der Computeralgebra wie etwa dem chinesischen Restesatz.

[Mi] M. Mignotte: Mathematics for Computer Algebra, Springer 1991

Behandelt vor allem Polynome einer Veränderlichen über den ganzen, reellen, komplexen Zahlen und über endlichen Körpern; für diese werden alle wesentlichen Algorithmen, Sätze, Schranken zusammengestellt und bewiesen. Insbesondere wird auch der in der Vorlesung nicht behandelte L^{3}-Algorithmus vorgestellt, der Polynome aus ℤ[X] durch Berechnung von Gitterbasen faktorisiert.

[Mo] P.L. Montgomery: Modular multiplikation without trial division, Math. Comp. 48 (1987), 243–246

Ein Trick, mit dessen Hilfe man modulare Multiplikationen ohne Division durch den Modulus ausführen kann.

[NQ] P. Naudin, C. Quitté: Algorithmique Algébrique, Masson 1992

Einführung in die Ringtheorie unter algorithmischen Gesichtspunkten; für die meisten Algorithmen werden vollständige ADA-Programme angegeben. Hauptanwendungen sind das Rechnen mit Zahlen, Modulararithmetik, Faktorisierung von Zahlen.

[MW] M. MacCallum, F. Wright: Algebraic computing with REDUCE, Oxford 1991

Nützliche Einführung in REDUCE, in der insbesondere auch der in der Vorlesung nicht behandelte symbolische Modus und sein Zusammenspiel mit dem (üblichen) algebraischen Modus gut erklärt wird – teilweise besser als im Handbuch. Auch die user contributed packages wie etwa das groebner-Paket werden beschrieben.

[Ray] G. Rayna: REDUCE – Software for algebraic computation, Springer, Reihe Symbolic Computation, 1987

Elementarer und ausführlicher als [MW]; der behandelte Stoffumfang ist deutlich geringer und bezieht sich auf die Vorgängerversion REDUCE 3.2.

[Ri] D. Richardson: Some unsolvable problems involving elementary functions of a real variable, J. Symb. Logic 33 (1968), 511–520

Der Unmöglichkeitssatz von Richardson in seiner Originalfassung; damals brauchte man noch Polynome und Exponenetialfunktionen, um eine beliebige rekursiv aufzählbare Menge zu beschreiben.

[W] P.S. Wang: An improved multivariate polynomial factoring algorithm, Math. Comp. 32 (1978), 1215–1231

Faktorisierung von Polynomen mehrerer Veränderlicher.