Algorytm dla iloczynu macierzy Toeplitza i wektora o prawidłowej długości jest dobrze znany: umieść go w macierzy cyrkulacyjnej, pomnóż przez wektor (i kolejne zera) i zwróć górne elementy n produkt.Produkt dwóch matryc typu Toeplitz?
Mam problem ze znalezieniem najlepszego (czasowego) algorytmu do pomnożenia dwóch macierzy Toeplitz o tym samym rozmiarze.
Czy ktoś może mi podać algorytm do tego?
Oto algorytm O (n^2) -time.
Aby obliczyć jeden z przekątnych macierzy produktu, musimy obliczyć produkty dot przez długie-n okien długości (2n-1) list, które są przesuwane w lockstep. Różnicę między dwoma kolejnymi wpisami można obliczyć w czasie O (1).
Na przykład, należy rozważyć produkt
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
pozycja 1,1 jest eo + fm + gl + hk + ij. Wpis 2,2 jest dp + eo + fm + gl + hk lub wpis 1,1 minus ij plus dp. Pozycja 3,3 to cq + dp + eo + fm + gl lub pozycja 2,2 minus hk plus cq. Wpis 4,4 to br + cq + dp + eo + fm, itp.
Jeśli zaimplementujesz to w postaci zmiennoprzecinkowej, pamiętaj o catastrophic cancellation.
Produkt z matryc Toeplitza niekoniecznie jest Toeplitz. W jaki sposób dane wyjściowe mają być reprezentowane? –
Jako macierz nxn, ponieważ nie ma innej reprezentacji, która wyświetliłaby wszystkie odpowiednie dane w tym przypadku. Nie pytam o algorytm, który działa szybciej niż 'O (n^2)', zastanawiam się tylko, czy w tym przypadku istnieje szybszy algorytm niż standardowa procedura mnożenia macierzy. –
Istnieje algorytm O (n^2 log n), który wykonuje multiplikacje wektorów macierzowych. Nie zdziwiłbym się, gdyby istniał algorytm O (n^2), ale nie mogę powiedzieć, że chętnie go znajdę. –