1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
|
Abstract. Two recursive cellular methods for multiplying matrices of even and odd order, namely: n = 2q r and а n = 3q r (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,14m 2.807) and O (1,17m 2.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.