32
$\begingroup$

I have a lower $n\times n$ triangular matrix called $A$ and I want to get $A^{-1}$ solved in $O(n^2)$. How can I do it?

I tried using a method called "forward substitution", but the inversion is solved in $O(n^3)$ for full $n\times n$ matrix.

$\endgroup$
  • $\begingroup$ We can decompose the matrix $A\in M_{n\times n}$ into many fragments may be each fragment is in $M_{O(n^{\alpha}) \times O(n^{\alpha}) }$, $\alpha<1$ and $\alpha$ is choosed later, and then mutiplicate these fragments separately, and at the same time, we find that these multiplications are repeated to a certain extent, so as to get a better result than $O(n^3)$. In fact we can use the decomposite process at infinite scale, to gain a algorithm with time complexity $O(n^{3-O(\alpha)})$, but it is unknown if this argument can gain a algorithm with time complexity $O(n^{2+\epsilon})$ $\endgroup$ – katago Nov 23 '20 at 8:43
88
$\begingroup$

No such method is known at present.

If one could invert lower triangular $n \times n$ matrices in time $O(n^2)$ then one could multiply $N \times N$ matrices in time $O(N^2)$. Indeed let $n=3N$ and apply the putative inversion algorithm to the block matrix $$ \left( \begin{array}{ccc} I & 0 & 0 \cr B & I & 0 \cr 0 & A & I \end{array} \right) $$ for any $N\times N$ matrices $A,B$: the inverse is $$ \left( \begin{array}{rrr} I & 0 & 0 \cr -B & I & 0 \cr AB & \!\!\! -A & I \end{array} \right) \, , $$ so you could read $AB$ off the bottom left block.

It is still an open problem whether general matrix multiplication can be done in time $O(N^2)$, or even $O(N^{2+o(1)})$. In particular it follows that no method is known to do what you are asking.

In fact it is known that conversely an algorithm that takes $O(N^2)$ or $O(N^{2+o(1)})$ time to multiply $N \times N$ matrices would let us also invert $n \times n$ matrices in time $O(n^2)$ or $O(n^{2+o(1)})$ respectively (with a different $O$-constant, and not limited to triangular matrices). So your question is in fact equivalent to the open question about fast matrix multiplication. See for instance page 3 of these lecture notes by Garth Isaak, which also shows the block-diagonal trick (in the upper- instead of lower-triangular setting).

POSTSCRIPT Strictly speaking, the reduction from $O(N^c)$ matrix multiplication to $O(n^c)$ inversion of triangular matrices means only that either we don't know how to attain $c=2$ or $c=2+o(1)$ in the latter problem, or such an algorithm is known but somehow nobody has noticed that this solves the former problem. But the second possibility seem most unlikely, because fast matrix multiplication is such a celebrated problem, and its reduction to triangular-matrix inversion is quite well known.

$\endgroup$
  • 13
    $\begingroup$ The perfect answer ! $\endgroup$ – Denis Serre Nov 23 '20 at 6:02
  • 3
    $\begingroup$ this answer is really beautiful. $\endgroup$ – lalala Nov 23 '20 at 8:49
  • 3
    $\begingroup$ I think it is known that we cannot have an algorithm with complexity $O(N^2)$ (though $O(N^{2+o(1)})$ is certainly unknown). Unfortunately I don't have a good source, only my BSc thesis which (I think) shows in Theorem 2.6.2 that the rank of the <n,n,n> matrix multiplication tensor is $>n^2$, which together with some relations between computational complexity and the rank of that tensor, show that the complexity can't be strictly $O(N^2)$. But I'm hardly an expert! $\endgroup$ – tomsmeding Nov 23 '20 at 9:57
  • 1
    $\begingroup$ Note: my comment above refers to algorithms using just a sequence of operations from {+, -, *, constant scaling}, but I believe that's a reasonable restriction. It is also the restricted language that the tensor-rank based matrix multiplication algorithms search in. $\endgroup$ – tomsmeding Nov 23 '20 at 10:00
  • 1
    $\begingroup$ I'm just putting this out there... it's gonna turn out to be $O(n^2 \log^2 n)$. Analogous to integer multiplication, but in two dimensions blah blah Fourier transform somethety something. $\endgroup$ – Mitch Nov 23 '20 at 20:49

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.