Factorization of multivariate polynomials
Martin Mok-Don Lee · Publication Server of Kaiserslautern University of Technology (Kaiserslautern University of Technology) · 2013
Faktorisierung von multivariaten Polynomen ist ein Grundstein fur viele Anwendungen in der Computeralgebra. Zur Berechnung dient ein Algorithmus, der von Zassenhaus 1969 zur Faktorisierung von univariaten Polynomen uber \(\mathbb{Z}\) benutzt wurde. Spater hat Musser diesen Algorithmus auf den multivariaten Fall ubertragen. In der Folge wurde der Algorithmus immer weiter verfeinert und verbessert. In dieser Arbeit wird jeder Schritt des Algorithmus beschrieben, sowie die Probleme, die in diesen Schritten auftauchen. Dabei werden nur die Koeffizientenbereiche \(\mathbb{F}_{q}\), \(\mathbb{Z}\) und \(\mathbb{Q}(\alpha)\) betrachtet. Der Fokus liegt besonders auf der schnellen Implementierung. Der Autor dieser Arbeit hat fast alle Algorithmen, die in dieser Arbeit beschrieben werden, in der C++ Bibliothek factory, die Teil des Computeralgebrasystems Singular ist, implementiert. Neben der Implementierung wird eine neue Schranke fur die Koeffizienten eines Faktors eines multivariaten Polynoms uber \(\mathbb{Q}(\alpha)\) bewiesen, die nicht voraussetzt, dass \(\alpha\) eine ganze algebraische Zahl ist. Diese Schranke ermoglicht es, dass Hensel Lifting und Rekombinieren von Faktoren modular berechnet werden konnen. Des Weiteren werden diverse Unterschritte verbessert. Abschliesend wird ein Uberblick uber die Leistungsfahigkeit der Implementierung gegeben mit diversen Benchmarkbeispielen sowie zufallig erzeugtem Input, der einen Eindruck uber die durchschnittliche Performance geben soll.