Having two square matrices $n \times n$ where the values are repeated for entries which are located diagonally with respect to each other, is it possible to get a time complexity $O(n^2\log n)$?
I tried the Strassen method for this kind of matrices but I can't achieve to get that complexity, any tips?
An example of the matrices could be:
$$\begin{pmatrix} 1 & 2 & 3 & 4\\ 5 & 1 & 2 & 3\\ 6 & 5 & 1 & 2\\ 7 & 6 & 5 & 1 \end{pmatrix}$$
Thanks (:
The general purpose matrix multiplication of two $4 \times 4$ matrices requires $64$ elementary multiplications. Using Strassen's algorithm, only $49$ are required.
Due to the special diagonal structure of the matrices, $37$ multiplications are sufficient:
Matrix A:
a1 a2 a3 a4
a5 a1 a2 a3
a6 a5 a1 a2
a7 a6 a5 a1
Matrix B:
b1 b2 b3 b4
b5 b1 b2 b3
b6 b5 b1 b2
b7 b6 b5 b1
Products:
P01 = a1b1
P02 = a1b2
P03 = a1b3
P04 = a1b4
P05 = a1b5
P06 = a1b6
P07 = a1b7
P08 = a2b1
P09 = a2b2
P10 = a2b3
P11 = a2b5
P12 = a2b6
P13 = a2b7
P14 = a3b1
P15 = a3b2
P16 = a3b5
P17 = a3b6
P18 = a3b7
P19 = a4b1
P20 = a4b5
P21 = a4b6
P22 = a4b7
P23 = a5b1
P24 = a5b2
P25 = a5b3
P26 = a5b4
P27 = a5b5
P28 = a5b6
P29 = a6b1
P30 = a6b2
P31 = a6b3
P32 = a6b4
P33 = a6b5
P34 = a7b1
P35 = a7b2
P36 = a7b3
P37 = a7b4
Matrix product $C = A \times B$:
c11 = P01 +P11 +P17 +P22
c12 = P02 +P08 +P16 +P21
c13 = P03 +P09 +P14 +P20
c14 = P04 +P10 +P15 +P19
c21 = P05 +P12 +P18 +P23
c22 = P01 +P11 +P17 +P24
c23 = P02 +P08 +P16 +P25
c24 = P03 +P09 +P14 +P26
c31 = P06 +P13 +P27 +P29
c32 = P05 +P12 +P23 +P30
c33 = P01 +P11 +P24 +P31
c34 = P02 +P08 +P25 +P32
c41 = P07 +P28 +P33+P34
c42 = P06 +P27 +P29 +P35
c43 = P05 +P23 +P30 +P36
c44 = P01 +P24 +P31 +P37
It might be possible to reduce this number even further. No optimization was attempted rather than keeping track of the products which actually occur.
