Department of Applied Mathematics and Theoretical Physics

Numerical Analysis Course

QR Factorisation

The QR factorisation of a matrix $A$ is its decomposition as the product where the matrix $Q$ is orthogonal and the matrix $R$ is upper triangular. Notice that the QR factorisation of a given matrix $A$ is not unique.

QR factorisation is often used to solve Linear Least Squares (LLS) problems, and it forms the basis for the QR Algorithm (see Part II), an iterative algorithm used to compute the eigenvalues and eigenvectors of a matrix.

Contents

Introduction

There are several ways in which the QR factorisation can be carried out. In what follows, we will mainly focus on two such ways, namely the method involving Householder reflections, and the method involving Givens rotations.

Householder reflections

A Householder reflection is a transformation of the form

$\Omega = I - 2\frac{uu^{\top}}{||u||^2}$

where $u\in R^m\backslash\{0\}$. Each such matrix is symmetric and orthogonal, and it can be shown that $\Omega x$ is the reflection of $x$ in the hyperplane orthogonal to $u$. Hence, $\det(\Omega) = -1$, and so $\Omega\in O_m \backslash SO_m$.

Givens rotations

A Givens rotation $\Omega^{[p,q]}$ is an orthogonal transformation of determinant 1 (hence it's in $SO_m$) which coincides with the unit matrix, except at the four entries:

$\Omega^{[p,q]}_{p,p} = \Omega^{[p,q]}_{q,q} = \cos(\theta)$

$\Omega^{[p,q]}_{p,q} = \sin(\theta)$

$\Omega^{[p,q]}_{q,p} = -\sin(\theta)$

for some $\theta\in[-\pi,\pi]$.

Implementation

When implementing the Householder reflections method, we have been careful not to execute explicit matrix multiplication when computing

$\left(I - 2 \frac{uu^{\top}}{||u||^2}\right)A = A - 2 \frac{u(u^{\top} A)}{||u||^2},$

which is an $O(m^2n)$ operation, but, as suggested in the notes, we have first evaluated

$w^{\top} = u^{\top} A$ (in $O(mn)$ operations)

and then we have formed

$A - 2 \frac{uw^{\top}}{||u||^2}$ (also in $O(mn)$ operations).

For large $m$, this is way more efficient. See get_householder.m and do_householder.m

When implementing the Givens rotations method, we have made use of MATLAB's inbuilt command givens, which essentially returns the values of the required $\Omega^{[p,q]}$ that differ from the identity. See get_givens.m

Moreover, the Givens rotation matrix has 'few' nonzero entries and so is sparse; this allows us to avoid doing a full matrix multiplication - we can get away with changing two rows. See do_givens.m

The GUI

Running the downloadable MATLAB® code on this page opens a GUI which demonstrates the QR algorithm.

IB_QR_GUI

Interface

You can enter any square matrix you like, or use one of the preset matrices available. If you choose to use one of the preset matrices, you have a choice between sparse and dense matrices.

If you only want to see the structure of the matrices (represented by black for non-zero entries, white for zero entries, and grey for entries that differ from the previous matrix), you can click on the 'Structure only' radio button. By default the GUI shows both the structure and the values. Note that if your matrix or the values in it are large, it is advisable to switch to the 'structure only' mode because of overlap. As soon as you enter a matrix, it will appear on the far left. At the same time, the current matrix for $R$ and the current matrix for $Q^{\top}$ will appear.

You can also select whether to use Householder reflections or Givens rotations to perform the QR algorithm. Notice that once you choose a method, you cannot change it during the iterations! The default method is Householder.

Once you have input the matrix (and chosen the method), you can start the QR algorithm by clicking on the 'Next' push button. You will see the new $R$ (in grey, you can see which rows have changed from the previous $R$), and the new $Q^{\top}$. To keep track of the number of iterations, there is a display on the right of the 'Next' push button. Keep going until the algorithm terminates (when the string 'Finished!' appears). To start a new iteration, input (or select) another matrix.

To close the GUI, click on the 'Close' push button.

The Code

All files as zip archive: qr_fac_all.zip