A FAST RECURSIVE ALGORITHM FOR MULTIPLYING MATRICES OF ORDER n=3~q(q>l)

摘要

A new fast recursive algorithm is proposed for multiplying matrices of order n = 3(q) (q 1). This algorithm is based on the hybrid algorithm for multiplying matrices of odd order n = 3 mu (mu = 2q - 1, q 1), which is used as a basic algorithm for mu = 3(q) (q 0). As compared with the well-known block-recursive Laderman's algorithm, the new algorithm minimizes by 10.4% the multiplicative complexity equal toW(m) = 0 896n(2.854) multiplication operations at recursion level d = log(3) n - 3 and reduces the computation vector by three recursion steps. The multiplicative complexity of the basic and recursive algorithms are estimated.