0
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ This looks like homework. $\endgroup$ – Gamow Mar 31 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 Bisht Mar 31 at 17:45
  • 1
    $\begingroup$ Hint: consider $n/3\times n/3$ submatrices. $\endgroup$ – Emil Jeřábek Apr 1 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 Bisht Apr 1 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řábek Apr 1 at 16:09
2
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.