I am currently trying to understand how to wrap my head around the following problem -

Consider solving $AX=B$ for $X$, where $A$ is $n\times n$, and $X$ and $B$ are $n\times m$. There are two obvious algorithms. The first algorithm factorizes $A=PLU$ using Gaussian elimination and then solves for each column of $X$ by forward and back substitution. The second algorithm computes $A^{-1}$ using Gaussian elimination and then multiplies $X=A^{-1}B$. Count the number of flops required by each algorithm, and show that the first one requires fewer flops.

My Book refers to the complexity of LU decomposition as $\frac{2}{3}n^3+\mathcal{O}({n^2})$. However my book never really discusses PLU. Am I to assume that PLU and LU are the same, complexity wise?

I've read up and looked at some proofs and I can see why some Gaussian elimination algorithms have $\frac{2}{3}n^3+\mathcal{O}({n^2})$ complexity using 3 basic summation properties here. I'm not sure if this proof is for just Gaussian elimination or LU. Moreover, I am not sure what algorithm the book is referring to in the second part of the question. I've read that finding the inverse takes $\mathcal{O}(n^3)$ complexity using Gaussian elimination and that multiplication takes $\mathcal{O}(n^3)$ as well, but I am not sure how to continue. Any direction would be helpful.

Edit: I believe I found something that discusses this but they seem to get a different coefficient for their LU decomposition complexity - here. I got 2/3 but they are getting 4/3 I believe.


Your Answer

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

Browse other questions tagged or ask your own question.