An algorithm for complex-valued vector-matrix multiplication

• Autorzy: Cariow A. , Cariowa G.

Warianty tytułu

PL

Zracjonalizowany algorytm wyznaczania iloczynu wektorowo-macierzowego, dla danych będących liczbami zespolonymi

• Języki publikacji: EN

Abstrakty

EN

In this note we present the algorithm for vector-matrix product calculating for vectors and matrices whose elements are complex numbers.

PL

W artykule został przedstawiony zracjonalizowany algorytm wyznaczania iloczynu wektorowo-macierzowego, dla danych będących liczbami zespolonymi. Proponowany algorytm wyróżnia się w stosunku do metody naiwnej zredukowaną złożonością multiplikatywną. Jeśli metoda naiwna wymaga wykonania 4MN mnożeń oraz 2M(2N-1) dodawań liczb rzeczywistych to proponowany algorytm wymaga tylko 3MN mnożeń oraz N+M(5N-1) dodawań.

Słowa kluczowe

EN

vector-matrix product; complex-valued data; fast algorithm

PL

iloczyn wektorowo-macierzowy; liczby zespolone; szybki algorytm

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 10b
• Strony: 213--216
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Cariow A.

autor

Cariowa G.

• Department of Computer Architectures and Telecommunications, Faculty of Computer Sciences, West Pomeranian University of Technology, Szczecin, ul. Żołnierska 51, 71-210 Szczecin,

Bibliografia

• [1] Blahut R.E., Fast algorithms for digital signal processing, Addison-Wesley Publishing company, Inc. 1985.
• [2] Pratt. W. K. Digital Image Processing (Second Edition), John Wiley & Sons, New York, 1991.
• [3] Goto, K. and van de Geijn, R. Anatomy of highperformance matrix multiplication. ACM Trans. Math. Softw. 2008, v. 34, No. 3, pp.1-25.
• [4] Valsalam V., Skjellum A., A framework for highperformance matrix multiplication based on hierarchical abstractions, algorithms and optimized low-level kernels, Concurrency and Computation Practice and Experience. 2002, v. 14, No.10, Publisher: Wiley Online Library, pp. 805-839
• [5] Varman P.J., Ramakrishnan I.V., "Synthesis of an Optimal Family of Matrix Multiplication Algorithms on Linear Arrays," IEEE Transactions on Computers, vol. 35, no. 11, pp. 989-996, Nov. 1986
• [6] Gunnels John A., Gustavson Fred G., Henry Greg M., van de Geijn Robert A., A family of highperformance matrix multiplication algorithms, Proceeding PARA'04 Proceedings of the 7th international conference on Applied Parallel Computing: state of the Art in Scientific Computing, v. 2073, No. 2, Publisher: Springer-Verlag, pp. 51-60.
• [7] Delorimier M. and Dehon A., “Floating-Point sparse matrix-vector multiply for FPGAs,” in Proc. of the IEEE Intl. Symposium on Field Programmable Gate Arrays, 2005, pp. 75-85.
• [8] Fujimoto N., “Dense matrix-vector multiplication on the CUDA architecture,” Parallel Processing Letters, 2008, vol. 18, No. 4, pp. 511-530.
• [9] Barazesh B., Michalina J., and Picco A. A VLSI signal processor with complex arithmetic capability. IEEE Transactions on Circuits and Systems, May 1988, 35(5) pp.495–505.
• [10] Fam A. T., Efficient complex matrix multiplication, IEEE Transactions on Computers, 1988, v. 37, no. 7, pp. 877-879.
• [11] Connolly, F.T., Yagle, A.E., Fast algorithms for complex matrix multiplication using surrogates, IEEE Transactions on Acoustics, Speech and Signal Processing, 1989, v. 37 no. 6, pp. 938 - 939.
• [12] Li, Guoqiang, Liu, Liren, Complex-valued matrix-vector multiplication using twos complement representation. Optics Communications, v. 105, no. 3-4, pp. 161-166.
• [13] Knuth D.E. , The Art Of Computing Programing, Volume 2, Semi-numerical Algorithms, Addison-Wesley, Reading, MA, USA, Sec-ond Ed., 1981.
• [14] Regalia P. A. and Mitra K. S., Kronecker Products, Unitary Matrices and Signal Processing Applications, SIAM Review. 1989, v. 31, no. 4, pp. 586-613.
• [15] Ţariov A., Algorithmic aspects of calculation rationalization in digital signal processing. West Pomeranian University of Technology, Szczecin, 2011 (in Polish).
• [16] Gustafsson O., Ohlsson H., and Wanhammar L., Low-complexity constant coefficient matrix multiplication using a minimum spanning tree approach, Proceedings of the 6th Nordic Signal Processing Symposium - NORSIG 2004, June 9 - 11, 2004, Espoo, Finland, pp.141-144.
• [17] Boullis, N., Tisserand, A., Some optimizations of hardware multiplication by constant matrices, IEEE Transactions on Computers, 2005, v. 54 no 10, pp. 1271 –1282.
• [18] Kinane A. , Muresan V., Towards an optimized VLSI design algorithm for the constant matrix multiplication problem. In: Proc. IEEE International Symposium on Circuits and Systems ISCAS-2006, 2006, pp. 5111 - 5114.