UNIVERSITÄTSBIBLIOTHEK
Das Suchergebnis hat sich seit Ihrer Suchanfrage verändert. Eventuell werden Dokumente in anderer Reihenfolge angezeigt.
  • Treffer 78 von 226
Zurück zur Trefferliste

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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Martin Mok-Don Lee
URN (Permalink):urn:nbn:de:hbz:386-kluedo-35553
Betreuer:Gerhard Pfister
Dokumentart:Dissertation
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):27.06.2013
Jahr der Veröffentlichung:2013
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Annahme der Abschlussarbeit:10.06.2013
Datum der Publikation (Server):27.06.2013
Seitenzahl:III, 95
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012