Some Tapas of Computer Algebra
Cohen, Arjeh M., Cuypers, Hans, Sterk, Hans (Eds.)
Springer-Verlag, Berlin Heidelberg, 1999, HC 48,10 €
ISBN 3-540-63480-0
In einem Restaurantführer von Mallorca wird von den sagenhaften vielfältigen Appetithäppchen Tapas gesprochen und diese dann weiter beispielhaft erläutert: kleine gebackene Calamares, Serrano-Schinken mit Melone oder in Fetteig gebackene Gemüsehäppchen.
Ist man so eingestimmt, dann sollte einem Computeralgebraiker das Wasser im Munde zusammenlaufen, wenn ihm oder ihr ein Buch mit dem Titel Some Tapas of Computer Algebra vorgelegt wird. Es handelt sich in der Tat um ein ungewöhnliches Buch über Computeralgebra!
Das Buch ist als vierter Band in der vom Springer-Verlag aufgelegten Reihe Algorithms and Computations in Mathematics erschienen. Die drei Herausgeber haben insgesamt neunzehn Autoren gewonnen bei dem Projekt mitzuwirken, das aus Kurzeinführungen in die Computeralgebraan der Technischen Universität in Eindhoven entstanden ist. Das Buch teilt sich in zwei Teile, mehr als drei Viertel des Buches sind elf Appetitanregern zu teilweise ganz verschiedenen Themen der Computeralgebragewidmet, die meisten zentralen Themen der Computeralgebrasind angesprochen. Der zweite Teil enthält dann sieben Projektvorschläge, die auf den zuvor behandelten Themen aufsetzen.
So wird beispielsweise von H. Cuypers, Leonhard H. Soicher und Hans Stark auf 24 Seiten im Tapas Working with Finite Groups eine Kurzeinführung in Computational Group Theory gegeben. Es werden zum einen Permutationsgruppen mit Algorithmen zur Bestimmung von Bahnen und Stabilisatoren, insbesondere der Schreier-Sims-Algorithmus behandelt, zum andern Gruppen, die durch Erzeugende und Relationenen gegeben sind. Der Todd-Coxeter-Algorithmus zur Abzählung von Nebenklassen erlaubt - wenn er terminiert - eine Darstellung als Permutationsgrupppe von Nebenklassen einer Untergruppe. Ein eher beschreibender Stil, der Ideen und Zusammenhänge verbunden aber mit zahlreichen Hinweisen zu weiterführender Literatur aufzeigt, macht den Beitrag zu einem Appetitanreger, der dann im Projekt 6 The Small Mathieu Groups von denselben Autoren sowie im Projekt 5 Explorations with the Icosahedral Group von A.M. Cohen, H. Cuypers und R. Riebeck weiter gestillt werden kann.
G. Ivanyos und L. Ronyai erläutern in Computations in Associative and Lie Algebras einige Methoden zur Bestimmung von Radikalen, einfachen Komponenten sowie von Nullteilern in endlich-dimensionalen Algebren.
Dem zentralen Thema Gröbnerbasen sind mehrere Tapas und Projekte gewidmet. Zum einen gibt A. Cohen eine dreißigseitige Einführung in Gröbnerbasen, während - darauf aufbauend - L. Gonzalez-Vega, F. Roiullier und M.-F. Roy elf Symbolic Recipes for Polynomial System Solving für den Fall von nur endlich vielen Lösungen geben. Die Rezepte sind in drei Klassen eingeteilt, zum einen die grundlegenden Techniken zur Bestimmung von Lösungen aus der Theorie der Gröbnerbasen, dann Methoden aus der Linearen Algebra (Eigenwerte, Vielfachheiten, Satz von Stickelberger, Spur) und schließlich die Jakobi-Determinante für den Fall von gleich vielen Gleichungen und Unbestimmten, bevor dann Gröbnerbasen und numerische Approximation in Zusammenhang gebracht werden.
G. M. Ziegler stellt dann die von Conti und Traverso hergestellte Beziehung zwischen Gröbner Bases and Integer Programming aus dem Gebiet der Optimierung und Operations Research dar - ein sehr interessanter, wenn auch vermutlich von einem Praxiseinsatz noch weit entfernter Zusammenhang -, während M. de Boer und R. Pellikaan Gröbner Bases for Codes in der Codierungstheorie einsetzen. Dieser Abschnitt ist eine Kurzeinführung in Grundbegriffe der Codierungstheorie, wobei Gröbnerbasen nur kurz bei der Bestimmung aller Codewörter von zyklischen Codes - es operiert die zyklische Gruppe auf den Codewörtern, oder äquivalent dazu, die Codewörter bilden ein Ideal des Polynomrestklassenring über einem endlichen Körper (modulo xn-1) - mit Minimalgewicht sowie in einem Zusammenhang mit Gewichtsfunktionen eine Rolle spielen. Dies wird dann aber im Projekt 7 für Golay-Codes ausgearbeitet. Im Abschnitt 11 Gröbner Bases for Decoding von denselben Autoren wird erläutert in welcher Weise Gröbnerbasen bei gewissen Klassen von Codes zum Dekodieren benutzt werden können.
Ein weiterer Abschnitt von L. Gonzalez-Vega, F. Rouillier, M.-F. Roy und G. Trujillo widmet sich den verschiedenen symbolischen Techniken, wenn man speziell an reellen Lösungen interessiert ist: Verallgemeinerung wie Sylvester-Habicht der Sturmschen Ketten zur Abzählung der reellen Nullstellen eines Polynoms, aber auch für Systeme von Polynomgleichungen; Quantorenelimination.
Der LLL-Gitter-Reduktionsalgorithmus von Lentra, Lenstra und Lovacs wird von F. Beukers in einem zehnseitigen Abschnitt präsentiert. Neben der traditionellen Faktorisierungsalgorithmen für Polynome von Berlekamp sowie die Idee von Cantor-Zassenhaus und der Faktorisierung mit Hilfe von Hensels Lemma kann dann auch deren Faktorisierungsalgorithmus mit polynomialer Laufzeit im nächsten Abschnitt vom selben Autor dargestellt werden.
M. van der Put stellt im Abschnitt Symbolic Analysis of Differential Equations einige Methoden zur Integration von Funktionen sowie für Gleichungen der Ordnung 2 (Kovacic) vor, nachdem zuvor einige Grundideen der Differential-Galoistheorie (Picard-Vessiot) erläutert werden: Analog zum klassischen Fall von Wurzeln eines Polynoms werden auch hier die Lösungen in Zusammenhang zu Gruppen gebracht, aus deren Struktur dann im Prinzip die Lösungen entwickelt werden können. Auffallend ist für mich hier, daß bei den Literaturverweisen zur Integrationstheorie nur auf ein Vorlesungsmanuskript, nicht aber auf die in der selben Reihe erschienenen Monographie dazu von M. Bronstein verwiesen wird.
Die weiteren Projekte behandeln u.a. die Themen Robotersteuerung, Interpolation, Quaternionen sowie automatisches Beweisen von geometrischen Sätzen durch Modellierung einer Fragestellung, ob ein Polynom - der Implikation des Satzes entsprechend - im Ideal - erzeugt von den Polynomen, die den Voraussetzungen des Satzes entsprechen - enthalten ist.
Wie im Restaurant werden die vielfältigen und unterschiedlichen Appetithappen auf unterschiedliche Geschmäcker treffen. Der Verdienst dieser Zusammenstellung ist es aber schon, hier ein reichliches Angebot mit Kurzeinführungen zu wichtigen Themen der Computeralgebra gegeben zu haben. Diese können für allgemeine Vorlesungen zur Computeralgebra, für Seminare und Arbeitsgruppen als Startpunkte verwendet werden. Ich sehe auch den einen oder andern motivierten Gymnasiallehrer, der sich über die mathematischen Hintergründe der Computeralgebra-Systeme, die er oder sie oder die Schüler im Unterricht benutzen, weiterbilden will, mit Gewinn dieses Buch nutzen.
Rezension: Johannes Grabmeier (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 24 - März 1999