A Fast Algorithm for Quaternion Multiplication

eng Artykuł w języku angielskim DOI: 10.14313/PAR_261/109

wyślij Janusz P. Papliński *, Aleksandr Cariow *, Marina Polyakova ** * West Pomeranian University of Technology in Szczecin, Faculty of Computer Science and Information Technology ** Odesa Polytechnic National University, Institute of Computer Systems, 1 Shevchenko Ave., Odesa, 65044, Ukraine

Pobierz Artykuł

Abstract

Quaternion algebra is used in many fields, including electrical engineering, robotics, computer graphics, navigation systems, and image and signal processing. In these applications, reducing computational complexity is particularly important, especially by limiting the number of real multiplications required to compute quaternion products. This paper proposes fast quaternion multiplication algorithms that reduce the number of real multiplications compared with the classical direct method while preserving computational correctness.

Keywords

computational complexity, fast algorithms, Hadamard matrices, quaternion multiplication, real multiplication reduction, signal processing, three-phase electrical signal

Szybki algorytm mnożenia kwaternionów

Streszczenie

Mnożenie kwaternionów znajduje zastosowanie w wielu dziedzinach, takich jak elektrotechnika, robotyka, grafika komputerowa, systemy nawigacyjne oraz przetwarzanie obrazów i sygnałów. W obszarach tych istotne znaczenie ma ograniczenie złożoności obliczeniowej algorytmów, w szczególności redukcja liczby mnożeń liczb rzeczywistych podczas obliczania iloczynów kwaternionów. W artykule zaproponowano algorytmy umożliwiające zmniejszenie liczby operacji mnożenia rzeczywistego w procesie obliczania iloczynów kwaternionów w porównaniu z klasyczną metodą bezpośrednią, przy zachowaniu poprawności i efektywności obliczeń.

Słowa kluczowe

macierze Hadamarda, mnożenie kwaternionów, przetwarzanie sygnałów, redukcja liczby mnożeń liczb rzeczywistych, szybkie algorytmy, trójfazowy sygnał elektryczny, złożoność obliczeniowa

Bibliografia

  1. Barry N., The application of quaternions in electrical circuits, 27th Irish Signals and Systems Conference (ISSC), Londonderry, UK, 2016, DOI: 10.1109/ISSC.2016.7528440.
  2. Brasil V.P., Filho A.L.F., Ishihara J.Y., Electrical three phase circuit analysis using quaternions, 18th International Conference on Harmonics and Quality of Power (ICHQP), Ljubljana, Slovenia, 2018, DOI: 10.1109/ICHQP.2018.8378813.
  3. Danielewski M., Sapa L., Foundations of the Quaternion Quantum Mechanics, “Entropy”, Vol. 22, No. 12, 2020, DOI: 10.3390/e22121424.
  4. Ahmed A., Ju H., Yang Y., Xu H., An improved unit quaternion for attitude alignment and inverse kinematic solution of the robot arm wrist, “Machines”, Vol. 11, No. 7, 2023, DOI: 10.3390/machines11070669.
  5. Bayro-Corrochano E., A survey on quaternion algebra and geometric algebra applications in engineering and computer science 1995–2020, “IEEE Access”, Vol. 9, 2021, 104326 104355, DOI: 10.1109/ACCESS.2021.3097756.
  6. Huang C., Li J., Gao G., Review of Quaternion-Based Color Image Processing Methods, “Mathematics”, Vol. 11, No. 9, 2023, DOI: 10.3390/math11092056.
  7. Miron S., Flamant J., Le Bihan N., Chainais P., Brie D., Quaternions in Signal and Image Processing: A compre hensive and objective overview, “IEEE Signal Processing Magazine”, Vol. 40, No. 6, 2023, 26–40, DOI: 10.1109/MSP.2023.3278071.
  8. Altamirano-Gomez G., Gershenson C., Quaternion Convolutional Neural Networks: Current Advances and Future Directions, “Advances in Applied Clifford Algebras”, Vol. 34, 2024, DOI: 10.1007/s00006-024-01350-x.
  9. Chen J., Ng M.K., Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss, “SIAM Journal on Imaging Sciences”, Vol. 15, No. 3, 2022, 1469–1498, DOI: 10.1137/22M1476897.
  10. BenYoussef N., Bouzid A., Color Edge Detection using Quaternion Convolution and Vector Gradient, VISIGRAPP 2017, Porto, 135–139, DOI: 10.5220/0006229601350139.
  11. Shi L., Funt B., Quaternion color texture segmentation, “Computer Vision and Image Understanding”, Vol. 107, No. 1, 2007, 88–96, DOI: 10.1016/j.cviu.2006.11.014.
  12. Zeng R., Wu J., Shao Z., Chen Y., Chen B., Senhadji L., Shu H., Color image classification via quaternion principal component analysis network, “Neurocomputing”, Vol. 216, 2016, 416–428, DOI: 10.1016/j.neucom.2016.08.006.
  13. Zhang H., Qi T., Zeng T., Quaternion-Aware Low-Rank Prior for Blind Color Image Deblurring, “Journal of Scientific Computing”, Vol. 101, 2024, DOI: 10.1007/s10915-024-02671-6.
  14. Voronin V., Semenishchev E., Zelensky A., Agaian S., Quaternion-based local and global color image enhancement algorithm, Proceedings of SPIE Defense + Security, Vol. 10993, 2019, 13–20, DOI: 10.1117/12.2519574.
  15. Wu T., Huang C., Jin Z., Jia Z., Ng M.K., Total Variation Based Pure Quaternion Dictionary Learning Method for Color Image Denoising, “International Journal of Numeri cal Analysis and Modelling”, Vol. 19, No. 5, 2022, 709–737.
  16. Komeno A.S.F., Filho A.L.F., Ishihara J.Y., Brasil V.P., Three-phase Quaternion Power in Three-wire Systems, International Conference on Renewable Energies and Power Quality (ICREPQ ’21), Almeria, 2021, Vol. 19, 493–498, DOI: 10.24084/repqj19.327.
  17. Taylor M.G., Application of quaternions to obtain analytic solutions to systems of polarization components, “Optics Communications”, Vol. 607, 2026, DOI: 10.1016/j.optcom.2026.132904.
  18. Biswas D., Ye Z., Mazomenos E.B., Jöbges M., Maharatna K., CORDIC Framework for Quaternion-based Joint Angle Computation to Classify Arm Movements, IEEE Interna tional Symposium on Circuits and Systems (ISCAS), Flor ence, 2018, DOI: 10.1109/ISCAS.2018.8350967.
  19. Parfieniuk M., Park S.Y., Versatile quaternion multipliers based on distributed arithmetic, “Circuits Systems and Signal Processing”, Vol. 37, 2018, 4880–4906, DOI: 10.1007/s00034-018-0789-5.
  20. Parfieniuk M., Park S.Y., Sparse-iteration 4D CORDIC algorithms for multiplying quaternions, “IEEE Transactions on Computers”, Vol. 65, No. 9, 2016, 2859–2871, DOI: 10.1109/TC.2015.2506572.
  21. Parfieniuk M., Petrovsky N.A., Petrovsky A.A., Rapid Prototyping of Quaternion Multiplier: From Matrix Notation to FPGA-Based Circuits, [In:] Rapid Prototyping Technology – Principles and Functional Requirements, Rijeka, 2011, 227–246, DOI: 10.5772/20939.
  22. Howell T.D., Lafon J.-C., The complexity of the quaternion product, Technical Report TR 75-245, Department of Computer Science, Cornell University, Ithaca, NY, June 1975, [https://hdl.handle.net/1813/6458].
  23. Ţ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”, Nr 7, 2010, 668–690.
  24. Cariow A., Naumowicz M., Handkiewicz A., Structure and Principles of Operation of a Quaternion VLSI Multiplier, “Applied Sciences”, Vol. 14, No. 18, 2024, DOI: 10.3390/app14188123.
  25. Kitsela V., Polyakova M., Cariow A., Fast algorithms for short-length type VI discrete cosine transform, “Electronics”, Vol. 15, No. 3, 2026, DOI: 10.3390/electronics15030699.