In class, we learned about QR factorization which is often used to solve least squares problems. We learned the classic Gram-Schmidt method, which iteratively computes the column vectors in the Q matrix and the elements in the upper triangular R matrix. QR factorization, however, is unstable because of rounding errors. There is another QR factorization algorithm, using matrices called Givens rotations, which calculates a series of matrices whose product is the R matrix.

A Givens rotation applied on a 2 element vector [x,y] is of the form:

where c=cos(theta) and s=sin(theta) for some theta. Applying this sort of trick on a large matrix nxn matrix A involves looking at two successive rows and generating the Givens matrix. The following is an example, taken from wikipedia, for a 3×3 matrix:

where theta is intelligently picked to be atan(6/-4) so the result in A(3,1) becomes 0

The final result becomes

To generate the QR factorizaation, we need to 0 out all the values of A below the diagonal.
While the indivdual Givens matrices are not independent (i.e. they aren’t multiplicatively associative), there are methods that can parallelize this process. Calculating the Givens matrix in the following order (given for an 8×8 matrix) :

This algorithm can achieve results in half the time if we fully parallelize. It also does not suffer from the degree of instability as Gram-Schmidt. Finally, this algorithm is most useful when we are dealing with sparse matrices; if many of the entries are 0, we can save a lot of the pairwise row calculations.

Sources:
http://www.cse.uiuc.edu/courses/cs554/notes/11_qr.pdf
http://en.wikipedia.org/wiki/Givens_rotation
http://en.wikipedia.org/wiki/QR_decomposition