Department of Justice, Russian Federal Center of Forensic Science, Khokhlovskii pereul. 13-2, Moscow, 109028, Russia
Abstract:
A method for deriving bilinear algorithms for matrix multiplication is proposed. New estimates for the bilinear complexity of a number of problems of the exact and approximate multiplication of rectangular matrices are obtained. In particular, the estimate for the boundary rank of multiplying $3\times 3$ matrices is improved and a practical algorithm for the exact multiplication of square $n\times n$ matrices is proposed. The asymptotic arithmetic complexity of this algorithm is $O(n^{2.7743})$.
Key words:bilinear complexity, rank of the matrix multiplication problem, boundary rank, algorithms for exact and approximate matrix multiplication, least-squares method, objective function.
Fulltext:
PDF file (263 kB)