The cost of decomposition $LU=PA$ for the matrix $A_{N\times N}$ is $O(N^3)$. However if we know about some special properties of matrix $A$ then we can reduce this cost but I wonder how to do it.
In my book it is written that for example for matrix A such that $a_{ij}=0$ for $i>j+1$ and $\det A\neq 0$ this cost can be $O(N^2)$ but I can't imagine an algorithm that would do that.
Can anyone present such an algorithm?