ISBN 978-3-8439-0489-6

978-3-8439-0489-6, Reihe Mathematik

Stefan Steidel
Parallel modular computation in commutative algebra

91 Seiten, Dissertation Technische Universität Kaiserslautern (2012), Softcover, A5

Zusammenfassung / Abstract

In this thesis we investigate parallel modular algorithms in commutative algebra with a focus on standard bases, primary decomposition and normalization. The concept of modularization in principle consists of three steps whereupon each of these steps is parallelizable: solving the considered problem modulo sufficiently many prime numbers, lifting process and verifying the lifted result. From the theoretical point of view it is thereby always the crucial point to find a sufficient verification of the lifted result which may not be too expensive compared to the previous steps. If a modular approach to the considered problem is reasonable because of an appropriate verification test it is then, from a practical point of view, not too difficult to develop a modular algorithm.

We reveal that the concept of modularization is a very powerful tool in computer algebra, especially if the considered problem is difficult to solve. The usage of an increasing number of cores for the parallel modular computations speeds up the whole algorithm enormously if every single calculation in positive characteristic takes some time. Nevertheless, one always has to take care of the communication and synchronization between the different subtasks and one has to be aware of the fact that for simple problems the computational overhead might be larger than the intrinsic complexity to compute a resolution of the problem itself. Similarly, if the computations in positive characteristic are comparatively fast then an increasing number of cores may slow down the algorithm since the overhead because of communication dominates the process.

In dieser Arbeit werden parallele modulare Algorithmen in der Kommu- tativen Algebra mit einem Fokus auf Standard Basen, Primrzerlegung und Normalisierung untersucht. Das Konzept der Modularisierung besteht prin- zipiell aus drei Schritten, von denen jeder einzelne parallelisierbar ist: Lo ̈sung des entsprechenden Problems modulo genu ̈gend vieler Primzahlen, Liftungs- prozess und Verifikation des gelifteten Resultats. Aus theoretischer Sicht ist es dabei immer entscheidend, eine hinreichende Verfikation des gelifteten Resultats zu finden, welche nicht zu aufwendig sein darf im Vergleich zu den vorhergehenden Schritten. Falls ein modularer Lo ̈sungsansatz des betrach- teten Problem auf Grund eines geeigneten Verifikationstests sinnvoll ist, so ist es aus praktischer Sicht nicht allzu schwer einen modularen Algorithmus zu entwickeln.

Es wird deutlich, dass das Konzept der Modularisieung ein sehr ma ̈chti- ges Werkzeug in der Computer Algebra ist, speziell wenn das betrachtete Problem schwierig zu lo ̈sen ist. Die Verwendung mehrerer Kerne fu ̈r die parallelen modularen Berechnungen beschleunigt den gesamten Algorith- mus enorm, falls jede einzelne Rechnung in positiver Charakteristik einige Zeit dauert. Gleichwohl muss man dabei immer auf die Kommunikation und die Synchronisation zwischen den verschiedenen Teilproblemen aufpas- sen und man muss sich daru ̈ber bewusst sein, dass fu ̈r einfache Probleme der rechnerische Overhead gro ̈ßer sein kann als der eigentliche Aufwand fu ̈r die Berechnung einer Lo ̈sung des Problems selbst. Gleichermaßen kann eine Verwendung mehrerer Kerne den Algorithmus verlangsamen, falls die Be- rechnungen in positiver Charakteristik vergleichsweise schnell sind, so dass der Overhead auf Grund der Kommunikation dominiert.