Ich muss f(x)=exp(A*x) für einen kleinen, variablen Spaltenvektor x und eine riesige, konstante Matrix A (viele Zeilen, wenige Spalten) wiederholt berechnen. Mit anderen Worten, die x sind wenige, aber die A*x sind viele. Meine Problemdimensionen sind so, dass A*x ungefähr so viel Laufzeit benötigt wie der exp () -Teil.
Abgesehen von der Taylor-Erweiterung und Vorberechnung eines Bereichs von Werten exp(y) (unter der Annahme, dass der Bereich y der Werte von A*x bekannt ist), die ich nicht erheblich beschleunigen konnte (bei Beibehaltung der Genauigkeit) In Bezug auf das, was MATLAB alleine macht, denke ich darüber nach, das Problem analytisch zu wiederholen, um einige Werte vorberechnen zu können.
Zum Beispiel finde ich das exp(A*x)_i = exp(\sum_j A_ij x_j) = \prod_j exp(A_ij x_j) = \prod_j exp(A_ij)^x_j
Dies würde mir erlauben, exp(A) einmal vorberechnen, aber die erforderliche Potenzierung in der Schleife ist so teuer wie der ursprüngliche exp() Funktionsaufruf, und die Multiplikationen (\ prod) müssen zusätzlich ausgeführt werden.
Gibt es eine andere Idee, der ich folgen könnte, oder Lösungen innerhalb von MATLAB, die ich vielleicht übersehen habe?
Bearbeiten: weitere Details
A ist 26873856 mal 81 groß (ja, es ist so groß), also x ist 81 mal 1.
nnz(A) / numel(A) ist 0.0012 , nnz(A*x) / numel(A*x) ist 0.0075 . Ich verwende bereits eine dünne Matrix, um A darzustellen, aber exp () einer dünn besetzten Matrix ist nicht mehr spärlich. In der Tat, ich speichere x nicht-sparse und ich berechne exp(full(A*x)) was sich als so schnell / langsam herausstellte wie full(exp(A*x)) (Ich denke A*x ist ohnehin nicht spärlich, da x nicht spärlich ist. ) exp(full(A*sparse(x))) ist eine Möglichkeit, ein spärliches A*x zu haben, ist aber langsamer. Noch langsamere Varianten sind exp(A*sparse(x)) (mit doppeltem Speicherausdruck für eine nicht-spärliche Matrix vom Typ sparse) und full(exp(A*sparse(x)) (was wiederum ein nicht-spärliches Ergebnis ergibt).
Ja, ich berechne elementweise exp, ich aktualisiere die obige Gleichung, um das zu reflektieren.
Noch eine Bearbeitung: Ich habe versucht, schlau zu sein, mit wenig Erfolg:
%Vor%Computer tun nicht wirklich Exponenten. Sie würden denken, dass sie das tun, aber was sie tun, sind hochgenaue Polynomnäherungen.
Referenzen:
Die letzte Referenz sah ziemlich gut aus. Vielleicht sollte es zuerst gewesen sein.
Da Sie an Bildern arbeiten, haben Sie wahrscheinlich eine diskrete Anzahl von Intensitätsstufen (255 normalerweise). Dies kann abhängig von der Art von "A" eine reduzierte Abtastung oder Suchvorgänge ermöglichen. Eine Möglichkeit, dies zu überprüfen, besteht darin, für eine ausreichend repräsentative Gruppe von Werten von "x" Folgendes zu tun:
%Vor%Wenn Sie Ihre Bilder in "interessanter" und "nicht so interessant" segmentieren könnten - wie wenn Sie eine Röntgenaufnahme betrachten würden, die in der Lage wäre, alle "außerhalb des menschlichen Körpers" liegenden Orte zu entfernen klemmen Sie sie auf Null, um Ihre Daten vorzusparen, was Ihre Anzahl eindeutiger Werte verringern könnte. Sie können das vorherige für jeden eindeutigen "Modus" innerhalb der Daten betrachten.
Zu meinen Ansätzen gehören:
Nun muss ich mich fragen, warum würden Sie in so vielen Wiederholungen von exp (A * x) * x leben und ich denke, dass Sie zwischen Frequenz- / Wellenzahldomäne und Zeit- / Raumdomäne wechseln könnten. Sie könnten sich auch mit Wahrscheinlichkeiten beschäftigen, die exp (x) als Grundlage verwenden und etwas Bayes-Spaß machen. Ich weiß nicht, dass exp (x) ein gutes Konjugat vorher ist, also werde ich mit dem Fourier-Material gehen.
Weitere Optionen: - Überlegen Sie sich, ob Sie fft, fft2 oder fftn für Ihre Matrizen verwenden - sie sind schnell und könnten einen Teil dessen tun, wonach Sie suchen.
Ich bin sicher, dass es eine Forier-Domain-Variante zu folgenden Punkten gibt:
Möglicherweise können Sie die Suche mithilfe der Woodbury-Matrix mit einer Berechnung kombinieren. Darüber müsste ich allerdings etwas nachdenken. ( link ) Irgendwann wusste ich, dass alles, was zählte (CFD, FEA, FFT), alles um die Matrixinversion ging, aber ich habe seitdem die besonderen Details vergessen.
Wenn Sie jetzt in MatLab leben, sollten Sie vielleicht einen "Coder" verwenden, der MatLab-Code in C-Code umwandelt. Egal wie viel Spaß ein Interpreter macht, ein guter C-Compiler kann viel schneller sein. Die Mnemonic (hoffentlich nicht zu ehrgeizig), die ich benutze, ist hier zu sehen: link ab ca. 13:49. Es ist wirklich einfach, aber es zeigt den Unterschied zwischen einer kanonisch interpretierten Sprache (Python) und einer kompilierten Version desselben (Cython / C).
Ich bin mir sicher, dass ich, wenn ich etwas konkreteres hätte und dazu aufgefordert wurde, mich intensiver an einer spezifisch relevanten Antwort beteiligen könnte.
Sie haben vielleicht keinen guten Weg, dies auf konventioneller Hardware zu tun. Kaufen Sie vielleicht etwas wie eine GPGPU. CUDA und seine Kollegen haben massiv parallele Operationen, die eine erhebliche Beschleunigung der Kosten für einige Grafikkarten ermöglichen. Sie können Tausende von "Kernen" (überglorifizierte Pipelines) haben, die die Arbeit einiger weniger ALUs erledigen, und wenn der Job ordnungsgemäß parallelisierbar ist (wie es aussieht), dann kann er viel schneller erledigt werden.
BEARBEITEN:
Ich dachte an Eureqa . Eine Option, die ich in Betracht ziehen würde, wenn ich ein "großes Eisen" für die Entwicklung, aber nicht für die Produktion hätte, wäre, ihr Eureqa-Produkt zu verwenden, um eine schnell genug und genau genug Näherung zu finden.
Wenn Sie eine "schnelle" Singulärwertzerlegung Ihrer "A" -Matrix durchgeführt haben, würden Sie feststellen, dass die dominante Leistung von 81 Eigenvektoren bestimmt wird. Ich würde mir die Eigenwerte ansehen und sehen, ob es nur wenige dieser 81 Eigenvektoren gibt, die den Großteil der Information liefern. Wenn das der Fall ist, dann kannst du die anderen auf Null klammern und eine einfache Transformation konstruieren.
Nun, wenn ich es wäre, würde ich "A" aus dem Exponenten herausholen wollen.Ich frage mich, ob Sie die 81x81-Eigenvektormatrix und "x" betrachten und ein wenig über lineare Algebra nachdenken können und welchen Raum Sie in Ihre Vektoren projizieren. Gibt es eine Möglichkeit, dass Sie eine Funktion erstellen können, die folgendermaßen aussieht:
f (x) = B2 · exp (B1 · x)
so dass das
B1 * x
ist viel kleiner als Ihr aktueller
Axe
Tags und Links performance matlab simplify exp