What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.
Inverse of matrix with QR method
-
0What is the size of the input matrix? $n\times n$? Is it full rank? – 2012-09-16
-
0Yes it is $n×n$ and full rank – 2012-09-16
-
0The 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"? – 2012-09-16
-
0Yes, you are right @joriki. I wrote it fast. – 2012-09-16
-
0Note that I had also provided the correct articles to make the question grammatical. – 2012-09-16
2 Answers
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.
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.
-
0This. 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. – 2012-09-17