It is said that if matrix multiplication of $n\times n$ matrices is doable in $O(n^\omega)$ for some $\omega\geq 2$, so is Gaussian elimination and vice versa.

Now, this could imply that it is somehow possible to do Gaussian elimination by multiplying some matrices (independent of $n$), but I cannot think of anything how this should be possible. Another possibility could be that we can split the matrix into parts and do Gaussian elimination (somehow by matrix multiplication) on those and then do Gaussian elimination on those 4 matrix parts. But again I can't think of any way this is possible. I am equally confused about the inverse problem.

So, I am curious on how to prove the above statement (both directions). Just the (more or less precise) idea would be awesome.


The general idea of Gaussian Elimination involves multiplying by permutation matrices but in a computer, they use a series of other matrices. These are actually never multiplied. The time complexity of Gaussian elimination is $$ \mathcal{O}(n^{3})$$

Gaussian Elimination is actually the LU decomposition. That is the following.

$$ A = LU $$ $$ L_{m-1}\cdots L_{2}L_{1}A = U $$ which gives us the product of the L matrices is actually inverse L $$ L^{-1} = \prod_{i=1}^{m-1} L_{i} $$ Which has to do with the following. In Trefethan the asymptotic analysis is derived geometrically from the following algorithm. enter image description here

The is most done by the by the vector operation in the inner loop which is executing one scalar-vector multiplication and one vector subtraction. $$ u_{j,k:m} = u_{j,k:m} - \ell_{jk}u_{k,k:m} $$ given here that l = m-k+1 is the length of the row then the number of flops is two flops per entry then we get the following analysis.

For each value k, the inner loop is repeated for rows $$ k+1, \cdots, m $$ This gives us a pyramid yielding the work $$ \approx \frac{2}{3}m^{3}flops$$

enter image description here

What you should note is that none of these matrices are never formed and that the algorithm you are talking about, Coppersmith-Winograd is for only very large matrices.


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.