Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.

share|improve this question
    
What is the size of the input matrix? $n\times n$? Is it full rank? –  user2468 Sep 16 '12 at 17:24
    
Yes it is $n×n$ and full rank –  Amir Masoud Sep 16 '12 at 18:08
    
The title and body seem to bear no relation to each other. I suspect that in the body "matrix" was supposed to read "the inverse of a matrix"? –  joriki Sep 16 '12 at 18:18
    
Yes, you are right @joriki. I wrote it fast. –  Amir Masoud Sep 16 '12 at 18:19
    
Note that I had also provided the correct articles to make the question grammatical. –  joriki Sep 16 '12 at 18:22

2 Answers 2

up vote 0 down vote accepted

As far as I recall, the QR decomposition stage requires $O\left(n^3\right)$ operations.

If I assume that you are not finding the inverse, but solving the linear system $Ax=b$, then once you have found the QR decomposition of $A$, the remaining operations are all $O\left(n^2\right)$.

If you are explicitly finding the inverse, then this will require an additional $O\left(n^3\right)$ operations once you have found the QR decomposition.

share|improve this answer

Calculating the $QR$ decomposition has complexity $O(n^3)$, after which $A = QR$ can be inverted into $R^{-1} Q^T$ also by $O(n^3)$ operations. In many of these algorithms, it is not the complexity that is important, but rather the numerical stability. It is well-known that first decomposing into $QR$ before inverting provides greater stability.

share|improve this answer
    
This. More or less all dense linear algebra is in $O(n^3)$ field operations, unless you decide to use a funkier matrix multiplication exponent, i.e. Coppsmith-Winograd's. –  user2468 Sep 17 '12 at 4:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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