• search hit 2 of 36
Back to Result List

## Factorization of multivariate polynomials

• Factorization of multivariate polynomials is a cornerstone of many applications in computer algebra. To compute it, one uses an algorithm by Zassenhaus who used it in 1969 to factorize univariate polynomials over $$\mathbb{Z}$$. Later Musser generalized it to the multivariate case. Subsequently, the algorithm was refined and improved. In this work every step of the algorithm is described as well as the problems that arise in these steps. In doing so, we restrict to the coefficient domains $$\mathbb{F}_{q}$$, $$\mathbb{Z}$$, and $$\mathbb{Q}(\alpha)$$ while focussing on a fast implementation. The author has implemented almost all algorithms mentioned in this work in the C++ library factory which is part of the computer algebra system Singular. Besides, a new bound on the coefficients of a factor of a multivariate polynomial over $$\mathbb{Q}(\alpha)$$ is proven which does not require $$\alpha$$ to be an algebraic integer. This bound is used to compute Hensel lifting and recombination of factors in a modular fashion. Furthermore, several sub-steps are improved. Finally, an overview on the capability of the implementation is given which includes benchmark examples as well as random generated input which is supposed to give an impression of the average performance.
• Faktorisierung von multivariaten Polynomen ist ein Grundstein für viele Anwendungen in der Computeralgebra. Zur Berechnung dient ein Algorithmus, der von Zassenhaus 1969 zur Faktorisierung von univariaten Polynomen über $$\mathbb{Z}$$ benutzt wurde. Später hat Musser diesen Algorithmus auf den multivariaten Fall übertragen. 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 für die Koeffizienten eines Faktors eines multivariaten Polynoms über $$\mathbb{Q}(\alpha)$$ bewiesen, die nicht voraussetzt, dass $$\alpha$$ eine ganze algebraische Zahl ist. Diese Schranke ermöglicht es, dass Hensel Lifting und Rekombinieren von Faktoren modular berechnet werden können. Des Weiteren werden diverse Unterschritte verbessert. Abschließend wird ein Überblick über die Leistungsfähigkeit der Implementierung gegeben mit diversen Benchmarkbeispielen sowie zufällig erzeugtem Input, der einen Eindruck über die durchschnittliche Performance geben soll.