10
$\begingroup$

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 PTLU factorization while not all square matrices are invertible. Therefore PTLU factorization is more versatile. Any other insights are still appreciated however so please comment or answer the question. Thanks

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.