\section{Fast Givens Rotations}

In this section we show how to use fast Givens rotations to find
the appropriate matrix $\Psi$ in Equation~\ref{pre-APsiA'}.
The Givens rotation performed on a 1 x 2 vector $A = [a_{1} \;\; a_{2}]$ consists
of post-multiplying vector $A$ by an orthogonal matrix $\Theta$
of the form
  \begin{equation}
	\Theta = \left [
		  \begin{array}{cr}
			\cos \alpha  &  - \sin \alpha \\
			\sin \alpha  &    \cos \alpha
		  \end{array}
		 \right ]
     \label{Theta}
  \end{equation}
to give a new 1 x 2 vector $A^{'} = [a^{'}_{1} \;\; a^{'}_{2}]$.  
 The matrix $\Theta$ can be chosen such that the resulting
vector $A^{'}$ lies along the first coordinate axis (i.e. $a^{'}_2$ = 0).
Thus, a Givens rotation can be used to zero out one particular 
element of the vector.
It is seen that
  \begin{equation}
    [a_{1} \;\; a_{2}] \left [
		   \begin{array}{cc}
			\frac{a_{1}}{\sqrt{a_{1}^{2} + a_{2}^{2}}} &
			\frac{- a_{2}}{\sqrt{a_{1}^{2} + a_{2}^{2}}} \\
			\frac{a_{2}}{\sqrt{a_{1}^{2} + a_{2}^{2}}} &
			\frac{a_{1}}{\sqrt{a_{1}^{2} + a_{2}^{2}}} 
		   \end{array}
		  \right ]
	=
    \left [ \sqrt{a_{1}^{2} + a_{2}^{2}} \;\; 0 \right ],
   \label{appropTheta}
  \end{equation}
therefore an appropriate choice for $\Theta$ can be made.  
As seen in Equation~\ref{appropTheta}, the Givens rotation requires a
square root calculation.  Computation of square roots can be
time consuming, so it is beneficial to minimize the number of square root
calculations.
A triangularization algorithm which eliminates the necessity for computing
square roots is called fast Givens rotations \cite{Gentleman73}.
Consider a matrix factorization
  \begin{equation}
	  S = ADA^{T},		\label{M-ADA}
  \end{equation}
where $D$ is a diagonal matrix.  The goal is to transform the factorization in
Equation~\ref{M-ADA} to the factorization
  \begin{equation}
	  S = A^{'}D^{'}(A^{'})^{T},		\label{M-A'D'A'}
  \end{equation}
where $D^{'}$ is a diagonal matrix and $A^{'}$ is unit lower triangular.

\input{givens-1x2}
\input{givens-1xn}
\input{givens-mxn}
\input{givens-opt}


