Hühne, Paul Christoph: Beiträge zum Entwurf größenoptimaler schneller Fouriertransformationen auf gewissen homogenen Räumen symmetrischer Gruppen. - Bonn, 2016. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5n-45359
@phdthesis{handle:20.500.11811/6917,
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5n-45359,
author = {{Paul Christoph Hühne}},
title = {Beiträge zum Entwurf größenoptimaler schneller Fouriertransformationen auf gewissen homogenen Räumen symmetrischer Gruppen},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2016,
month = nov,

note = {Sei Sn die symmetrische Gruppe auf {1,...,n} und Sn-k die Untergruppe von Sn, die die Elemente j>n-k stabilisiert. Komplexwertige Funktionen auf dem homogenen Raum Sn/Sn-k identifizieren wir mit den Funktionen auf Sn, die konstant auf den Linksnebenklassen von Sn-k sind. Mit anderen Worten werden Funktionen auf der Sn betrachtet, die Sn-k-rechtsinvariant sind. Maslen hat 1998 einen Algorithmus beschrieben, bei dem die Auswertung der diskreten Fouriertransformation von Sn-k-rechtsinvarianten Signalen mit Θ(nk+1) arithmetischen Operationen durchführbar ist. Für den Fall k=1 haben Clausen and Kakarala 2010 einen Algorithmus vorgestellt, der die Auswertung der Fouriertransformation von Sn-1-invarianten Signalen mit Θ(n) arithmetischen Operationen berechnet. Die vorliegende Arbeit setzt die bisherigen Arbeiten fort. Es wird ein Ansatz beschrieben, mit dem sich für kleine k asymptotisch optimale Algorithmen zur Auswertung von Sn-k-invarianten Signalen herleiten lassen. Konkret werden asymptotisch optimale Algorithmen für die Fälle k=2 und k=3 konstruiert. Beispielsweise ist nun die Auswertung der diskreten Fouriertranformation eines Sn-2-invarianten reellwertigen Signals auf der Sn für n=5000 mit weniger als einer Sekunde auf einem Einsteiger-Notebook möglich. Zudem sind diese Algorithmen mit einem Speicheraufwand von Θ(nk) ebenfalls asymptotisch gesehen optimal. Diese Algorithmen können in neueren Anwendungen bezüglich des Graphlet-Spektrums von Kondor et al. oder Kondors Ansatz für eine Branch-and-Bound Lösung des NP-schweren Quadratic Assigment Problems, die sich vollständig im Spektralbereich der Sn abspielt, verwendet werden.},
url = {http://hdl.handle.net/20.500.11811/6917}
}

Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:

InCopyright