Prodotto di due matrici di Toeplitz?

L'algoritmo O(n log n) per il prodotto di una matrice Toeplitz e un vettore della lunghezza corretta è ben noto: inserirlo in una matrice di circulante, moltiplicarlo per il vettore (e gli zeri successivi) e restituire i primi n elementi del Prodotto.Prodotto di due matrici di Toeplitz?

Sto riscontrando problemi nel trovare il migliore algoritmo (in termini di tempo) per moltiplicare due matrici di Toeplitz della stessa dimensione.

Qualcuno può darmi un algoritmo per questo?

fonte

2013-04-08 Govind Parmar

Il prodotto delle matrici di Toeplitz non è necessariamente Toeplitz. Come viene rappresentato l'output? –

Come una matrice nxn, visto che non ci sono altre rappresentazioni che mostrerebbero tutti i dati rilevanti in questo caso. Non sto chiedendo un algoritmo che funzioni più velocemente di 'O (n^2)', mi sto semplicemente chiedendo se c'è un algoritmo più veloce della routine di moltiplicazione della matrice standard in questo caso. –

C'è un algoritmo O (n^2 log n) che fa n moltiplicazioni a matrice vettoriale. Non mi sorprenderebbe se esistesse un algoritmo O (n^2), ma non posso dire di essere desideroso di trovarlo. –

Ecco un algoritmo di tempo O (n^2).

Per calcolare una delle diagonali della matrice del prodotto, è necessario calcolare i prodotti punto su liste di lunghezza-n di lunghezza- (2n-1) che scorrono a serraggio. La differenza tra due voci successive può essere calcolata nel tempo O (1).

Si consideri ad esempio il prodotto di

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

L'entrata è 1,1 eo + fm + gl + hk + ij. La voce 2,2 è dp + eo + fm + gl + hk o la voce 1,1 meno ij più dp. La voce 3,3 è cq + dp + eo + fm + gl o la voce 2,2 meno hk più cq. La voce 4,4 è br + cq + dp + eo + fm, ecc.

Se si implementa questo in virgola mobile, prestare attenzione a catastrophic cancellation.

fonte

2013-04-09 02:52:39

Prodotto di due matrici di Toeplitz?

risposta

Problemi correlati