|
Anzeige
|
schneller als FFT
Gast
#3457654
In diesem Artikel wird ein Algorithmus angedeutet, der schneller als eine FFT arbeiten soll: http://web.mit.edu/newsoffice/2013/leaner-fourier-transforms-1211.html Weis jemand genaueres darüber? Gibt es eventuell ein Matlab Beispiel?
Gast
#3457676
December 11, 2013 "[...] in January [...] will reveal an algorithm [...]" Es dürfte also eher unwahrscheinlich sein, als Außenstehender bereits Details darüber zu finden. Ist das dann die FFFT?
Gast
#3457737
Fang' mit diesem paper [1] an. Mit dem kannst du dir bis zum Symposium die Zeit vertreiben. Fragen kannst du jederzeit hier stellen. [1] http://arxiv.org/pdf/1201.2501v1.pdf
Gast
#3460147
Schon interessant, was für ein Aufwand getrieben wird, Schätzalgorithmen zu erdenken, um Rechenzeit zu sparen - in Zeiten, in denen im Zweifelsfall nichts mehr vorhanden ist, als Rechenleistung (...abgesehen von Speicher). Man nehme ein dickes FPGA. Für Anwendungen in der Bild- und Tonverarbeitung mag dieser Aufwand gerechtfertigt sein, da die Signalkette - von Aufnahmegerät bis Konsument - noch schwächere Glieder aufweist, als dass solche Verfahren hier großen Schaden anrichten könnten. In welchen Gebieten machen solche Verfahren eurer Meinung nach außerdem Sinn?
Gast
#3460161
Trendanalysen?
Gast
#3460163
>panikplauze Schon mal drüber nachgedacht, dass man leicht sehr quasi beliebig grosse Datenmengen generieren kann, aber die Verarbeitung der Datenmegen trotz schneller Server/GPGPUs immer noch Probleme bereitet. Bestes Beispiel ist das CERN, wo man Probleme hat, die Daten in Real-Time zu verarbeiten und danach zu speichern. Also nix mit dickem FPGA, eine Serverfarm ist immer noch schneller. Ist der FFT Algo 10% schneller, so braucht man 10% weniger Rechner, was unter Umständen viel Geld entspricht, wenn die Serverfarm gross ist, wie im CERN. Und im Gegensatz zu anderen Tricks, wie z.B. Teile des Programms in Assembler und SIMD Befehlen auf einen bestimmten CPU abzustimmen, bleibt der Code bei der Verwendung eines schnellern Algos portabel und ist einfacher verständlich. Tomate schrieb: > Und im Gegensatz zu anderen Tricks, wie z.B. Teile des > Programms in Assembler und SIMD Befehlen auf einen bestimmten CPU > abzustimmen, bleibt der Code bei der Verwendung eines schnellern Algos > portabel und ist einfacher verständlich. Ausserdem lautet die erste Optimierungsregel: find a better algorithm. Grüße, Kurt > Fang' mit diesem paper [1] an.
Das ist dann aber schon keine normale FFT mehr... In der Hinsicht wäre
der Goertzel ja dann auch schon eine schnellere FT als die FFT ;)
Gast
#3460483
Das NSA muss auch große Datenmengen auf Muster und Regelmäßigkeiten untersuchen.
Gast
#3462590
Tomate schrieb: > Ist der FFT Algo 10% schneller, so braucht man 10% weniger Rechner, was > unter Umständen viel Geld entspricht, wenn die Serverfarm gross ist, wie > im CERN. Na gut, für solche Spezialanwendungen mag das zutreffen um die Datenmengen grob vorzusortieren. Die Rede ist von O(log log N)! Ich kann mir jedoch nicht vorstellen, dass die darauf folgenden Analysen mit diesen Schätzalgorithmen durchgeführt werden. Ein ähnliches Szenario kann ich mir auch in Video-Schnittsoftware vorstellen, wo Previews oder Previewanalysen mit den sehr schnellen Algos gemacht werden, das Mastering hingegen mit den klassischen. Schaut mal nach compressed sensing. Soweit ich es gesehen habe ist die neue fft nicht fuer äquidistant abgetastete signale und setzt gewisse a-prioiri Kenntnisse über das Signal vorraus. panikplauze schrieb: > Schon interessant, was für ein Aufwand getrieben wird, Schätzalgorithmen > zu erdenken, um Rechenzeit zu sparen - in Zeiten, in denen im > Zweifelsfall nichts mehr vorhanden ist, als Rechenleistung Ja, die verfügbare Rechenleistung ist toll, wenn man aber mal vom Heim-PC weggeht kommt man sehr schnell an den Punkt, an dem die Rechenleistung nichtmehr im Überfluss vorhanden ist. Und ein Schätzalgorithmus bedeutet bei richtiger Anwendung, das man die gleichen Ergebnisse mit weniger Rechenzeit bekommt. Und Rechenzeit bedeutet Energieaufwand. Ist die Berechnung 5% schneller, spart man auch 5% Strom. Auf einem mobilen Gerät bedeutet das, die Akkulaufzeit wird besser. In einer Serverfarm wird weniger Rechenleistung benötigt => geringere Anschaffungs- und Unterhaltkosten. Gruß Kai
Gast
#3502194
die Geschichte ist doch schon weit über ein Jahr alt und wurde hier auch bereits diskutiert. Die FFT ist ungenauer und eignet sich nur für SW Implementierungen, wenn Zeit gespart werden soll. Ein Görzel oder Cooley–Tukey im FPGA geradeaus implementiert ist effektiver. Antwort schreiben |
Anzeige
|
