Produkt von zwei Toeplitz Matrizen?

Der O(n log n) Algorithmus für das Produkt einer Toeplitz-Matrix und eines Vektors der richtigen Länge ist allgemein bekannt: lege ihn in eine zirkulante Matrix, multipliziere ihn mit dem Vektor (und nachfolgenden Nullen) und gib die obersten n Elemente zurück Produkt.Produkt von zwei Toeplitz Matrizen?

Ich finde Probleme, den besten (zeitlichen) Algorithmus für die Multiplikation von zwei Toeplitz-Matrizen der gleichen Größe zu finden.

Kann mir jemand einen Algorithmus dafür geben?

Quelle

2013-04-08 Govind Parmar

Das Produkt von Toeplitz-Matrizen ist nicht unbedingt Toeplitz. Wie soll die Ausgabe dargestellt werden? –

Als eine nxn-Matrix, da es keine andere Darstellung gibt, die in diesem Fall alle relevanten Daten anzeigen würde. Ich frage nicht nach einem Algorithmus, der schneller läuft als 'O (n^2)', ich frage mich nur, ob es in diesem Fall einen schnelleren Algorithmus gibt als die Standard-Matrix-Multiplikation. –

Es gibt einen O (n^2 log n) -Algorithmus, der n Matrix-Vektor-Multiplikationen durchführt. Es würde mich nicht wundern, wenn es einen O (n^2) -Algorithmus gäbe, aber ich kann nicht sagen, dass ich daran interessiert bin, es zu finden. –

Hier ist ein O (n^2) -Zeitalgorithmus.

Um eine der Diagonalen der Produktmatrix zu berechnen, müssen wir Punktprodukte über Länge-n Fenster von Längen- (2n-1) Listen berechnen, die im Gleichschritt gleiten. Der Unterschied zwischen zwei aufeinanderfolgenden Einträgen kann in der Zeit O (1) berechnet werden.

Betrachten wir zum Beispiel das Produkt von

e f g h i o p q r s 
d e f g h m o p q r 
c d e f g l m o p q 
b c d e f k l m o p 
a b c d e j k l m o

Der 1,1-Eintrag eo + fm + gl + hk + ij ist. Der 2,2-Eintrag ist dp + eo + fm + gl + hk oder der 1,1-Eintrag minus ij plus dp. Der 3,3-Eintrag ist cq + dp + eo + fm + gl oder der 2,2-Eintrag minus hk plus cq. Der 4,4-Eintrag lautet br + cq + dp + eo + fm usw.

Wenn Sie dies in Gleitkomma implementieren, beachten Sie catastrophic cancellation.

Quelle

2013-04-09 02:52:39

Antwort

Verwandte Themen