ich habe eine Anwendung, die mir insgesamt zu langsam läuft. Als Nadelöhr hat sich dabei die Cholesky-Zerlegung einer großen, dünnbesetzten Matrix herausgestellt.
Matrix-Größe: ca. 7000 x 7000 Einträge
Nicht-Null-Einträge: ca. 0,1 bis 0,25 %
Ausprobiert habe ich bisher die Cholesky-Zerlegung mit der Apache Commons Math Bibliothek und mit Parallel Colt, wobei Parallel Colt deutlich schneller ist und somit mein aktueller Stand.
Allerdings liegt die Laufzeit je nach Anzahl der Nicht-Null-Einträge zwischen 3 und 17 Sekunden, was für meine Anwendung deutlich zu lange ist.
Ich bin mir bewusst, dass es Algorithmen gibt, die die zu zerlegende Matrix erst permutieren, um bessere Ergebnisse zu erzielen (wen es interessiert: algorithm - Cholesky decomposition of sparse matrices using permutation matrices - Stack Overflow). Eigentlich möchte ich aber mit der Cholesky-Zerlegung überhaupt nichts zu tun haben und nur ein cholesky.decompose() aufrufen und mit dem Ergebnis weiter arbeiten.
Kennt jemand eine Java-Bibliothek, die eine schnelle Cholesky-Zerlegung dünnbesetzter Matrizen anbietet?
Oder kann mir jemand Benchmark-Tests verschiedener solcher Bibliotheken nennen, die mir einen Performance-Überblick bieten?
Die Stackoverflow-Frage lässt nicht gerade hoffen, dass ich viel Rückmeldung bekomme, ich bin aber für jeden Gedanken dankbar!
Damit kann ich dir leider nicht weiterhelfen. Aber allgemein hilft es manchmal, das Problem etwas großraumiger anzuschauen. Es gibt Situationen, da versucht man alles mögliche, um den Weg von B nach C zu optimieren, für den Weg von A nach D gibt es aber noch ganz andere und weit einfachere / schnellere Lösungen.
Theoretisch gibt es sowas wie cuSPARSE :: CUDA Toolkit Documentation , aber (erstens bin ich mir nicht mal 100% sicher, dass das das ist, was du suchst … in Bezug auf die Anwendungen hab’ ich teilweise nicht so den Überblick :o und) man müßte halt mal testen, ob das was bringen kann.
Der allgemeinere Ansatz von @Crian hat mich auf die eigentlich recht offensichtliche Idee gebracht, nochmal ein bisschen was anderes zu probieren, danke für den Schubs.
Ich benötige die Cholesky-Zerlegung (natürlich) für das Lösen eines linearen Gleichungssystems, deshalb habe ich es noch einmal versucht mittels LU-Zerlegung und QR-Zerlegung zu lösen, was aber erwarteter Weise noch langsamer als die Cholesky-Zerlegung war.
Die Frage, ob ich das noch großräumiger umgehen könnte, und der Beitrag von @Marco13 haben mich bewogen, noch einmal meine Situation kurz näher zu erläutern.
Der Algorithmus, den ich implementiere, stammt nicht von mir. Die Autoren geben aber Laufzeiten an, die insgesamt (ca. 10 Iterationen) im Bereich weniger Sekunden liegen und sind stolz darauf, das ohne GPU-Implementierung geschafft zu haben. Bei mir liegt aber nun zum Teil eine Iteration schon im Bereich von fast 20 Sekunden – für deutlich kleinere Probleme.
Da das Ganze „nur“ Teil meiner Bachelorarbeit ist, ist es nicht weiter schlimm, dass meine Laufzeiten so schlecht sind. Zumal die gewählte Sprache sicherlich auch noch einen großen Einfluss darauf hat, aber das ist eine andere Frage. Ich hätte mir lediglich gewünscht, dass ich mit einer schnelleren Bibliothek näher an die Vorgaben heranreiche, da die Unterschiede ja schon enorm sind. So werde ich mich aber eher auf kleinere Probleme beschränken.
Vielen Dank nochmal so weit.
Und wenn doch noch jemand eine schnelle Cholesky-Zerlegung dünnbesetzter Matrizen hat – immer her damit.
FALLS du eine (einigermaßen aktuelle) NVIDIA-Karte hast:
Ob GPU OK ist oder nicht, weiß ich jetzt nicht. Aber ich verweise mal (shameless self promotion? Neee) auf jcuda.org - Samples , wo als „JCudaMatrixCgSample20141023.zip“ ein kleines Testprojekt ein CG-Solver drinsteckt. Das ganze ist NUR eine kleine Demo, und eigentlich NICHT für den „Produktiveinsatz“ gedacht, aber … wie schnell das ganze im Vergleich ist, würde mich auch mal interessieren @Bleiglanz Das ist ein echtes Problem (bin mir gerade (wegen der Google-Links) nicht sicher, ob das von dir sarkastisch gemeint war…)
Okay. Vielleicht hätte ich die Lösung schneller gefunden, wenn Parallel Colt nur ein bisschen angenehmer zu nutzen wäre oder die API nicht ganz so kurz gehalten wär. Aber im Prinzip ist Parallel Colt schnell, man muss nur wissen wie:
Statt SparseDoubleCholeskyDecomposition cholesky = new SparseDoubleCholeskyDecomposition(a, 0);
bewirkt ein SparseDoubleCholeskyDecomposition cholesky = new SparseDoubleCholeskyDecomposition(a, 1);
Wunder.
Der Wert 1 bewirkt, dass ein AMD-Algorithmus ausgeführt wird, also die Matrix günstig permutiert wird. Das steht auch in der API, nur ein bisschen arg knapp.
Die Unterschiede sind bemerkenswert. Jetzt wird eine Cholesky-Zerlegung einer 15000 x 15000 Matrix mit ca. 0,1 % Nicht-Null-Einträgen innerhalb von 400 ms ausgeführt!
Ein bisschen bin ich ja trotzdem noch versucht, JCuda eine Chance zu geben, aber nur ein bisschen
Hierbei stellt sich natürlich auch die Frage, auf was für Systemen diese Laufzeiten ermittelt wurden. Gibt es dazu Angaben? Falls die Rechner um den passenden Faktor schneller sein sollten, müsstest du dir vielleicht gar keine Sorgen machen müssen.
