Für eine Klasse war eine Frage, die von meinem Lehrer gestellt wurde, der algorithmische Aufwand, eine Matrix mit ihrer Transponierten zu multiplizieren. Mit dem Standard-3-Schleifen-Matrixmultiplikationsalgorithmus ist die Effizienz O (N ^ 3), und ich frage mich, ob es eine Möglichkeit gab, die Matrix * -Matrixtransposition zu manipulieren oder zu nutzen, um einen schnelleren Algorithmus zu erhalten. Ich verstehe, dass wenn du eine Matrix mit ihrer Transponierten multiplizierst, du weniger der Matrix berechnen musst, weil sie symmetrisch ist, aber ich kann mir nicht vorstellen, wie man einen Algorithmus manipuliert, der weniger als O (n ^ 3) braucht.
Ich weiß, dass es Algorithmen wie Coppensmith und Straussen gibt, die schnellere allgemeine Matrixmultiplikationsalgorithmen sind, aber könnte irgendjemand irgendwelche Hinweise oder Einsichten geben, wie man die Transponierung rechnerisch ausnutzt?
Danke
Im Moment gibt es keine aymptotischen barrierebrechenden Eigenschaften dieser speziellen Multiplikation.
Die offensichtliche Optimierung besteht darin, die Symmetrie des Produkts auszunutzen. Das heißt, der Eintrag [i][j] th ist gleich dem Eintrag [j][i] th.
Für implementierungsspezifische Optimierungen gibt es eine erhebliche Menge an Caching, die Sie ausführen können. Eine sehr große Menge an Zeit bei der Multiplikation großer Matrizen wird für die Übertragung von Daten zu und von Speicher und CPU aufgewendet. So haben die CPU-Designer ein Smart-Caching-System implementiert, bei dem kürzlich genutzter Speicher in einem kleinen Speicherbereich namens Cache gespeichert wird. Außerdem haben sie es so gemacht, dass naher Speicher ebenfalls zwischengespeichert wird. Dies liegt daran, dass ein großer Teil des Speicher-IO auf das Lesen / Schreiben von Arrays zurückzuführen ist, die sequentiell gespeichert werden.
Da die Transponierte einer Matrix einfach dieselbe Matrix ist, in der die Indizes getauscht sind, kann die Zwischenspeicherung eines Wertes in der Matrix mehr als doppelt so stark sein.
Tags und Links algorithm complexity-theory linear algebra matrix-multiplication