Faster than Fast Fourier
Eieiei. Das MIT will einen bis zu zehnmal schnelleren Alternativ-Algorithmus zur Fast Fourier Transformation gefunden haben. Wär Beth nicht schon tot hätt ihn jetzt der Schlag getroffen. Mal sehen, ob da was dran ist und sich das als tauglich erweist.
Allerdings bin ich da durchaus skeptisch. Ich habe den Algorithmus zwar noch nicht gesehen (und bin da in der Mathematik auch lange nicht mehr so fit wie ich es mal war), aber an der erwähnten Presseerklärung kommt mir was faul vor. Nämlich daß es manchmal schneller ist, der Algorithmus also naheliegenderweise für häufig vorkommende Signale optimiert ist. Wie Kompressionsverfahren. Die haben auch immer irgendwo Schwachstellen, bei denen sie ineffektiv werden.
Der Witz an der FFT ist nämlich, daß sie ein sogenannter flacher Algorithmus ist. Der Programmlauf hängt überhaupt nicht von den eingegebenen Daten ab. Es gibt kein if/else oder while oder sowas, das von den zu verarbeitenden Daten abhängt, nur von der Größe des Datenfensters. Das hat eine Menge Vorteile. Für die FFT muß die Maschine nicht Turing-fähig sein. Im Prinzip kann man die FFT auch zur Kompilationszeit auswickeln und als eine simple Reihe von Multiplikations-, Additions- und Tauschbefehlen aufschreiben, die immer exakt gleich läuft. Man kann beispielsweise ein Steuerwerk mit beliebig vielen Rechenwerken betreiben, weil der Ablauf immer derselbe ist.
Eine Besonderheit von Signalprozessoren ist (die sind etwas aus der Mode gekommen), daß jeder Befehl unabhängig von den Daten eine ganz bestimmte, vorher bekannte Zahl von Taktzyklen benötigt, egal welche Daten man eingibt. Man kann also vorher ganz präzise und verlässlich sagen, wie lange eine FFT dauern wird. Und das auf Signalprozessoren dann ohne jegliche Uhr oder Interrupts oder sowas vollsynchron in Echtzeit laufen lassen. Das ist in vielen Anwendungen wichtiger als der durchschnittliche Aufwand.
Die Presseerklärung läßt erkennen, daß der Aufwand bei diesem Verfahren von den eingegebenen Daten abhängt und anscheinend eben nicht immer schneller als FFT ist. In der Signalverarbeitung nutzt es aber nichts, wenn ein Algorithmus manchmal oder sogar häufig schnell ist, weil der „Worst Case” zählt. Der Algorithmus muß immer funktionieren ohe aus dem Takt zu kommen. Insofern könnte sich das Ding als akademisch erweisen.
Das hat natürlich auch irgendwo einen Aspekt der IT-Sicherheit. Einen flachen, konstant und synchron ablaufenden, nicht Turing-Fähigkeit verlangenden Algorithmus wie FFT, der eigentlich nur Rechenwerke steuert, dem die eingegebenen Daten aber letztlich völlig egal sind, kann man durch die Wahl der Daten praktisch nicht angreifen. Immer dann, wenn die Laufzeit von den Daten abhängt und der Algo Turingfähigkeit voraussetzt, stellt sich die Frage, mit welchen Daten man den Algorithmus aus der Bahn werfen kann.
Ich wäre da erstmal vorsichtig.
Zumal Rechenleistung heutzutage nicht das Problem ist, die steht eigentlich bei vielen Anwendungen ausreichend zur Verfügung. Stabilität, Fehlerfreiheit und verlässliches Timing sind meistens eigentlich wichtiger.
8 Kommentare (RSS-Feed)
Ich bin noch dabei das Paper durchzuarbeiten, aber meines Erachtens ist der Geschwindigkeitsboost um den Faktor 10 (selbst, wenn der Algorithmus stabil laufen würde) auch nur akademischer Natur. Das liegt daran, dass bei den meisten Problemen aus der digitalen Bildverarbeitung (bzw. Signalverarbeitung oder überall da, wo FFT sonst noch so zum Einsatz kommt) die FFT sowieso schon eine der schnelleren Operationen ist gegenüber den Sachen, die man eigentlich gerade lösen will.
Ich hab im Bereich der Bildverarbeitung schon ein bisschen was gemacht (3D-Rekonstruktion, Zerfetzte Bilder wieder zusammensetzen etc.) und da war es bisher immer so, dass der Flaschenhals nicht in der FFT sondern in anderen Bereichen lag.
Das ist wieder plumpe Uni-PR um es in die Medien zu schaffen.
Wenn ich schon “bis zu 10 mal schneller lese” dann weiss ich sofort
das gilt nur für ganz besondere Fälle/Umstände. Und was steht im Artikel, genau das, nur wird da nach und nach die Katze aus dem Sack gelassen.
Angepasste FFT für Spezialfälle ist nix neues. Solche Sonderfälle auszunutzen findet man bei Algorithmen aller Art immer wieder.
Wie gesagt eine reine PR-Meldung des MIT. -> Tonne
Siehe auch Goertzel-Algorithmus
Ich weiß nicht, ob die den “wiedererfunden” haben, aber der ist auch im speziellen schneller als die FFT.
In den USA scheint die Konzentration auf bestimmte Algorithmen ohne diese wirklich zu verstehen sehr stark verbreitet zu sein.
Ich hatte schon das Vergnügen, dass man verwundert war, dass ich das “Sortieren” von Unterstationsnummern stark beschleunigen konnte. Man kann 1 Million Zahlen von 0 bis 999 natürlich sortieren und dann zählen.
Bei der FFT ist zwischen N log N und N nicht viel Platz zum Optimieren.
@HF: Denkfehler! Sie reden von einer Beschleunigung um bis zu Faktor 10. Konstante Faktoren werden im O-Kalkül nicht berücksichtigt. (Und sind ohnehin eher dubios, weil das Verhältnis von eingesparten Rechenoperationen und dem Mehraufwand durch Programmsprünge usw. maschinenabhängig ist, was ja gerade der Grund ist, warum es im O-Kalkül nicht vorkommt.) Es würde mich algorithmisch verblüffen,w enn die unter N log N kämen, weil da bei einer Eingabe von N Werten und einer Ausgabe von N Werten, von denen jeder nachweisbar von jedem Eingabewert abhängt, mit Linear nicht viel läuft.
Man kann sich trefflich drüber streiten, ob ein Algorithmus, der höchstens um einen konstanten Wert schneller ist, noch dazu maximal Faktor 10, überhaupt schneller ist, denn es hat guten Grund, daß man sowas im O-Kalkül nicht berücksichtigt. Weil es nicht viel sagt.
Bei der FFT ist zwischen N log N und N nicht viel Platz zum Optimieren.
Der asymptotische Aufwand eines neuen Algorithmus mag kleiner sein, aber was nützt es, wenn die real existierenden konstanten Vorfaktoren dafür sorgen, dass auf einem realen Prozessor erst für N größer 10 hoch 2000 ein Vorteil entsteht? Der Artikel selbst scheint mir aber ganz vernünftig zu sein.
@Hadmut: Kannst Du Dir vorstellen, dass die “Informatik” wieder in die Fächer auseinanderfällt, aus denen sie vor 50 Jahren geschaffen wurde?
Theoretische Informatik und Praktische Informatik haben fast nichts miteinander zu tun, ausser dem verkrampften Versuch schlechter Theoretiker, das eine als das andere zu verkaufen.
@HF
“Theoretische Informatik und Praktische Informatik haben fast nichts miteinander zu tun, ausser dem verkrampften Versuch schlechter Theoretiker, das eine als das andere zu verkaufen.”
Die praktische Langsamkeit von Programmen ist nur zu oft zu spüren. Nämlich immer dann, wenn die Theorie nicht verstanden und Algorithmen ohne Prüfung der Vorrausetzungen gewählt wurden.
Ich sehe durchaus ein (theoretisches) Anwendungsfeld für sowas. Sicher nicht für Signalprozessoren oder die klassische professionelle Anwendung mit dedizierter Hardware.
Für irgendwelche mobilen Anwendungen könnte es aber durchaus sinnvoll sein, so einen Algorithmus zu haben. Da wäre nicht selten genug Kapazität für den Worst Case da, man will ja aber möglichst wenig nutzen um Strom zu sparen.
Bleibt alleine die Frage nach einer irgendwie praxisrelevanten Anwendung auf einem Mobiltelefon…
Je nachdem wie empfindlich der Algorithmus auf “falsche” Eingaben ist und wie schlecht er dann wird könnte sich sowas aber auch bei größerer Hardware lohnen, wenn viele Instanzen parallel laufen.