The Sparse QR Factorization

The QR Factorization will factorize our $\mathbf{A}$ matrix into a $\mathbf{Q}$ and an $\mathbf{R}$ matrix, such that $\mathbf{Q}\mathbf{R}=\mathbf{A}$. The $\mathbf{Q}$ matrix is orthogonal, and the $\mathbf{R}$ matrix is upper triangular.

One can get an impression of the interesting properties of orthogonal factorizations by considering the following trivial -- but nonetheless interesting property:

$$\mathbf{Q}\mathbf{R}x = b \quad\mathrm{and}\quad \mathbf{R}x = \mathbf{Q}^Tb$$

Once we know $\mathbf{Q}$, solving the original system is a simple matter of back-substitution, since $\mathbf{R}$ is upper-triangular.