Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
-->

UDC 681.322.012
L.D. Jelfimova1


1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

larisaelf@gmail.com

RECURSIVE CELLULAR METHODS OF MATRIX MULTIPLICAION

Abstract. Two recursive cellular methods for multiplying matrices of even and odd order, namely: n = 2qr  and а n = 3qr (q >1, r is the order of the cellules, n / r = m ) are proposed. These methods are based on the well-known fast cellular methods for multiplying matrices of order n = 2μr (μ >1) for μ = 2q (q >0) and n = 3μr (μ >1) for μ = 3q (q >0). New methods for multiplying cellular (m xm)-matrices operate by numerical (r xr)-cellules, variate their order, and are characterized by the lowest (compared to the well-known cellular methods) multiplicative complexity, which equal, respectively, to O (1,14m2.807) and O (1,17m2.854) cellular operations of multiplication. These methods allow obtaining cellular analogs of the well-known matrix multiplication algorithms with maximally minimized multiplicative complexity, whose estimation is illustrated by the example of the traditional matrix multiplication algorithm.

Keywords: linear algebra, family of cellular matrix multiplication methods, cellular analogs of matrix multiplication algorithms.


full text

REFERENCES

  1. Modi J.J. Parallel algorithms and matrix computation. Oxford: Clarendon Press, 1988. 260 p.

  2. Jelfimova L.D. A fast cellular method of matrix multiplication. Cybernetics and Systems Analysis. 2008. Vol. 44, N 3. P. 357–361.

  3. Jelfimova L.D. A mixed cellular method of matrix multiplication. Cybernetics and Systems Analysis. 2009. Vol. 45, N 1. P. 19–24.

  4. Jelfimova L.D. New cellular methods for matrix multiplication. Cybernetics and Systems Analysis. 2013. Vol. 49, N 1. P. 15–25.

  5. Jelfimova L.D. A unified cellular method for matrix multiplication. Cybernetics and Systems Analysis. 2013. Vol. 49, N 5. P. 663–672.

  6. Jelfimova L.D. An ultrafast cellular method for matrix multiplication. Cybernetics and Systems Analysis. 2018. Vol. 54, N 6. P. 892–899.

  7. Strassen V. Gaussian elimination is not optimal. Numerische Mathematik. 1969. Vol. 13. P. 354-356.

  8. Laderman J.D. A noncommutative algorithm for multiplying matrices using 23 multiplications. Bulletin of the American Mathematical Society. 1976. Vol. 82, N 1. P. 126–128.




© 2023 Kibernetika.org. All rights reserved.