+ Antworten
Ergebnis 1 bis 12 von 12

Thema: Library für Matrizen

  1. #1
    User short Themenstarter

    Registriert seit
    20.12.2015
    Fachbeiträge
    20
    Genannt
    0 Post(s)
    Hallo

    Ich würde gerne eine externe Java library gebrauchen um Matrizen darzustellen und Operationen auf ihnen auszuführen. Ich habe die jeigen library gefunden, welche sehr gut und schnell zu sein scheint. Natürlich gibt es auch noch die Apache Commons library und viele andere. Meine Anforderungen sind die folgenden:

    • Handling von grossen Matrizen
    • Übliche Matrix-Operationen
    • Schnell
    • Möglichkeit auf Kolonnen und Zeilen zuzugreifen.
    • Kolonnen und Zeilen hinzufügen/entfernen (keine fixed size Matrizen)
    • Möglichkeit missing values darzustellen (wie z.B. not a number etc.)
    • Thread-safety (dies könnte ich aber auch selber sicherstellen)



    Hat da jemand schon Erfahrungen und kann eine empfehlen?

  2. #2
    Global Moderator Viertel Gigabyte
    Registriert seit
    05.08.2008
    Fachbeiträge
    4.905
    Genannt
    309 Post(s)
    Eine konkrete Empfehlung für eine bestimmte Library werde ich nicht abgeben.

    Aber ich habe schon in verschiedenen Zusammenhängen nach ähnlichen Libraries gesucht. Die genannten Anforderungen klingen teilweise recht vordergründig. Man stelle sich eine Matrix-Library vor, die wie folgt für sich wirbt:
    Features of the CML (Crappy Matrix Library)
    • Very memory consuming (can only handle Matrices up to 13x17)
    • Does not offer any matrix operations at all (yeah, NONE of them!)
    • Very slow! (The latest version is 34% slower than the previous one!)
    (Aber teilweise ist natürlich klar, was gemeint ist )

    Ein paar Gedanken dazu:

    1. Große Matrizen. Da stellt sich natürlich die Frage: WIE groß? Und: Geht es um Dense oder Sparse Matrizen? Die meisten (außer den "einfachsten") Libraries haben ja die explizite Unterscheidung zwischen Dense und Sparse Matrizen. Ganz grob kann man sagen: Sparse Matrizen brauchen weniger Speicher, sind aber langsamer (und bieten ggf. weniger (effiziente) Operationen an.

    2. Die "üblichen" Matrix-Operationen: Da kann man teilweise sehr weit gehen, in bezug auf die Frage, was "üblich" ist. Mutliplikation, Transponieren, Invertieren? Joa. LU-Faktorisierung mit Cholesky-Preconditioner? Naja. Bequeme, effiziente, elementweise Operationen auf den Matrizen? Hm.

    3. Performance. Auch da kann man sehr viel Aufwand reinstecken. Bei sowas wie Java Matrix Benchmark ist jemand schonmal recht weit gegangen. Aber die Abwägung muss da auch auf den Anwendungsfall bezogen sein. Das fängt an bei den VIELEN (!) Freiheitsgraden, die so ein Performancetest hat: Kleine vs. Große Matrizen? Dünnbesetzt vs. dichtbesetzt? Welche Operationen genau müssen besonders performant sein? Welche Prioritäten setzt man, in bezug auf den Trade-Off zwischen Performance, Einfachheit, Generalität, Flexibilität? Die Multiplikation zweiter ("großer") dichtbesetzter double-Matrizen wird man in Java kaum schneller machen können, als mit JCublas. Das soll aber keine Eigenwerbung sein: Der Aufwand, um diese Operation mit dieser Performance zu nutzen, ist vergleichsweise hoch, und die Flexibilität (oder allgemeiner: Der Erfüllungsgrad der anderen Punkte) ist gering bzw. schlicht NICHT vorhanden.

    4. Zugriff auf Zeilen/Spalten: Das bieten "viele" Libraries, mit unterschiedlichen Abstufungen. Wenn die Library auch nur einen Hauch Abstraktion hat, kann man sowas auch recht trivial selbst implementieren (wobei es, wenn es mit der jeweiligen Library "einfach" möglich ist, es meistens auch schon eingebaut ist )

    5. Zeilen/Spalten hinzufügen/entfernen: Da wird es schon deutlich dünner. Man muss wohl damit rechnen, dass eine Library, die auf Algebra/BLAS Operationen ausgelegt ist, eine Matrix nicht als "rechteckige, über 2D indizierbare Liste" ansieht, sondern wirklich als Matrix - und eine Matrix hat eine bestimmte Größe, und üblicherweise ist die nicht dynamisch....

    6. Missing values darstellen: Da steckt im hervorgehobenen Wort eine Anforderung, die von fast KEINER Library angeboten wird: Die Darstellung. Im oben angedeuteten Sinn zielen die meisten Libraries eben darauf ab, eine Library für Mathematische Operationen zu sein. Etwas, womit nur gerechnet wird. Die Darstellung ist ein Thema, das dazu komplett orthogonal ist (sein kann/sein sollte...). Es GIBT natürlich libraries, wo ~"zusätzlich noch irgendwas für die Visualisierung" angeboten wird. Aber je nachdem, wie das in den Anwendungskontext integriert sein soll, muss man sich da ggf. andere Optionen offen halten

    7. Thread-safety: Abgesehen davon, dass bestimmte Operationen parallel ausgeführt werden, wird wohl praktisch KEINE Library "thread safe" sein, in dem Sinne, dass um jeden furz-Setter ein dickes synchronized gewickelt wird. Das hat einfach mit den "üblichen" Anwendungsszenarien so einer Library nichts zu tun, bzw. würde ggf. "von außen" sichergestellt werden müssen.

    ---

    Allgemein ist die Spanne und der Raum der Optionen bei solchen Libraries SO gigantisch und SO abhängig vom jeweiligen Anwendungsfall, dass es sicher kein "Silver Bullet" gibt. Bei einigen meiner Recherchen fand ich eine Sache bezeichnend - nämlich die gigantische Spanne zwischen
    • Der Klasse Matrix aus JAMA: "public class Matrix", praktisch ein gewrappter 2D-double-Array
    • Der nächsten Entsprechung dieser Klasse in UJMP: DefaultDenseDoubleMatrix2D, die von 7 Klassen erbt, und 77 (siebenundsiebzig!) interfaces implementiert


    Das https://ujmp.org/ ist, wie man sich schon anhand dessen denken kann, engineered bis zum Anschlag - und, wie der Name schon suggeriert, zielt es auf Universalität ab. Das interessanteste daran fand ich, dass es die Möglichkeit bietet, über einen Plugin-Mechanismus Matrizen aus fast jeder anderen Matrix-Library transparent zu integrieren. ("fast" jeder - überraschenderweise scheint "jeigen" gerade NICHT dabei zu sein ). Es bietet wohl auch ein Plugin für die Visualisierung, wie auch im Hintergrundbild der Homepage zu sehen ist. Aber wirklich "aktiv" damit gearbeitet habe ich noch nicht, deswegen soll das keine Emfehlung für die Library selbst sein, sondern nur die Empfehlung, da mal ein Auge drauf zu werfen.

    (Aber nur nebenbei: Selbst diese Library bietet anscheinend nicht die Möglichkeit, Zeilen/Spalten zu einer Matrix hinzuzufügen. Das ist einfach zu unüblich. Die Option, sich dafür eine eigene Datenstruktur zu basteln, und um diese Struktur dann ein passendes Interface zu wickeln, sollte es aber bei allen Libraries geben, die "die zentrale 'Matrix'" nicht als Klasse, sondern als Interface definiert haben)

  3. #3
    User short Themenstarter

    Registriert seit
    20.12.2015
    Fachbeiträge
    20
    Genannt
    0 Post(s)
    Ich danke dir für die ausführliche Info. UJMP schaut sehr interessant aus, fast noch besser als jeigen. Leider unterstützt es aber keine dynamischen Matrizen. Siehst du einen Weg wie man effizient eine Kolonne (oder Zeile) einer bestehenden Matrix hinzufügen könnte (ohne jeweils eine neue Matrix zu kreieren)?

  4. #4
    Global Moderator Viertel Gigabyte
    Registriert seit
    05.08.2008
    Fachbeiträge
    4.905
    Genannt
    309 Post(s)
    Unterstützt jeigen sowas? Sah erstmal nicht so aus, abgesehen von Konkatenation von Matrizen. Wie gesagt, das ist eine sehr "unübliche" Operation. Wenn man sie unterstützen würde, würde das viele Fragen aufwerfen. (Z.B: Man holt sich eine Zeile von einer Matrix, fügt dann in die Matrix eine Spalte ein - erscheint die Spalte (als neuer Eintrag) in der vorher abgeholten Zeile? etc). Die Frage, WER denn WANN genau WAS von dem Einfügen mitkriegen soll, ist recht vertrackt. Das so flexibel zu machen, und gleichzeitig sowohl die "normalen" Operationen als auch das Einfügen effizient hinzukriegen ist kompliziert. Gibt's da irgendwelche Prioritäten?

  5. #5
    User short Themenstarter

    Registriert seit
    20.12.2015
    Fachbeiträge
    20
    Genannt
    0 Post(s)
    Nein, so weit ich weiss unterstützt jeigen das auch nicht. Wenn ich eine Kolonne anhänge, könnte ich natürlich einfach eine neue Matrix generieren, ist halt einfach nicht so effizient. Oder ich könnte zuerst alles in 2D arrays speichern und dannach die Matrix erzeugen, allerdings sind 2D arrays ja auch fix.

  6. #6
    Global Moderator Viertel Gigabyte
    Registriert seit
    05.08.2008
    Fachbeiträge
    4.905
    Genannt
    309 Post(s)
    Zitat Zitat von BlackHawk Beitrag anzeigen
    Wenn ich eine Kolonne anhänge, könnte ich natürlich einfach eine neue Matrix generieren, ist halt einfach nicht so effizient.
    Deswegen hatte ich nach den Prioritäten gefragt. Vordergründig: Welche Operation wird "öfter" ausgeführt? Wenn man die Matrix mit
    Java Code:
    1.  
    2. Matrix m = matrixWith10000Rows();
    3. for (int c=0; c<10000; c++)
    4. {
    5.     m.addColumnMaybeEvenAtSomeSpecialIndex(someIndex[c]);
    6. }
    aufbauen will, wäre diese Operation sicher zeitkritisch(er), als wenn das nur ein selten auftretender Schritt nach einer langen Folge von anderen zeitkritischen Dingen (GEMM etc) ist. Verschiedene trade-offs und Zwischenlösungen wären denkbar: Mit einer bestimmten (flexiblen) Matrix-Struktur das Aufbauen erledigen, und das dann in eine (statische) Matrix kopieren, mit der die anderen Operationen schnell durchgeführt werden können. Den Trade-Off zwischen "LinkedList mit schnellen Einfügen an beliebiger Stelle" vs. "ArrayList mit schnellem indizierten Zugriff, aber langsamem Einfügen vorne" kennt man ja, und kann man so gesehen auf 2D übertragen...

  7. #7
    User short Themenstarter

    Registriert seit
    20.12.2015
    Fachbeiträge
    20
    Genannt
    0 Post(s)
    Also die Matrix sollte Kolonne für Kolonne aufgebaut werden, allerdings nur ca. 100 Kolonen. Was für eine flexible Matri-Struktur schwebt dir vor? Eine 2D ArrayList wäre ne Möglichkeit, da ich ja eigentlich nur appenden muss.

  8. #8
    Global Moderator Viertel Gigabyte
    Registriert seit
    05.08.2008
    Fachbeiträge
    4.905
    Genannt
    309 Post(s)
    Schon die Anforderung, nur appenden zu müssen, ist etwas, was das ganze VIEL einfacher macht - und (bzw. speziell) auch VIEL einfacher eine effiziente Implementierung ermöglicht.

    Jetzt wäre noch gut, zu wissen, ob NUR (!) Spalten angefügt werden müssen, oder irgendwann auch mal Zeilen (oder ob die Zeilenzahl von vornherein bekannt ist und immer gleich bleibt)

  9. #9
    User short Themenstarter

    Registriert seit
    20.12.2015
    Fachbeiträge
    20
    Genannt
    0 Post(s)
    Es müssen NUR Zeilen eingefügt werden (war vorhin falsch mit den Spalten). Die Spaltenzahl ist vorher bekannt.

  10. #10
    Global Moderator Viertel Gigabyte
    Registriert seit
    05.08.2008
    Fachbeiträge
    4.905
    Genannt
    309 Post(s)
    Dann könnte man, je nachdem, welche Library genau verwendet wird, im besten Fall einfach sowas machen wie
    Java Code:
    1.  
    2. class DynamicRowsMatrix extends TheBestMatchingAbstractBaseClass implements WhateverMatrixInterface
    3. {
    4.     private final int numColumns;
    5.     private final List<double[]> rows;
    6.  
    7.     DynamicRowsMatrix(int numColumns)
    8.     {
    9.         this.numColumns = numColumns;
    10.         this.rows = new ArrayList<double[]>();
    11.     }
    12.  
    13.     void addRow()
    14.     {
    15.         rows.add(new double[numColumns]);
    16.     }
    17.  
    18.     // Implementation of the interface (i.e. the abstract methods from the base class)
    19.     @Override
    20.     public int getNumRows() { return rows.size(); }
    21.     public int getNumCols() { return numColumns; }
    22.     public void set(int r, int c, double value) { rows.get(r)[c] = value; }
    23.     public double get(int r, int c) { return rows.get(r)[c]; }
    24.     ...
    25. }

    Sowas wie "eine View auf eine Spalte zurückgeben" sollte nach Möglichkeit ja schon in der abstrakten Basisklasse stecken. Praktisch könn(t)en ALLE (!) Funktionalitäten auf der Matrix durch die angedeuteten 4 Funktionen umgesetzt werden, d.h. viel mehr sollte in einer passenden Basisklasse nicht mehr abstrakt sein.




    }

  11. #11
    User short Themenstarter

    Registriert seit
    20.12.2015
    Fachbeiträge
    20
    Genannt
    0 Post(s)
    Vielen Dank. Damit sollte das Problem gelöst sein.

  12. #12
    User Megabyte Avatar von mymaksimus
    Registriert seit
    17.08.2013
    Fachbeiträge
    1.270
    Genannt
    50 Post(s)
    Off topic:
    darf man fragen, wieso genau du soetwas wie "zeilen / spalten einfügen" brauchst?
    "und außerdem, so lange her, dafür gibts keine teile mehr.."

+ Antworten Thema als "offen" markieren

Direkt antworten Direkt antworten

Nenne das erste Element im Periodensystem der Elemente?

Aktive Benutzer

Aktive Benutzer

Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)

Ähnliche Themen

  1. Schnelle Cholesky-Zerlegung dünnbesetzter Matrizen
    Von eitelkalk im Forum Allgemeine Themen
    Antworten: 8
    Letzter Beitrag: 24.04.2015, 20:09
  2. Noch einmal Matrizen
    Von mymaksimus im Forum Spiele- und Multimedia-Programmierung
    Antworten: 15
    Letzter Beitrag: 19.10.2014, 01:56
  3. Rotations- und sonstige Matrizen
    Von mymaksimus im Forum Allgemeine Themen
    Antworten: 180
    Letzter Beitrag: 19.11.2013, 14:59
  4. Matrizen - perspektivische Projektion?
    Von mymaksimus im Forum Theoretisches
    Antworten: 12
    Letzter Beitrag: 06.11.2013, 11:58
  5. LWJGL - Matrizen (OpenGL 3+)
    Von Oneric im Forum Spiele- und Multimedia-Programmierung
    Antworten: 6
    Letzter Beitrag: 18.10.2013, 14:32

Berechtigungen

  • Neue Themen erstellen: Ja
  • Themen beantworten: Ja
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •