What is the usefulness of matrix decomposition?

Question

Both $LU$, $LDL^T$ and Cholesky decomposition require to use $O(n^3)$ to solve it. However, the time complexity is the same as Gaussian Elimination Method. Some Lecturers say that it can increase the speed of solving $Ax=b$. In fact, these decompositions can only reduce some constant factors for this problem. Therefore, what is the usage of these decompositions?

Answer 1

The factorizations are particularly useful if you have to solve $Ax=b$ for many right hand sides. Each solution takes $O(n^{2})$ time once the factorization has been computed.

Answer 2

Suppose, that we want to solve $Ax = b$ for a single RHS and $n\times n$ dense matrix A. Algorithmic complexity of the LU method and the Gausian elimination method is the same and equal $2/3n^3+O(n^2)$.

This would suggest, that the Gausian elimination can be efficient at least for some problems. However this is far from true. The algorithmic complexity does not take into account memory issues. The LU factorization can be easily optimized for memory accesses using different blocking techiques. Such optimized version are over 10 times faster, than unoptimized version for a moderately large matrices ($n$ of order $10^3$) and even faster for larger ones.

The Gausian elimination is not "memory friendly". Probably it could be also blocked, but resulting algorithm would be (probably) close to the LU factorization.