Editing QR decomposition (section)

===Using Givens rotations===
QR decompositions can also be computed with a series of [[Givens rotation]]s. Each rotation zeroes an element in the subdiagonal of the matrix, forming the ''R'' matrix.  The concatenation of all the Givens rotations forms the orthogonal ''Q'' matrix.

In practice, Givens rotations are not actually performed by building a whole matrix and doing a matrix multiplication.  A Givens rotation procedure is used instead which does the equivalent of the sparse Givens matrix multiplication, without the extra work of handling the sparse elements. The Givens rotation procedure is useful in situations where only relatively few off-diagonal elements need to be zeroed, and is more easily parallelized than [[Householder transformation]]s.

====Example====
Let us calculate the decomposition of
: <math>A = \begin{bmatrix}
  12 & -51 &   4 \\
   6 & 167 & -68 \\
  -4 &  24 & -41
\end{bmatrix}.</math>

First, we need to form a [[rotation matrix]] that will zero the lowermost left element, {{nowrap|1=<math>a_{31} = -4</math>.}}  We form this matrix using the Givens rotation method, and call the matrix <math>G_1</math>.  We will first rotate the vector {{nowrap|<math>\begin{bmatrix} 12 & -4 \end{bmatrix}</math>,}} to point along the ''X'' axis.  This vector has an angle {{nowrap|<math display="inline">\theta = \arctan\left(\frac{-(-4)}{12}\right)</math>.}}  We create the orthogonal Givens rotation matrix, <math>G_1</math>:

:<math>\begin{align}
  G_1 &= \begin{bmatrix}
    \cos(\theta) & 0 & -\sin(\theta) \\
               0 & 1 &             0 \\
    \sin(\theta) & 0 &  \cos(\theta)
  \end{bmatrix} \\
      &\approx \begin{bmatrix}
    0.94868 & 0 & -0.31622 \\
    0       & 1 &  0       \\
    0.31622 & 0 &  0.94868 
  \end{bmatrix}
\end{align}</math>

And the result of <math>G_1A</math> now has a zero in the <math>a_{31}</math> element.
:<math>G_1A \approx \begin{bmatrix}
  12.64911 & -55.97231 &  16.76007 \\
   6       & 167       & -68       \\
   0       &   6.64078 & -37.6311 
\end{bmatrix}</math>

We can similarly form Givens matrices <math>G_2</math> and {{nowrap|<math>G_3</math>,}} which will zero the sub-diagonal elements <math>a_{21}</math> and {{nowrap|<math>a_{32}</math>,}} forming a triangular matrix {{nowrap|<math>R</math>.}}  The orthogonal matrix <math>Q^\textsf{T}</math> is formed from the product of all the Givens matrices {{nowrap|<math>Q^\textsf{T} = G_3 G_2 G_1</math>.}}  Thus, we have {{nowrap|<math>G_3 G_2 G_1 A = Q^\textsf{T} A = R</math>,}} and the ''QR'' decomposition is {{nowrap|<math>A = QR</math>.}}

====Advantages and disadvantages====

The QR decomposition via Givens rotations is the most involved to implement, as the ordering of the rows required to fully exploit the algorithm is not trivial to determine. However, it has a significant advantage in that each new zero element <math>a_{ij}</math> affects only the row with the element to be zeroed (''i'') and a row above (''j''). This makes the Givens rotation algorithm more bandwidth efficient and parallelizable than the Householder reflection technique.