what is the advantage of LU factorization

Question

In this question Necessity/Advantage of LU Decomposition over Gaussian Elimination it is asked why LU factorization is useful. I understand how this reduces time complexity of solving a number equations of the form Ax=b for matrix A and column matrix b but why don't you just find A^-1 instead?

Inversion has a lower time complexity than LU factorization (comparing the value used in the previous link and ones found here https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations) and matrix multiplication has the same time complexity in this case as is needed to solve for different values of b.

Overall, I see the value of LU factorization as opposed to resolving multiple matrix equations but I don't know why it would be better than the method I described that uses matrix inversion. Clearly LU factorization has some value, I would like to know what that it. Thanks

I believe the answer to this question is that all square matrices have a P^TLU factorization while not all square matrices are invertible. Therefore P^TLU factorization is more versatile. Any other insights are still appreciated however so please comment or answer the question. Thanks

Answer 1

The $LU$ factorization of a matrix has other advantages than just speeding up Gaussian elimination. It is also really efficient from a storage point of view. Example: take the matrix $$A = \begin{pmatrix} \phantom{-}2 & \phantom{-}1 & \phantom{-}3 \\ \phantom{-}4 & -1 & \phantom{-}3 \\ -2 & \phantom{-}5 & \phantom{-}5 \end{pmatrix}.$$ Applying $LU$ factorization we get the identity $$A = \begin{pmatrix} \phantom{-}1 & \phantom{-}0 & \phantom{-}0 \\ \phantom{-}2 & \phantom{-}1 & \phantom{-}0 \\ -1 & -2 & \phantom{-}1 \end{pmatrix} \begin{pmatrix} \phantom{-}2 & \phantom{-}1 & \phantom{-}3 \\ \phantom{-}0 & -3 & -3 \\ \phantom{-}0& \phantom{-}0 & \phantom{-}2 \end{pmatrix} = LU.$$ Notice how we can cleverly store the $LU$ factorization in the computer using the matrix $B$ defined as the matrix with elements $$b_{ij} = \begin{cases} l_{ij} & \text{if } i > j \\ u_{ij} & \text{otherwise,} \end{cases}$$ that is, in this particular example, the matrix $$B = \begin{pmatrix} \phantom{-}2 & -1 & \phantom{-}3 \\ \phantom{-}2 & -3 & -3 \\ -1 & -2 & \phantom{-}2 \end{pmatrix}.$$ So you can see that the $LU$ factorization of a matrix has some really convenient storage applications. Think about calculating determinant of $A$. All you need is $$2 \times (-3) \times 2 $$ from the diagonal of $B$.