%% 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.
% 
%% 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 <matlab:doc('givens') 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(R) 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
% * <IB_QR_GUI.m> (Run this)
% * <IB_QR_GUI.fig> (Required)
% * <do_householder.m> (Required - applies Householder)
% * <get_householder.m> (Required - calculates Householder)
% * <do_givens.m> (Required - applies Givens)
% * <get_givens.m> (Required - calculates Givens)
%
% All files as zip archive: <qr_fac_all.zip>
