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

Abstract

Sei <em>S_n</em> die symmetrische Gruppe auf {1,...,<em>n</em>} und <em>S_n-k</em> die Untergruppe von <em>S_n</em>, die die Elemente <em>j>n-k</em> stabilisiert. Komplexwertige Funktionen auf dem homogenen Raum <em>S_n</em>/<em>S_n-k</em> identifizieren wir mit den Funktionen auf <em>S_n</em>, die konstant auf den Linksnebenklassen von <em>S_n-k</em> sind. Mit anderen Worten werden Funktionen auf der <em>S_n</em> betrachtet, die <em>S_n-k</em>-rechtsinvariant sind. Maslen hat 1998 einen Algorithmus beschrieben, bei dem die Auswertung der diskreten Fouriertransformation von <em>S_n-k</em>-rechtsinvarianten Signalen mit Θ(<em>n</em>^<em>k+</em>1) arithmetischen Operationen durchführbar ist. Für den Fall <em>k=</em>1 haben Clausen and Kakarala 2010 einen Algorithmus vorgestellt, der die Auswertung der Fouriertransformation von <em>S</em>_<em>n-</em>1-invarianten Signalen mit Θ(<em>n</em>) arithmetischen Operationen berechnet. Die vorliegende Arbeit setzt die bisherigen Arbeiten fort. Es wird ein Ansatz beschrieben, mit dem sich für kleine <em>k</em> asymptotisch optimale Algorithmen zur Auswertung von <em>S_n-k</em>-invarianten Signalen herleiten lassen. Konkret werden asymptotisch optimale Algorithmen für die Fälle <em>k=</em>2 und <em>k=</em>3 konstruiert. Beispielsweise ist nun die Auswertung der diskreten Fouriertranformation eines <em>S</em>_<em>n-</em>2-invarianten reellwertigen Signals auf der <em>S_n</em> für <em>n=</em>5000 mit weniger als einer Sekunde auf einem Einsteiger-Notebook möglich. Zudem sind diese Algorithmen mit einem Speicheraufwand von Θ(<em>n^k</em>) 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 <em>S_n</em> abspielt, verwendet werden.