Beiträge zum Entwurf größenoptimaler schneller Fouriertransformationen auf gewissen homogenen Räumen symmetrischer Gruppen
Beiträge zum Entwurf größenoptimaler schneller Fouriertransformationen auf gewissen homogenen Räumen symmetrischer Gruppen
Dokument öffnen (1.1MB)Art der Hochschulschrift
DissertationPrüfungsdatum
31.05.2016Datum der Veröffentlichung
29.11.2016Erstgutachter
Clausen, MichaelZweitgutachter
Weber, AndreasMetadaten
Zur Langanzeige
Zitierbare Links 
Inhalt
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.
Schlagwörter
symmetrische Gruppe, homogener Raum, diskrete Fouriertransformation, FFT, Faltung
Klassifikation (DDC)
004 InformatikHü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
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 = {https://hdl.handle.net/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 = {https://hdl.handle.net/20.500.11811/6917}
}
Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:
