Verstehe das Problem nicht. Luxusproblem ?

[G-Punkt]

Vielleicht habe ich mich noch zu wenig mit dem Problem beschäftigt.

Eine Matrix besteht nunmal aus u=n^2 Einträgen. Wenn man die Multiplikation in O(n^2)=O(u) haben will, dann ist das lineare Zeit. Wenn man eine Liste sortiert geht dies in O(n*log n).

Die naive Matrixmultiplikation wird in O(n^3) erledigt, also in O(u^1.5), was auch nicht schlecht ist.

Habe es nie analysiert wie das bei speziellen dünnbesetzten Matrizen ist (Diagonalmatrix ist einfach).

Ich sehe das Ganze nicht als Weltproblem in der Kategorie von P-NP. Ist es nur ein Jammern auf hohem Niveau?

[korona]

Es geht um Leistungsgewinn. Matrixmultiplikationen werden oft und viel eingesetzt. Das Verfahren kann bisherigen Code "gratis" schneller machen. Gerade bei sehr großen Matrizen mit Tausenden oder Millionen Einträgen kann das schon mal einiges an Zeitersparnis mit sich bringen

[Schattenwerk]

G-Punkt schrieb:
--------------------------------------------------------------------------------
> Ich sehe das Ganze nicht als Weltproblem in der Kategorie von P-NP. Ist es
> nur ein Jammern auf hohem Niveau?

Mit der Argumentation könntest du heute auch noch auf einem 100 MHz Pentium arbeiten.

Der Grundkonzept von Optimierung ist, dass eine begrenzte Ressource effizient eingesetzt wird. Liegt dem Menschen aber nicht immer, wie man bei unserer Erde sieht ;)

[G-Punkt]

Das ist mir schon klar.

Aber man ist nicht bei O(2^n) oder O(n^6).

Und spezielle Matrizen kann man auch speziell multiplizieren. Oder das dahinterstehende Problem insgesamt besser lösen.

[G-Punkt]

???

[AvailableLight]

G-Punkt schrieb:
--------------------------------------------------------------------------------
> Ich sehe das Ganze nicht als Weltproblem in der Kategorie von P-NP. Ist es
> nur ein Jammern auf hohem Niveau?

Beim Maschinellen Lernen bieten derlei winzige Optimierungen Einsparpotenziale bei Zeit und Hardwarekosten. Viele große Netze werden monatelang trainiert, da können Nachkommastellen im Exponenten Machbarkeit, Preis und Geschwindigkeit maßgeblich beeinflussen. Also definitiv kein Luxusproblem.

[Schattenwerk]

Subjekt, Prädikat, Objekt, dann wird auch ein Satz draus.

[minnime]

Wo ist denn bitteschön n² linear? Das ist polynominell wenn auch nicht gleich exponentiell. Aber selbst wenn das linear lohnt sich eine Optimierung.

[Thargon]

Worum geht es denn bei Optimierung? Grundsätzlich gibt es zwei Arten von Problemen: Die, die mit gegebenen Ressourcen (Zeit, Speicher, etc.) berechenbar sind, und die die es eben nicht sind. Natürlich sind die beiden Mengen für jemanden der Zugriff auf einen HPC hat anders als bei einer SmartWatch, aber letztendlich ist es immer das gleiche. Außerdem liegen Probleme a la O(2^n) schon bei vergleichsweise kleinen n auf der nicht berechenbaren Seite, während Probleme a la O(log(n)) wesentlich länger berechenbar bleiben.

Optimierungen - egal ob in der Rechenhardware dem Berechnungsverfahren oder der Repräsentation (z.B. FP16) - dienen dazu, diese Grenze zu verschieben, sodass wir größere Probleme berechnen können. Insofern ist jede noch so kleine Optimierung sinnvoll. Und wenn diese drei Forscher innerhalb von 1k Arbeitsstunden eine Optimierung entwickeln konnten, die global betrachtet potentiell schon in einigen Tagen mehrere Millionen Stunden CPU-Zeit einsparen kann (ja, die Zahlen habe ich mir gerade ausgedacht), dann war das gut investierte Brain-Zeit.

[G-Punkt]

Wie ich geschrieben habe: Die Eingabegrösse einer dichtbesetzten ist n^2, wenn n die Anzahl der Variablen ist.

[G-Punkt]

Das schon. Aber kennst du dich SPEZIFISCH mit der Multiplikation von 2 Matrizen aus? Es gibt https://de.wikipedia.org/wiki/Matrizenmultiplikation.

[MarkusXXX]

G-Punkt schrieb:
--------------------------------------------------------------------------------

> Ich sehe das Ganze nicht als Weltproblem in der Kategorie von P-NP. Ist es
> nur ein Jammern auf hohem Niveau?

Das Training von ChatGPT-3 hat 5 Millionen Dollar gekostet. Das entspricht 355 Jahre auf einer Tesla V100 GPU. Da lohnen sich alternative Ansätze schon.