Show simple item record

Beiträge zum Entwurf größenoptimaler schneller Fouriertransformationen auf gewissen homogenen Räumen symmetrischer Gruppen

dc.contributor.advisorClausen, Michael
dc.contributor.authorHühne, Paul Christoph
dc.date.accessioned2020-04-23T00:12:25Z
dc.date.available2020-04-23T00:12:25Z
dc.date.issued29.11.2016
dc.identifier.urihttp://hdl.handle.net/20.500.11811/6917
dc.description.abstractSei 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.
dc.language.isodeu
dc.rightsIn Copyright
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectsymmetrische Gruppe
dc.subjecthomogener Raum
dc.subjectdiskrete Fouriertransformation
dc.subjectFFT
dc.subjectFaltung
dc.subject.ddc004 Informatik
dc.titleBeiträge zum Entwurf größenoptimaler schneller Fouriertransformationen auf gewissen homogenen Räumen symmetrischer Gruppen
dc.typeDissertation oder Habilitation
dc.publisher.nameUniversitäts- und Landesbibliothek Bonn
dc.publisher.locationBonn
dc.rights.accessRightsopenAccess
dc.identifier.urnhttps://nbn-resolving.org/urn:nbn:de:hbz:5n-45359
ulbbn.pubtypeErstveröffentlichung
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.affiliation.locationBonn
ulbbnediss.thesis.levelDissertation
ulbbnediss.dissID4535
ulbbnediss.date.accepted2016-05-31
ulbbnediss.instituteMathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Informatik / Institut für Informatik
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeWeber, Andreas


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

The following license files are associated with this item:

InCopyright