Wolfram Koepf: Computeralgebra - Eine algorithmisch orientierte Einführung.
Springer, Berlin-Heidelberg-New York, 2006, ISBN 3-540-29894-0

Vorwort

Das vorliegende Lehrbuch über Computeralgebra gibt eine Einführung in dieses moderne Gebiet der Mathematik. Es entstand im Laufe der letzten fünf Jahre und umfaßt den Stoff zweier vierstündiger Vorlesungen, die ich mehrfach an der Universität Kassel durchgeführt habe. Als ich im Jahr 2000 an die Universität Kassel kam und im Sommersemester 2000 zum ersten Mal die Vorlesung Computeralgebra und im darauffolgenden Wintersemester die Vorlesung Computeralgebra 2 abhalten durfte, begann ich mit der Niederschrift. Ich habe diese Vorlesungen dann mehrfach an der Universität Kassel für Studenten der Studiengänge Diplom-Mathematik, gymnasiales Lehramt Mathematik, Bachelor Computational Mathematics sowie Bachelor Informatik ab dem dritten Studiensemester abgehalten.

Vorausgesetzt werden also lediglich einige Kenntnisse aus der linearen Algebra sowie der elementaren Analysis (sowie eine intuitive Vorstellung von einem Wahrscheinlichkeitsmaß). Daher ist das Buch auch für interessierte Gymnasiallehrer als Quelle zum Verständnis für Algorithmen der Computeralgebra oder als Vertiefung in Leistungskursen sehr gut geeignet. Ich habe mich bemüht, die wichtigsten Prinzipien und Algorithmen der Computeralgebra aufzunehmen, deren Beweise ich allerdings so elementar wie möglich führe. Da ich den Besuch einer Algebra-Vorlesung nicht voraussetzen konnte, habe ich auf tiefliegende algebraische Argumente verzichtet. Die Präsentation ist mehr algorithmisch als algebraisch orientiert. Beispielsweise wird der Chinesische Restsatz (lediglich) als Algorithmus und nicht als Isomorphiesatz formuliert. Die vorliegende Vorlesung ersetzt keine Algebra-Vorlesung, sie wirbt vielmehr für eine algebraische Vertiefung.

In der einführenden Computeralgebra-Vorlesung habe ich in etwa den Stoff der ersten neun Kapitel durchgenommen. Dieser Kanon scheint mir die unverzichtbare Grundlage der Computeralgebra darzustellen. Jeder Dozent wird allerdings sicher eigene Akzente setzen. Ich habe beispielsweise aus Zeitmangel die Beweise einiger Sätze über endliche Körper weggelassen und auf den Beweis im Text verwiesen, ein anderer Dozent wird vielleicht lieber auf das Kapitel über Codierungstheorie und Kryptographie verzichten, obwohl nach meiner Erfahrung die Studierenden gerade dieses Kapitel sehr gerne annehmen. Eine weitere Variante besteht darin, die Algorithmen für ganze Zahlen und für Polynome (wie beispielsweise den euklidischen Algorithmus und seine Erweiterung) parallel anstatt hintereinander zu behandeln. Kann man höhere Algebrakenntnisse voraussetzen, werden einige Beweise kürzer. Dem jeweiligen Dozenten bleiben also genügend Auswahlmöglichkeiten, um seinen eigenen Stil zu bewahren.

In den ersten beiden Kapiteln wird vorgestellt, was ein Computeralgebrasystem kann und wie man in einem solchen System programmiert. Danach wird die Ganzzahlarithmetik behandelt, die die Grundlage jedes Computeralgebrasystems darstellt. Nach dem modularen Rechnen mit dem chinesischen Restsatz, dem kleinen Satz von Fermat und der Betrachtung von Primzahltests folgt dann zunächst ein Kapitel über Codierungstheorie und Kryptographie, in welchem die behandelten zahlentheoretischen Grundlagen angewandt werden. Hier wird u.a. das RSA-Verfahren behandelt.

Als nächstes werden Polynome betrachtet, wobei hier die Algorithmen der Ganzzahlarithmetik erneut ins Spiel kommen. Es folgt der Kronecker-Algorithmus zur Faktorisierung von Polynomen mit ganzzahligen Koeffizienten. Im Kapitel über algebraische Zahlen wir dann die modulare Arithmetik von einem neuen Standpunkt aus betrachtet. Nun können auch endliche Körper und Resultanten eingeführt werden. Im folgenden Kapitel über Polynomfaktorisierung werden moderne effizientere Algorithmen behandelt und implementiert. Es folgt ein Kapitel über Vereinfachung und Normalformen, welches den Kanon der ersten Vorlesung abschließt.

Die Kapitel 10-12 stellen die Themen der von mir durchgeführten weiterführenden Vorlesung bereit und sind naturgemäß stärker von meinen eigenen Interessen geprägt. Diese Auswahl ist nach meiner Überzeugung für eine weiterführende Vorlesung besonders gut geeignet, denn die Kapitel wenden das in der ersten Vorlesung erarbeitete Wissen auf Themen an, die jedem Mathematikstudenten während seines Studiums begegnen und die auch viele Mathematik-Anwender benötigen und interessieren: Potenzreihen, Summationsformeln und Integration. Während man Potenzreihen bereits in der Analysis kennenlernt und beispielsweise in der Physik und in der Wahrscheinlichkeitstheorie benötigt, treten Summationsformeln überall in Mathematik und in Anwendungen auf. Unbestimmte Integration schließlich wird im allgemeinen als ein schwieriges Problem der Analysis betrachtet, und es ist nicht unmittelbar klar, daß man dieses Problem mit Methoden der Algebra anpacken kann.

Naturgemäß konnte ich nicht alle relevanten Themen der Computeralgebra aufnehmen, auch weil das Buch eine direkte Vorlage zu zwei Vorlesungen liefern und daher nicht zu umfangreich sein sollte. Beispielsweise habe ich mich entschieden, die Theorie der Gröbnerbasen wegzulassen, obwohl diese eine sehr bedeutende Rolle in Computeralgebrasystemen spielen, insbesondere bei der Lösung polynomialer Gleichungssysteme, wo Gröbnerbasen inzwischen Resultanten den Rang abgelaufen haben. Will man dieses Thema allerdings gründlich behandeln, so muß man hierfür entweder höhere Algebrakenntnisse voraussetzen oder es wird daraus leicht ein eigenes Buch. Hier verweise ich also lieber auf die bereits vorhandene Literatur, beispielsweise das für eine Vorlesung oder ein Seminar sehr gut geeignete Buch von Cox, Little und O'Shea (1997). Ebenfalls hätte ich gerne den für viele Anwendungen wichtigen LLL-Algorithmus von Lenstra, Lenstra und Lovász (1982) behandelt, mußte diesen aus Platzgründen aber ebenfalls weglassen. Bei einer weiteren Vertiefung ist eine Behandlung dieser beiden Themenkreise allerdings zwingend.

Alle betrachteten Algorithmen des Buchs werden in Sitzungen mit dem Computeralgebrasystem Mathematica programmiert und getestet.Dies geht auf eine persönliche Präferenz des Autors zurück. (Ich halte Mathematica für die Lehre am besten geeignet, denn die Oberfläche ist ausgereifter als die der Konkurrenz, sie ist schneller, leichter zu bedienen und hat mehr Eingabemöglichkeiten. Für die Forschung allerdings ist Mathematica<> nur sehr begrenzt geeignet, da sich Ergebnisse in der Regel nicht verifizieren lassen, denn Mathematica verfügt über keine Möglichkeit, den Rechenablauf und die verwendeten Algorithmen zu hinterfragen. Hier haben Maple und MuPAD deutliche Vorteile.) Dennoch ist der jeweilige Dozent keineswegs an dieses System gebunden, denn die Definitionen und Sätze des Buchs sind selbstverständlich völlig unabhängig von einem speziellen Computeralgebrasystem.

Um das Buch vollends systemunabhängig zu gestalten, habe ich im Internet auf der Webseite http://www.mathematik.uni-kassel.de/~koepf/CA alle Computeralgebra-Sitzungen des Buchs auch als Maple-Worksheets und MuPAD-Notebooks bereitgestellt. Die drei verwendeten Systeme sind allesamt sogenannte General Purpose-Systeme und beherrschen die Mathematik in einer Breite, die dem Themenumfang des Buchs entspricht. Sie besitzen ferner die Möglichkeit, Sitzungen in einem internen Format (Mathematica: Notebooks .nb; Maple: Worksheets .mws und .mw; MuPAD: Notebooks .mnb und .mn) abzuspeichern.

Die in einem derartigen Notebook oder Worksheet abgespeicherten Befehle können jederzeit erneut vom System berechnet werden, was eine Vorführung durch den Dozenten ermöglicht. Ich habe die Computeralgebra-Sitzungen in meinen Veranstaltungen mit Laptop und Beamer vorgeführt und die Rechenergebnisse jeweils während der Vorlesung erzeugt. Dies gibt den Studenten die Möglichkeit, die Algorithmen direkt nachzuvollziehen, und es können auch immer sofort weitere Beispiele betrachtet werden, die von den Studierenden vorgeschlagen werden. Ferner können die Algorithmen im Sinne experimenteller Mathematik ohne Umweg zum Testen benutzt werden.

Aus diesem Grund war mir auch wichtig, die Algorithmen nicht - wie in vielen anderen Büchern zum Thema - in Pseudocode darzustellen, sondern als lauffähige Programme. Im Rahmen dieses Buchs bzw. der im Internet verfügbaren Maple- und MuPAD-Quellen liegen alle betrachteten Algorithmen in den drei Systemen Mathematica, Maple und MuPAD vor. Ich denke, daß dies für viele Leser nützlich sein dürfte. Was den Übungsbetrieb betrifft: Mit allen drei Systemen können die Studenten sehr einfach ihre bearbeiteten Übungsblätter als Notebooks oder Worksheets digital zum Korrigieren einreichen, und der übungsleiter kann diese Dateien dann korrigiert zurückgeben.

Als Sprecher der Fachgruppe Computeralgebra habe ich einige Tagungen zum Thema Computeralgebra in Lehre, Ausbildung und Weiterbildung organisiert. Auf diesen Tagungen bin ich des öfteren von Gymnasiallehrern nach Literatur zu den Algorithmen der Computeralgebra gefragt worden. Mit diesem Buch liegt auch für diesen Leserkreis eine leicht verständliche Beschreibung der algorithmischen Grundlagen von Computeralgebrasystemen vor. Bislang gibt es - bis auf das kürzlich ebenfalls beim Springer-Verlag erschienene Buch von Michael Kaplan (2004), welches allerdings höhere Algebrakenntnisse voraussetzt - keine derartige Quelle in deutscher Sprache. Da das Buch elementar gehalten ist, ist es auch als Nachschlagewerk über Algorithmen der Computeralgebra gut geeignet, denn es besitzt einen sehr ausführlichen Index.

Als Grundlage für die ersten 9 Kapitel des vorliegenden Buchs konnte ich auf die englischsprachigen Bücher Childs (1979), Geddes, Czapor, Labahn (1992) und von zur Gathen, Gerhard (1999) zurückgreifen. Das Buch von Lindsay Childs entstand bereits 1979 und war sicher eines der ersten Bücher über Algorithmen der Computeralgebra, obwohl dies der Titel A Concrete Introduction to Higher Algebra nicht unbedingt suggeriert. Ebenfalls eine sehr wertvolle Quelle ist das Buch von Geddes, Czapor und Labahn aus dem Jahr 1992, das im wesentlichen eine sehr ausführliche und gut lesbare Beschreibung der Fähigkeiten von Maple darstellt. Schließlich erschien 1999 das Buch der beiden Autoren von zur Gathen und Gerhard, das man durchaus als Computeralgebra-Bibel bezeichnen kann. Aufgrund seiner Fülle und seiner höheren Algebra-Voraussetzungen scheint dieses Buch als Grundlage für eine einführende Vorlesung allerdings nicht direkt geeignet zu sein.

Das vorliegende Buch wäre nicht entstanden ohne die Hilfe zahlreicher Kollegen, Mitarbeiter und Studenten, die mir mit Rat und Tat zur Seite standen, den Text an etlichen Stellen abrunden und viele große und kleine Fehler der Erstfassung korrigieren halfen. Ganz besonders bedanken möche ich mich bei meinem langjährigen Forschungskollegen Dr. Dieter Schmersau, mit dem ich unzählige Gespräche über das gesamte Material geführt habe sowie bei Dr. Reinhard Oldenburg, der ebenfalls sehr ausführlich Korrektur gelesen hat. Schließlich geht mein Dank an meine Mitarbeiter, Studenten und Freunde Imran Hafeez, Peter Horn, Detlef Müller, Torsten Sprenger und Jonas Wolf. Jeder der Genannten hat mir wertvolle Hinweise zum Text gegeben und jedem Einzelnen ist zu verdanken, die Anzahl schlecht verständlicher Textteile, Druckfehler etc. deutlich vermindern zu helfen. Eine besonders unangenehme Fehlerquelle war die mehrfache Anpassung des Textes auf neue Mathematica-Versionen im Laufe der Jahre. Ich hoffe und bin einigermaßen zuversichtlich, daß das nun veröffentlichte Buch keine sinnentstellenden Fehler mehr enthält. Ich kann allerdings selbstverständlich nicht dafür garantieren, ob sich neue Versionen von Mathematica - bzw. in den ausgearbeiteten Sitzungen Maple und MuPAD - wie beschrieben verhalten werden.

Ein herzlicher Dank geht auch an die Universität Kassel für die Genehmigung zweier Forschungssemester im Zeitraum des Entstehens dieses Buchs, ohne die eine Fertigstellung nicht möglich gewesen wäre. Ebenfalls bedanke ich mich beim Konrad-Zuse-Zentrum Berlin für die Möglichkeit, dort in den letzten 5 Jahren an meinem Buch arbeiten zu können. Schließlich möchte ich mich beim Springer-Verlag bedanken, der mein Projekt von Anfang an begleitet und unterstützt hat.

Kassel, 20. November 2005, Wolfram Koepf
Wolfram Koepf
25. Februar 2006