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?
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.
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
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?
>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 ;)
Das NSA muss auch große Datenmengen auf Muster und Regelmäßigkeiten untersuchen.
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
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.