Geodesic
On bilinear complexity of multiplication of $5\times2$ matrix by $2\times2$ matrix
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 19-29 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this paper we study bilinear complexity (i.e. the minimum number of multiplications without using commutativity of the elements) for the problem of multiplication of matrices of small size. We show that the bilinear complexity for the problem of multiplication of a $5\times2$ matrix by a $2\times~2$ matrix is at least 17 for any field.
Mots-clés : matrix multiplication
Keywords: algorithm, complexity, bilinear complexity. 
@article{UZKU_2014_156_3_a2,
     author = {V. B. Alekseev},
     title = {On bilinear complexity of multiplication of $5\times2$ matrix by $2\times2$ matrix},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {19--29},
     year = {2014},
     volume = {156},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a2/}
}
TY  - JOUR
AU  - V. B. Alekseev
TI  - On bilinear complexity of multiplication of $5\times2$ matrix by $2\times2$ matrix
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2014
SP  - 19
EP  - 29
VL  - 156
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a2/
LA  - ru
ID  - UZKU_2014_156_3_a2
ER  - 
%0 Journal Article
%A V. B. Alekseev
%T On bilinear complexity of multiplication of $5\times2$ matrix by $2\times2$ matrix
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2014
%P 19-29
%V 156
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a2/
%G ru
%F UZKU_2014_156_3_a2
V. B. Alekseev. On bilinear complexity of multiplication of $5\times2$ matrix by $2\times2$ matrix. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 19-29. http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a2/

[1] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 ; Shtrassen V., “Algoritm Gaussa ne optimalen”, Kiberneticheskii sb., 7, Mir, M., 1970, 67–70 | DOI | MR | Zbl

[2] Coppersmith D., Winograd S., “Matrix Multiplication via Arithmetic Progressions”, J. Symbolic Computation, 9:3 (1990), 251–280 | DOI | MR | Zbl

[3] Bürgisser P., Clausen M., Shokrollahi M. A., Algebraic complexity theory, Springer, Berlin–Heidelberg, 1997, 618 pp. | MR | Zbl

[4] Waksman A., “On Winograd's algorithm for inner products”, IEEE Trans. Comput., C-19 (1970), 360–361 | DOI | MR

[5] Alekseyev V. B., “On the complexity of some algorithms of matrix multiplication”, J. Algorithms, 6:1 (1985), 71–85 | DOI | MR | Zbl

[6] Laderman J. D., “A noncommutative algorithm for multiplying $3\times3$ matrices using 23 multiplications”, Bull. Amer. Math. Soc., 82:1 (1976), 126–128 | DOI | MR | Zbl

[7] Bläser M., “On the complexity of the multiplication of matrices of small formats”, J. Complexity, 19 (2003), 43–60 | DOI | MR | Zbl

[8] Makarov O. M., “Nekommutativnyi algoritm umnozheniya kvadratnykh matrits pyatogo poryadka, ispolzuyuschii sto umnozhenii”, Zhurn. vychisl. matem. i matem. fiziki, 27:2 (1987), 311–315 | MR | Zbl

[9] Smirnov A. V., “O bilineinoi slozhnosti i prakticheskikh algoritmakh umnozheniya matrits”, Zhurn. vychisl. matem. i matem. fiziki, 53:12 (2013), 1970–1984 | DOI | MR

[10] Winograd S., “On multiplication of $2\times2$ matrices”, Linear Algebra Appl., 4 (1971), 381–388 | DOI | MR | Zbl

[11] Hopcroft J. E., Musinski J., “Duality applied to the complexity of matrix multiplication and other bilinear forms”, SIAM J. Comput., 2:3 (1973), 159–173 | DOI | MR | Zbl

[12] Hopcroft J. E., Kerr L. R., “On minimizing the number of multiplications necessary for matrix multiplication”, SIAM J. Appl. Math., 20:1 (1971), 127–148 | DOI | MR

[13] Alekseev V. B., Smirnov A. V., “O tochnoi i priblizhennoi bilineinykh slozhnostyakh umnozheniya matrits razmerov $4\times2$ i $2\times2$”, Sovremennye problemy matematiki, 17, 2013, 135–152 | DOI

[14] Bini D., Capovani M., Lotti G., Romani F., “$O(n^{2.7799})$ complexity for approximate matrix multiplication”, Inform. Process. Lett., 8:5 (1979), 234–235 | DOI | MR | Zbl

[15] Landsberg J. M., “The border rank of the multiplication of $2\times2$ matrices is seven”, J. Amer. Math. Soc., 19:2 (2006), 447–459 | DOI | MR | Zbl