An unified approach for developing rationalized algorithms for hypercomplex number multiplication

• Autorzy: Cariow A. , Cariowa G.

Warianty tytułu

PL

Uogólnione podejście do konstruowania zracjonalizowanych algorytmów mnożenia liczb hiperzespolonych

• Języki publikacji: EN

Abstrakty

EN

In this article we present a common approach for the development of algorithms for calculating products of hypercomplex numbers. The main idea of the proposed approach is based on the representation of hypernumbers multiplying via the matrix-vector products and further creative decomposition of the matrix, leading to the reduction of arithmetical complexity of calculations. The proposed approach allows the construction of sufficiently well algorithms for hypernumbers multiplication with reduced computational complexity. If the schoolbook method requires N2 real multiplications and N(N-1) real additions, the proposed approach allows to develop algorithms, which take only [N(N-1)/2]+2 real multiplications and 3Nlog2N+[N(N-3)+4]/2 real additions.

PL

W artykule zostało przedstawione uogólnione podejście do syntezy algorytmów wyznaczania iloczynów liczb hiperzespolonych. Główna idea proponowanego podejścia polega na reprezentacji operacji mnożenia liczb hiperzespolonych w formie iloczynu wektorowomacierzowego i dalszej możliwości kreatywnej dekompozycji czynnika macierzowego prowadzącej do redukcji złożoności obliczeniowej. Proponowane podejście pozwala zbudować algorytmy wyróżniające się w porównaniu do metody naiwnej zredukowaną złożonością obliczeniową. Jeśli metoda naiwna wymaga wykonania N2 mnożeń oraz N(N-1) dodawań liczb rzeczywistych to proponowane podejście pozwala syntetyzować algorytmy wymagające tylko [N(N-1)/2]+2 mnożeń oraz 3Nlog2N+[N(N-3)+4]/2 dodawań.

Słowa kluczowe

EN

hypernumber; multiplication; fast algorithm

PL

liczba hiperzespolona; mnożenie; szybki algorytm

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2015
• Tom: R. 91, nr 2
• Strony: 36--39
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Cariow A.

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

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] Kantor, I.L. and Solodovnikov A.S. Hypercomplex numbers. An elementary introduction to algebras. Springer: New York, (1989).
• [2] Chanyal B.C., Bisht P.S. and Negi O.P.S., Generalized Octonion Electrodynamics, Int. J. Theor. Phys., 49(6), (2010), 1333-1343.
• [3] Alfsmann D., Göckler H.G., Sangwine S.J. and Ell T.A. Hypercomplex Algebras in Digital Signal Processing: Benefits and Drawbacks (Tutorial). Proc. EURASIP 15th European Signal Processing Conference (EUSIPCO 2007), Poznań, Poland, (2007), 1322-1326.
• [4] Snopek K.M. The Study of Properties of n-D Analytic Signals in Complex and Hypercomplex Domains, Radioengineering, (2012), vol. 21, No. 2, 29-36.
• [5] Bihan, N.L., Sangwine, S.J. Quaternion principal component analysis of color images. In: IEEE International Conference on Image Processing (ICIP 2003). v.1., Barcelona, Spain, (2003). 809–812.
• [6] Moxey C.E., Sangwine S.J., Ell T.A., Hypercomplex correlation techniques for vector images, IEEE Trans. Signal Process., 2003. 51, 1941-1953
• [7] Wang Hui ; Wang Xiao-Hui ; Zhou Yue; Yang Jie Color Texture Segmentation Using Quaternion-Gabor Filters, Transaction on Image Processing, 2006 IEEE International Conference 8-11 Oct. (2006), 745 – 748.
• [8] Calderbank R., Das S., Al Dhahir N. , Diggavi S., Construction And Analysis of A New Quaternionic Space-Time Code For 4 Transmit Antennas, Commun. Inf. Syst., (2005), 5, 97-122.
• [9] Malekian E., Zakerolhosseini A., Mashatan A., QTRU: Quaternionic Version of the NTRU Public-Key Cryptosystems, Int. J. Inf. Secur., 3, 29-42, 2011
• [10] Makarov O.M. An algorithm for the multiplication of two quaternions, Zh. Vychisl. Mat. Mat. Fiz. 17(6) (1977) 1574–1575 (in Russian).
• [11] Dimitrov V.S., Cooklev T.,V., Donevsky B.D., On the multiplication of reduced biquaternions and applications, Inform. Process. Lett. 43 (3) (1992) 161–164.
• [12] Ţariov А., Algorytmiczne aspekty racjonalizacji obliczeń w cyfrowym przetwarzaniu sygnałów, Wydawnictwo Uczelniane ZUT, (2011).
• [13] Steeb W.-H., Hardy Y., Matrix Calculus and Kronecker Product: A Practical Approach to Linear and Multilinear Algebra, World Scientific Publishing Company; 2 edition (2011).
• [14] Ţariov A., Strategie racjonalizacji obliczeń przy wyznaczaniu iloczynów macierzowo-wektorowych. Metody Informatyki Stosowanej, n 1, (2008), 147- 158.
• [15] Ţariova G., Ţariov A., Aspekty algorytmiczne redukcji liczby bloków mnożących w układzie do obliczania iloczynu dwóch kwaternionów, Pomiary, Automatyka, Kontrola, n 7, (2010), 668-690.
• [16] Ţariov A., Ţariova G., Aspekty algorytmiczne organizacji układu procesorowego do mnożenia liczb Cayleya. Elektronika- Konstrukcje, Technologie, Zastosowania, n 11, (2010), 137-140
• [17] Cariow A., Cariowa G., An algorithm for fast multiplication of sedenions, Information Processing Letters, 113 (2013). 324–331.
• [18] Cariow A., Cariowa G., An algorithm for multiplication of Dirac numbers, Journal of Theoretical and Applied Computer Science, (2013), vol. 7, no. 4, 26-34.
• [19] Cariow A., Cariowa G., An algorithm for fast multiplication of Pauli numbers, Advances in Applied Clifford Algebras, (2014). This article is Publisher with open access at Springerlink.com DOI 10.1007/s00006-014-0466-0.