Library für Matrizen


#1

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:

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

Hat da jemand schon Erfahrungen und kann eine empfehlen?


#2

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)
[ul]
[li]Very memory consuming (can only handle Matrices up to 13x17)[/li]> [li]Does not offer any matrix operations at all (yeah, NONE of them!)[/li]> [li]Very slow! (The latest version is 34% slower than the previous one!)[/li]> [/ul]

(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 [inline]synchronized[/inline] 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
[ul]
[li]Der Klasse Matrix aus JAMA: “public class Matrix”, praktisch ein gewrappter 2D-double-Array[/li][li]Der nächsten Entsprechung dieser Klasse in UJMP: DefaultDenseDoubleMatrix2D, die von 7 Klassen erbt, und 77 (siebenundsiebzig!) interfaces implementiert[/li][/ul]

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 :confused: ). 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

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 [B]effizient[/B] eine Kolonne (oder Zeile) einer bestehenden Matrix hinzufügen könnte (ohne jeweils eine neue Matrix zu kreieren)?


#4

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

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

[QUOTE=BlackHawk;129320]Wenn ich eine Kolonne anhänge, könnte ich natürlich einfach eine neue Matrix generieren, ist halt einfach nicht so effizient.[/QUOTE]

Deswegen hatte ich nach den Prioritäten gefragt. Vordergründig: Welche Operation wird “öfter” ausgeführt? Wenn man die Matrix mit

Matrix m = matrixWith10000Rows();
for (int c=0; c<10000; c++)
{
    m.addColumnMaybeEvenAtSomeSpecialIndex(someIndex```);
}

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

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

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

Es müssen NUR Zeilen eingefügt werden (war vorhin falsch mit den Spalten). Die Spaltenzahl ist vorher bekannt.


#10

Dann könnte man, je nachdem, welche Library genau verwendet wird, im besten Fall einfach sowas machen wie

class DynamicRowsMatrix extends TheBestMatchingAbstractBaseClass implements WhateverMatrixInterface
{
    private final int numColumns;
    private final List<double[]> rows;

    DynamicRowsMatrix(int numColumns) 
    {
        this.numColumns = numColumns;
        this.rows = new ArrayList<double[]>();
    }

    void addRow()
    {
        rows.add(new double[numColumns]);
    }

    // Implementation of the interface (i.e. the abstract methods from the base class)
    @Override
    public int getNumRows() { return rows.size(); }
    public int getNumCols() { return numColumns; }
    public void set(int r, int c, double value) { rows.get(r)``` = value; }
    public double get(int r, int c) { return rows.get(r)```; }
    ...
}

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

Vielen Dank. Damit sollte das Problem gelöst sein.


#12

[OT]darf man fragen, wieso genau du soetwas wie “zeilen / spalten einfügen” brauchst?[/OT]