Fast algorithms to compute matrix-vector products for Toeplitz and Hankel matrices

摘要

W artykule zaprezentowano praktyczne i efektywne algorytmy obliczania iloczynu macierzy Toeplitza/Hankela przez wektor będące pozbawionymi rekursji modyfikacjami metody Karatsuby. W odróżnieniu od tradycyjnych algorytmów, stosowanie FFTw tym przypadku nie jest konieczne. Realizacja opracowanych algorytmów wykorzystuje niekonwencjonalny sposób doboru elementów macierzy transformacji podczas tworzenia tablicy danych do przetworzenia(nazwane odpowiednio „7-order" i „mirrored 7-order"). Podejście to pozwala na wyznaczanie iloczynów macierzowo-wektorowych równolegle przy jednoczesnej redukcji mnożarek i sumatorów.%The paper presents practical and effective algorithms to calculate the Toeplitz/Hankel matrix by a vector product that are recursiveless modification of Karatsuba's method. Unlike traditional algorithms, in this case using the FFT is not required. Realization of the developed algorithms involves the use of unconventional ways of choosing the elements of the initial transformation matrix during the formation of an array of data to be processed. We have called these methods respectively "7-order" technique and "mirrored 7-order" technique. This approach allows us to calculate the vector-matrix products in parallel way with a reduced number of hardware multipliers and adders.