0
$\begingroup$

$A$ is an invertible matrix square $n$ matrix. The exercise is about 3 different ways you can solve this and I have to determine its efficiency. It's always the same matrix $A$ but a different right hand side vector.

$$ Ax_i = b_i \text{ for } i=1,...,m $$

The first method is solving each system of linear equations individually. I'm pretty sure this would result in a complexity of $O(m n^3)$, as elimination for a squared matrix is $O(n^3)$ and we have $m$ systems.

The second method is "solving all systems together using the idea in Gauss-Jordan". I'm not entirely sure here what they mean here. I think the advantage that we have here is that we only have to put $A$ in the echelon form once? And then we basically repeat the operations we did to get $A$ in that form for each $b_i$. But I don't know what cost this would have. I know putting in echelon form would be $O(n^3)$ though.

The last method is first inverting $A$ and then calculating $x_i = A^{-1}b_i$ for each $i$. This should be $O(n^3 + mn^2)$. The first term is for inverting the matrix and the second one for the $m$ matrix multiplications.

The last question on the problem set is if any method has an advantage. I can see for $m < n$ they don't really differ too much, but as $m$ grows, for example when $m=n^2$, the third method would be $O(n^4)$ while the first method is $O(n^5)$. But I still don't know about the second method, could someone help me please? Thanks!

$\endgroup$
  • 1
    $\begingroup$ Isn't the second method the method of forming an $LU$ decomposition and solving $LU x_i = b_i$ ? Because if so, forming the (dense) $LU$ decomposition is an $\mathcal{O}(n^3)$ operation and solving one system is a $\mathcal{O}(n^2)$ operation which makes the total a $\mathcal{O}(n^3 + m n^2)$ operation. So if $m = n$ the problem remains $\mathcal{O}(n^3)$. $\endgroup$ – hickslebummbumm Oct 11 '14 at 18:18
  • $\begingroup$ Can you explain what is $m$? $\endgroup$ – user2097 Oct 11 '14 at 18:26
  • $\begingroup$ @user2097, sorry, it was supposed to be $m$ systems $\endgroup$ – Clash Oct 12 '14 at 0:24

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.