Matrixmultiplikation A^T*A

05/09/2007 - 08:53 von Rico Poser | Report spam
Hallo,

ich habe folgende Problemstellung:

Gegeben ist eine unregelmàßig dünn besetzte Matrix A (n x m). Làsst
sich, und wenn ja wie, anhand der besetzten Positionen in A eine Aussage
machen an welchen Positionen das Matrixprodukt A^T * A besetzt ist?

Vielen Dank im Voraus.

Rico
 

Lesen sie die antworten

#1 Robert Hartmann
05/09/2007 - 11:15 | Warnen spam
Hallo,

Rico Poser schrieb:
Gegeben ist eine unregelmàßig dünn besetzte Matrix A (n x m). Làsst
sich, und wenn ja wie, anhand der besetzten Positionen in A eine
Aussage machen an welchen Positionen das Matrixprodukt A^T * A
besetzt ist?



Dir geht es dabei tatsàchlich nur um die binàre Aussage "Stelle (i,j)
der Ergebnismatrix ist besetzt" und du brauchst das Ergebnis danach
nicht wirklich?

Nur als Idee:
Konvertiere deine Matrix A in eine 0-1 Matrix B, also 1 für Stelle ist
besetzt und 0 für Stelle ist frei. Dann kannst du jeden Eintrag in B
mit den Wahrheitswerten wahr für 1, falsch für 0 identifizieren.
Jetzt wird die Multiplikation der Elemente zu einem logischen Und,
die Addition zu einem logischen Oder.
(Das Rechnungsschema bliebt "Zeile mal Spalte" und "Punkt- vor
Strichrechnung" bleibt ebenso weiter gültig.)

Die Ergebnismatrix E = B^T * B ist wieder eine 0-1 Matrix,
die genau angibt an welcher Stelle Eintràge sind und an
welchen nicht.

Ich fürchte allerdings, dass du so etwas nicht möchtest, denn
die Zeitkomplexitàt ist im wesentlichen weiterhin O(max(n,m)^3).

Aber bei der Speicherkomplexitàt sollte sich etwas veràndern,
denn 0-1 Werte brauchen prinzipiell nur 1 bit bei einer sinnvollen,
einer speicherplatzsparenden Datenstruktur. Wenn du alle drei Matrizen
behalten möchtest, dann benötigst du 3*n*m bit bei sinnvoller
Datenstruktur.

Besten Gruß,
Robert

Ähnliche fragen