I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices? $$ \begin{bmatrix} A & 0\\ C & D \end{bmatrix} \begin{bmatrix} P & 0\\ R & S \end{bmatrix} = \begin{bmatrix} AP & 0\\ CP + DR & DS \end{bmatrix} $$ Initially, I thought the above block decomposition yields an $O(n^2)$ time algorithm since there are 4 recursive instances of multiplication of $n/2 \times n/2$ matrices. However, I quickly realized that we cannot recurse since the lower left blocks are not triangular ($C$ and $R$ above).
8
-
2$\begingroup$ This looks like homework. $\endgroup$– GamowMar 31, 2020 at 17:20
-
$\begingroup$ I also don't see any easy way to reduce general matrix multiplication to lower triangular multiplication. We can decompose matrix into LUP decomposition but we still don't get product of two lower (or upper) triangular matrices $\endgroup$– Pranav BishtMar 31, 2020 at 17:45
-
1$\begingroup$ Hint: consider $n/3\times n/3$ submatrices. $\endgroup$– Emil JeřábekApr 1, 2020 at 7:01
-
2$\begingroup$ @Gamow It's not homework. In fact, I was creating a short question on block-wise matrix multiplication as a TA. Now understanding the solution, I can understand why you felt its a homework question. $\endgroup$– Pranav BishtApr 1, 2020 at 15:24
-
1$\begingroup$ It would actually manifest if you iterated the decomposition to $n/2\times n/2$ matrices twice (yielding a decomposition to $n/4\times n/4$ matrices). $\endgroup$– Emil JeřábekApr 1, 2020 at 16:09
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}^{th}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}^{th}$ block of $3n \times 3n$ matrix $N$ with rest of the blocks all zero. Both M and N are lower triangular. An asymptotically faster algorithm for $M.N$ would then yield faster algorithm for $A.B$ too.
$$ \begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & A & 0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0\\ B & 0 & 0\\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ AB & 0 & 0 \end{bmatrix} $$
It's amazing how this argument does not manifest when trying to embed $A$ and $B$ in $2n \times 2n$ matrices!