Drawbacks on using LU decomposition I have been reading about LU decomposition, and one thing I realised is that we don't really talk much about its disadvantage. Using LU can be unstable in the algorithm. But what other drawbacks about it can we deduce? 
 A: It depends really on the system you are trying to solve, that being said, in general, there are systems that are relatively ill-conditioned, so the result you may get may be the only result you have the right to expect from. A few non-argumentative facts about LU decomposition are:


*

*It requires forward and backward substituion

*Solving requires storing in memory the LU factors

*It requires around $\frac{n^3}{3}$ FLOPS

*It requires (like most) pivoting to ensure numerical stability


You may run into more possibilities for blown up errors if you poorly manage your FLOPS and operations, however, for any precision, this consequence is unavoidable, even if you are using other operations. 
A: *

*Gaussian elimination with partial pivoting is backward stable in the theoretical sense of the term. However, the best possible growth factor for the error (covering all invertible matrices) scales like $2^d$ where $d$ is the dimension. Thus the optimal general error estimate doesn't really make it look backward stable (over all invertible matrices), because upon use in dimension $100$ you can in theory lose a factor of $2^{100} \approx 10^{30}$ in accuracy. However, one peculiar thing, which to my understanding is still not well-understood, is that the actual examples where the growth factor is so large never come up in applications. Indeed in applications the stability of Gaussian elimination with partial pivoting seems to be quite good*. Without partial pivoting it is horrible, however.

*Gaussian elimination for a general matrix takes about $n^3/3$ operations, at least the first time. (Afterwards the LU decomposition reduces it to about $n^2$ operations.) In many applications this is too long: the preference in the dense context is to use $mn^2$ operations, where $m \ll n$. This corresponds to doing the procedure using just $m$ matrix multiplications. Many iterative methods fall into this class.

*Memory is not a problem in the dense context: in memory-intensive applications one can overwrite the entries of $A$ with the entries of $U$ (like how we commonly write hand calculations) and put entries of $L$ into the newly created zero entries of $A$. Thus no more memory is technically required than was used to store $A$ in the first place. In less memory-intensive applications you can store $A,L,U$ separately with no real difficulty.

*Memory is a problem in the sparse context, because Gaussian elimination can easily destroy sparsity. In the sparse context you usually want a method that treats the matrix $A$ as an abstract linear map, so that you do not have direct access to its entries but only to what it does to vectors. Again many iterative methods fall into this class.


* To be more precise, the growth factor for Gaussian elimination is usually not drastically larger than the condition number of the matrix. The condition number can easily be huge, but there is nothing algorithmic that can be done to reduce it. Preconditioning, which is fairly problem-specific, is required instead.
