Inverse of matrix with QR method

1,614

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:
1,614

Related videos on Youtube

Amir
Author by

Amir

Computationally Intensive ...

Updated on August 01, 2022

Comments

  • Amir
    Amir over 1 year

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

    • Admin
      Admin about 11 years
      What is the size of the input matrix? $n\times n$? Is it full rank?
    • Amir
      Amir about 11 years
      Yes it is $n×n$ and full rank
    • joriki
      joriki about 11 years
      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"?
    • Amir
      Amir about 11 years
      Yes, you are right @joriki. I wrote it fast.
    • joriki
      joriki about 11 years
      Note that I had also provided the correct articles to make the question grammatical.
  • Steve
    Steve about 11 years
    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.