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.
$\begingroup$
$\endgroup$
1
-
$\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$– katagoNov 23, 2020 at 8:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
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.
answered Nov 23, 2020 at 2:35
-
14
-
4
-
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$ Nov 23, 2020 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$ Nov 23, 2020 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$– MitchNov 23, 2020 at 20:49