DSpace
KOBRA
KOBRA

KOBRA - Dokumentenserver der Universität Kassel  → Fachbereiche  → FB 10 / Mathematik und Naturwissenschaften  → Institut für Mathematik  → Algorithmische Algebra und Diskrete Mathematik  → Dissertationen 

Please use this identifier to cite or link to this item: http://nbn-resolving.de/urn:nbn:de:hebis:34-2009030226513

Title: Faktorisierung in Schief-Polynomringen
Authors: Horn, Peter
???metadata.dc.subject.swd???: ComputeralgebraVerschiebungsoperatorFaktorisierungLineare Algebra
???metadata.dc.subject.ddc???: 510 - Mathematik (Mathematics)
Issue Date: 2-Mar-2009
Abstract: In der Arbeit werden zunächst die wesentlichsten Fakten über Schiefpolynome wiederholt, der Fokus liegt dabei auf Shift- und q-Shift-Operatoren in Charakteristik Null. Alle für die Arithmetik mit diesen Objekten notwendigen Konzepte und Algorithmen finden sich im ersten Kapitel. Einige der zur Bestimmung von Lösungen notwendigen Daten können aus dem Newtonpolygon, einer den Operatoren zugeordneten geometrischen Figur, abgelesen werden. Die Herleitung dieser Zusammenhänge ist das Thema des zweiten Kapitels der Arbeit, wobei dies insbesondere im q-Shift-Fall in dieser Form neu ist. Das dritte Kapitel beschäftigt sich mit der Bestimmung polynomieller und rationaler Lösungen dieser Operatoren, dabei folgt es im Wesentlichen der Darstellung von Mark van Hoeij. Der für die Faktorisierung von (q-)Shift Operatoren interessanteste Fall sind die sogenannten (q-)hypergeometrischen Lösungen, die direkt zu Rechtsfaktoren erster Ordnung korrespondieren. Im vierten Kapitel wird der van Hoeij-Algorithmus vom Shift- auf den q-Shift-Fall übertragen. Außerdem wird eine deutliche Verbesserung des q-Petkovsek-Algorithmus mit Hilfe der Daten des Newtonpolygons hergeleitet. Das fünfte Kapitel widmet sich der Berechnung allgemeiner Faktoren, wozu zunächst der adjungierte Operator eingeführt wird, der die Berechnung von Linksfaktoren erlaubt. Dann wird ein Algorithmus zur Berechnung von Rechtsfaktoren beliebiger Ordnung dargestellt. Für die praktische Benutzung ist dies allerdings für höhere Ordnungen unpraktikabel. Bei fast allen vorgestellten Algorithmen tritt das Lösen linearer Gleichungssysteme über rationalen Funktionenkörpern als Zwischenschritt auf. Dies ist in den meisten Computeralgebrasystemen nicht befriedigend gelöst. Aus diesem Grund wird im letzten Kapitel ein auf Evaluation und Interpolation basierender Algorithmus zur Lösung dieses Problems vorgestellt, der in allen getesteten Systemen den Standard-Algorithmen deutlich überlegen ist. Alle Algorithmen der Arbeit sind in einem MuPAD-Package implementiert, das der Arbeit beiliegt und eine komfortable Handhabung der auftretenden Objekte erlaubt. Mit diesem Paket können in MuPAD nun viele Probleme gelöst werden, für die es vorher keine Funktionen gab.This thesis first sums up the most important facts about skew polynomials, where the main focus is on shift and q-shift operators in characteristic zero. All concepts and algorithms necessary for arithmetics with these objects are introduced in chapter one. Some information necessary to compute solutions can be read off the Newton polygon, a geometrical shape associated to an operator. This is explained and derived in the second chapter. Especially for the q-shift case, this is new. The third chapter is dedicated to the computation of polynomial and rational solutions, following mainly the ideas of Mark van Hoeij. The most interesting solutions from a factoring point of view are the (q-)hypergeometric solutions, since they are in one-to-one correspondence with first order right factors. Their computation is addressed in the fourth chapter. The van Hoeij algorithm is transferred to the q-case. Furthermore, using information from the Newton polygon, the Petkovsek algorithm is significantly improved in the q-case. The computation of general order factors is the topic of the fifth chapter. The adjoint operator introduced allows to compute left-hand factors. Then an algorithm for arbitrary order factors is shown, which unfortunately is not practical for orders beyond four. For most of the algorithms described above the solution of linear systems over the field of rational functions is needed. Most computer algebra systems do not solve this task satisfyingly fast. Therefore, in the sixth chapter, an algorithm for this task based on evaluation and interpolation is introduced. This algorithm turns out to be superior to those implemented in the tested systems. All algorithms are implemented as a MuPAD package, which is part of the thesis. This package offers a convenient way to handle the objects considered. Using this package many problems can be solved that were undoable in MuPAD so far.
URI: urn:nbn:de:hebis:34-2009030226513
Appears in Collections:Dissertationen

Files in This Item:

File Description SizeFormat
Software.zipQuellcode und Beispiele156.35 kBZIPView/Open
DissertationHorn.pdf893.92 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.