mschnell hat geschrieben:Die dünn besetzten Matrizen braucht man zur Berechnung bestimmter physikalischer Prozesse (z.B. in einer Physik-Engine).
Nein. die Feststellung lautet vielmehr: "Es gibt relativ viele lineare mathematische Probleme, die beim Lösen mit Matrizen dünnbesetzte Matrizen erzeugen. Die Vorgänge, die eine PhysikEngine berechnet, gehören auch dazu."
mschnell hat geschrieben:Es gibt Verfahren, die dünn besetzte Matrix-Gleichungen besser (schneller und/oder genauer) lösen als das normale Gauss-Jordan-Verfahren.
JA! Insbesondere schneller. Die Wikipedia sagt dazu:
http://de.wikipedia.org/wiki/Krylow-Unterraum-Verfahren Das sind relativ neue Verfahren. Aber sie haben den Nachteil, dass sie nur auf bestimmte Matrizen anwendbar sind. Das Verfahren der Konjugierten Gradienten ist zwar das Schnellste, aber in Bezug auf die Matrizen, die es akzeptiert, ist es eine Primadonna. Daher wurden etliche Verfahren daraus abgeleitet, die einen ähnlichen Lösungsansatz haben, aber die man auf eine ganz normale dünnbesetzte Matrix anwenden kann. Zum Beispiel das BiCGStab-Verfahen (Bi-Konjugate-Gradient-Stabilized-Method).
mschnell hat geschrieben:direkt oder iterativ ?
Iterativ.
mschnell hat geschrieben:Dein Verfahren macht keine bestimmten Voraussetzungen über die besetzten Stellen der Matrix (ist aber nur sinnvoll, wenn die allermeisten Elemente = 0 sind).
Ja. Ich mache deshalb keine Voraussetzungen, weil das Zeug noch in Entwicklung ist. Du hast also keine ausgereiften Verfahren vor Dir. Zum Beispiel ist Dein Verfahren sicherlich viel effektiver als mein Gauss-Jordan-Solver. Du betreibst Pivot-Optimierung, wohingegen ich eine Methode "SetDominatingDiagonal" laufen lasse (ich vertausche Zeilen, aber nicht sehr effektiv) und Du hast zusätzlich beim Lösen Threads laufen und ich nicht. Man muss aber sagen, dass der Gauss-Jordan-Solver meist die letzte Rettung ist, der geht fast immer, wenn die anderen Solver irgendwo im Wald veschwinden. Nur einmal habe ich festgestellt, dass sogar der Gauss-Jordan-Solver versagt hat, aber ich bin dem Fehler nicht nachgegangen. Da muss vermutlich noch viel getestet werden.
Ach ja: und Alexander hat komplexe Zahlen dabei. Leider rührt er sich nicht mehr. Er ist aber vermutlich der einzige Mathematiker hier und würde daher dringend gebraucht werden. Es gibt vielleicht Dinge, die man im Ansatz eines solchen Projektes auch berücksichtigen sollte. Dünnbesetzte Matrizen gehören meiner Meinung nach dazu. Es ist nämlich so: WENN Alexander ein Mathematiker ist und WENN er sich für numerische Mathematik interessiert, dann wird er sich dann in seinen Allerwertesten beißen, weil er dunnbesetzte Matrizen nicht berücksichtigt hat. Ein Rewrite wird dann notwendig sein und genau das will ich ihm ersparen.
mschnell hat geschrieben:Sind nicht meist strengere Vorgaben sinnvoll, die eine weniger komplexe Definition der Matrix erlauben ?
Ich weiß jetzt nicht genau, was Du damit meinst. Meine Definition ist eigentlich ganz simpel, einfacher gehts nicht. Die Matrix hat quadratisch zu sein und man muss zunächst definieren, wieviele Zeilen man hat. Dann wird Zeile für Zeile eingegeben, zum Schluß die Rechte Seite. Null-Elemente müssen nicht eingegeben werden. Der Algo für das Finden von Elementen ist eine schnelle binäre Suche. Das wars schon.
mschnell hat geschrieben:Bleiben die Matrizen im Laufe der Bearbeitung so unterbesetzt, dass die komplexe Darstellung mit Records sinnvoll bleibt, oder müssen neue Elemente <> 0 kreiert werden ?
Die Eingabematrix muss bei der Berechnung der schnellen Solver unverändert erhalten bleiben. Unverändert bedeutet, dass sie höchstens in eine andere Matrix mit dem gleichen Lösungsvektor umgewandelt werden darf, also Zeilen umsortieren etc. ist erlaubt. Kurz: Nein, es müssen keine neuen Elemente <> Null erzeugt werden. Das wäre auch kontraproduktiv, wegen den dynamischen Arrays würde das zuviel Zeit in Anspruch nehmen und wäre, soweit ich weiß auch nicht sehr speicherfreundlich.
mschnell hat geschrieben:st für die Mesh-Geschichte (Polygon-Netze) nicht tatsächlich eine Bearbeitung in der Grafikkarte das gegebene ?
Tja, das glauben die meisten Leute. Aber das ist definitiv nicht so. Das alte OpenGL, das den meisten Leuten viele Goodies und Erleichterungen angeboten hat, wird nicht mehr weiterentwickelt. Es gibt jetzt Geometry-Shader, aber die erwarten für Ihre Berechnungen ziemlich viele Eingaben vom Programmierer. Die berechnen beileibe nicht alles selbst. Die schwierigen langwierigen Dinge müssen der Grafikkarte mundgerecht zur Kenntnis gebracht werden, also vorberechnet werden. Ich habe den Leuten zugesehen, die gejubelt haben: "Es gibt jetzt OpenGL3!" Aber was dabei nicht so laut gesagt wurde: vom Programmierer wird jetzt viel mehr höhere Mathematik verlangt also voher. Und Mathematiker sind eine dünngesäte Spezies.
Ich bin auch kein Mathematiker. Aber ich brauche das Zeug. Ich habe nachgesehen, ob es solche Software gibt. Ja die gibt es. Aber alles in C,C++,Fortran(!), sogar Python. Aber nichts in Pascal.
Viele Grüße
Traude
Verein
Links
Suche