An algorithm for multiplication of trigintaduonions

• Autorzy: Cariow A. , Cariowa G.
• Języki publikacji: EN

Abstrakty

EN

In this paper we introduce efficient algorithm for the multiplication of trigintaduonions. The direct multiplication of two trigintaduonions requires 1024 real multiplications and 992 real additions. We show how to compute a trigintaduonion product with 498 real multiplications and 943 real additions. During synthesis of the discussed algorithm we use a fact that trigintaduonion multiplication may be represented by a vector-matrix product. Such representation provides a possibility to discover repeating elements in the matrix structure and to use specific properties of their mutual placement to decrease the number of real multiplications needed to compute the product of two trigintaduonions.

Słowa kluczowe

EN

trigintaduonion; multiplication of trigintaduonions; fast algorithm; matrix notation

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Journal of Theoretical and Applied Computer Science
• Rocznik: 2014
• Tom: Vol. 8, nr 1
• Strony: 50--75
• Opis fizyczny: Bibliogr. 49 poz., rys.

Twórcy

autor

Cariow A.

• Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Szczecin, Poland

autor

Cariowa G.

• Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Szczecin, Poland

Bibliografia

• [1] R. Abłamowicz (ed.), Clifford Algebras – Applications to Mathematics, Physics, and Engineering, PIM 34, Birkhauser, Basel 2004.
• [2] D. Alfsmann, H. G. Göckler, S. J. Sangwine, and T. A. Ell. Hypercomplex Algebras in Digital Signal Processing: Benefits and Drawbacks (Tutorial). Proc. EURASIP 15th European Signal Processing Conference (EUSIPCO 2007), Poznań, Poland, (2007), pp. 1322–1326.
• [3] E. Bayro-Corrochano. Multi-resolution image analysis using the quaternion wavelet transform, Numerical Algorithms, vol. 39, No 1–3, (2005), pp. 35–55.
• [4] N. Le Bihan and J. Mars. Singular value decomposition of quaternion matrices: A new tool for vector-sensor signal processing, Signal Process., vol. 84, no. 7, (2004), pp. 1177–1199.
• [5] N. L. Bihan, S. J. Sangwine. Quaternion principal component analysis of color images. In: IEEE International Conference on Image Processing (ICIP 2003), vol. 1, Barcelona (Spain), (2003), pp. 809–812.
• [6] S. Buchholz and N. Le Bihan. Polarized signal classification by complex and quaternionic multi-layer perceptrons, Int. J. Neural Syst., vol. 18, no. 2, (2008), pp. 75–85.
• [7] T. B¨ulow and G. Sommer. Hypercomplex signals – a novel extension of the analytic signal to the multidimensional case, IEEE Trans. Sign. Proc., vol. SP–49, no. 11, (2001), pp. 2844–2852.
• [8] R. Calderbank, S. Das, N. Al-Dhahir and S. Diggavi. Construction And Analysis Of A New Quaternionic Space-Time Code For 4 Transmit Antennas, Communications In Information And Systems, vol. 5, No. 1, (2005), pp. 97–122.
• [9] A. Cariow, G. Cariowa, Algorithm for multiplying two octonions, Radioelectronics and Communications Systems (Allerton Press, Inc. USA), vol. 55, No 10, (2012), pp. 464–473.
• [10] G. Cariowa, A. Cariow. Representation of sedenions multiplication via matrix-vector product, Metody Informatyki Stosowanej, No 1, (2011), pp. 133–139.
• [11] A. Cariow, G. Cariowa. An algorithm for fast multiplication of sedenions, Information Processing Letters, 113, (2013), pp. 324–331.
• [12] A. Cariow., G. Cariowa. Rationalized algorithm for computing the product of two sedenions, Central European Journal of Computer Science. vol. 2, no. 4, (2012), pp. 389–397.
• [13] R. E. Cawagas, A. S. Carrascal, L. A. Bautista, J. P. Sta. Maria, J. D. Urrutia, B. Nobles., The Basic Subalgebra Structure Of The Cayley-Dickson Algebra Of Dimension 32 (Trigintaduonions), arXiv:0907.2047v3, (2009).
• [14] W. L. Chan, H. Choi, R. G. Baraniuk. Directional hypercomplex wavelets for multidimensional signal analysis and processing, Proceedings of ICASSP ’04: IEEE International Conference on Acoustics, Speech, and Signal Processing, 12–17 May, v. 3, (2004), pp. III–996–III–999.
• [15] Ensembles de nombres, Taladris, Silk78, Seirios, Telchar, Tigerfou, Médiat Forum Futura-Science (2011), 190 p.
• [16] O. Ertug, Communication over Hypercomplex Kahler Manifolds: Capacity of Dual-Polarized Multidimensional-MIMO Channels, Wireless Personal Communications, vol. 41, no 1, (2006), pp. 155–168.
• [17] Wei Feng, Bo Hu. Quaternion Discrete Cosine Transform and its Application in Color Template Matching, Proceedings of the 2008 Congress on Image and Signal Processing, vol. 2, (2008), pp. 252–256.
• [18] M. Gogberashvili, Octonionic electrodynamics, Journal of Physics A, Vol. 39, No. 22, (2006) 7099–7104.
• [19] S. L. Hahn, and K.M. Snopek. The unified theory of n-dimensional complex and hypercomplex analytic signals, Bulletin of the polish academy of sciences technical sciences, vol. 59, No. 2, (2011), pp. 167–181.
• [20] M. E. Kansu, M. Tanişli and S. Demir, Electromagnetic energy conservation with complex octonions. Turk J Phys., 36 (2012), pp. 438–445.
• [21] I. Kantor and A. Solodovnikov. Hypercomplex numbers, Springer-Verlag, New York., 1989.
• [22] L. Kavan, S. Collins, J. Žara, and C. O’Sullivan. Skinning with Dual Quaternions. Proc. of Interactive 3D Graphics and Games Symposium I3D ’07: (2007), pp. 1–23.
• [23] X. Kong. INS algorithm using quaternion model for low cost IMU, Robotics and Autonomous Systems, 46, (2004), 221–246.
• [24] I. S. Kotsireas, Ch. Koukouvinos. Orthogonal designs via computational algebra, Journal of Combinatorial Designs, v. 14, No 5, (2006), pp. 351–362.
• [25] Z. Lu, Y. Xu, Yang, X., Song, L. and Traversoni, L. 2D quaternion Fourier transform: the spectral properties and its application in color image representation, IEEE International Conference on Multimedia and Expo., (2007), pp. 1715–1718.
• [26] O. M. Makarov. An algorithm for the multiplication of two quaternions, Zh. Vychisl. Mat. Mat. Fiz., 17:6, (1997), 1574–1575.
• [27] E. Malekian, A. Zakerolhosseini, A. Mashatan. QTRU: Quaternionic Version of the NTRU Public-Key Cryptosystems, Int. J. Inf. Secur., 3, (2011), pp. 29–42.
• [28] J. L. Marins, X. Yun, E. R. Bachmann, R. B. McGhee and M. J. Zyda. An Extended Kalman Filter for Quaternion-Based Orientation Estimation Using MARG Sensors, Proceedings of the 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems, Maui, Hawaii, USA, Oct. 29 – Nov. 03, (2001), pp. 2003–2011.
• [29] C. E. Moxey, S. J. Sangwine and T.A. Ell. Hypercomplex correlation techniques for vector images, IEEE Trans. Signal Processing, vol. 51, (2003), pp. 1941–1953.
• [30] S. Pei, C. Cheng. A novel block truncation coding of color images by Rusing quaiemion-moment preserving principle. In: IEEE International Symposium on Circuits and systems, vol. 2, Atlanta (USA) (1996), 684–687
• [31] S. C. Pei, J. H. Chang, J. J. Ding. Quaternion matrix singular value decomposition and its applications for color image processing, in: IEEE Internat. Conf. on Image Processing (ICIP), vol. 1, (2003), pp. 805–808.
• [32] S. C. Pei, J. H. Chang and J. J. Ding. Commutative reduced biquaternions and their Fourier transform for signal and image processing applications, IEEE Trans. On Signal Processing, vol. 52, no. 7, (2004), pp. 2012–2031.
• [33] S. J. Sangwine. Fourier transforms of color images using quaternion or hypercomplex, numbers, in Electronics Letters, 10 Oct. 1996, vol. 32, (1996), pp. 1979–1980.
• [34] S. J. Sangwine and T.A. Ell, Hypercomplex auto- and cross-correlation of color images, in Proc. ICIP, (1999), pp. 319–323.
• [35] S. J. Sangwine, Le N. Bihan. Hypercomplex analytic signals: extension of the analytic signal concept to complex signals, Proc. EURASIP 15th European Signal Processing Conference (EUSIPCO 2007), Pozna´n, Poland, (2007), pp. 621–624.
• [36] H. D. Schtte and J. Wenzel. Hypercomplex numbers in digital signal processing, in Proc. ISCAS’ 90, New Orleans, (1990), pp. 1557–1560.
• [37] J. Seberry, Ken Finlayson, S. S. Adams, T. Wysocki, T. Xia and B. Wysocki. The theory of quaternion orthogonal designs, IEEE Trans. Signal Process., vol. 56, no. 1, (2008), pp. 256–265.
• [38] L. Shi and B. Funt. Quaternion Colour Texture Segmentation. Computer Vision and Image Understanding, 107. (2007), pp. 88–96.
• [39] W. H. Steeb, Y. Hardy. Matrix Calculus and Kronecker Product: A Practical Approach to Linear and Multilinear Algebra, World Scientific Publishing Company; 2 edition, (2011), 324 pages.
• [40] C. Took and D. Mandic. The quaternion LMS algorithm for adaptive filtering of hypercomplex processes, IEEE Trans. Signal Process., vol. 57, no. 4, (2009), pp. 1316–1327.
• [41] T. Tsui, X. Zhang, and D. Androutsos, Color image watermarking using the spatio-chromatic Fourier transform, in Proc. ICASSP, Toulouse, France, May 2006, pp. 305–308.
• [42] A. Ţariov. Algorithmic aspects of computing rationalization in digital signal processing, West Pomeranian University Press, (2011) (in Polish).
• [43] A. Ţariov, G. Ţariova. Algorithmic aspects of Cayley numbers multiplier organization, Elektronika, no 11, (2010), pp. 104–108 (in Polish).
• [44] G. Ţariova, A. Ţariov. Algorithmic aspects of multiplication blocks number reduction in two quaternion hardware multiplier, Pomiary, Automatyka, Kontrola, No 7, (2010), pp. 668–690 (in Polish).
• [45] K. Ueda and S. I. Takahashi. Digital filters with hypercomplex coefficients, in Proc. IEEE Int. Symp. Circuits Syst., May 1993, vol. 1, (1993), pp. 479–482.
• [46] G. Xu, X. Wang and X. Xu. Fractional quaternion Fourier transform, convolution and correlation, Signal Processing, vol. 88. (2008), pp. 2511–2517.
• [47] Z. H. Weng. Compounding Fields and Their Quantum Equations in the Trigintaduonion Space. arXiv: 0704.0136.
• [48] Z. H. Weng. Some helicities in electromagnetic and gravitational Fields, arXiv: 1101.2941v1, 15, Jan (2011), pp.1–51.
• [49] P. Zenczykowski. Nonrelativistic phase-space and octonions. International Journal of Theoretical Physics, Vol. 29, No. 8, (1990), pp. 835–852.