Inverting lower triangular matrix in time $n^2$ 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.
 A: 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.
