\subsection{Combined Covariance Update}

The combined update of the covariance matrix $P_{t}$ is performed using
fast Givens rotations of the matrices
  \[ A = 
	\left [ \begin{array}{ccc}
		I & HL & 0		\\
		0 & \Phi L & G
		\end{array}
	\right ]
  \]
  \[ D = 
	\left [ \begin{array}{ccc}
		R & 0 & 0	\\
		0 & \overline{D} & 0	\\
		0 & 0 & Q
		\end{array}
	\right ],
  \]
where $A$ is an ($n$+$m$)x(2$n$+$m$) matrix and $D$ is a
(2$n$+$m$)x(2$n$+$m$) diagonal matrix.
For notational convenience, define $A$ as an $M$ x $N$ matrix.
In order to facilitate the development of the mapping for
fast Givens rotations, it is useful to represent 
Algorithm~\ref{givens-mxn-opt} 
in a condensed manner, shown in Algorithm~\ref{givens-short}.
Below is a textual description of what each procedure listed in 
Algorithm~\ref{givens-short} represents:
\begin{description}
\item[$W_{i,N}$:]  
	Rotate $A_{i}$ to zero out the $N$th element
	and compute resulting $A'_{i}$ and $D'$.
\item[$X_{i,N,k}$:]  
	Rotate row $A_{k}$ of matrix $A$,
	changing only elements $i$ and $N$.
\item[$Y_{i,j}$:]  
	Rotate $A_{i}$ to zero out the $j$th element (when $a_{ii}=1$)
	and compute resulting $A'_{i}$ and $D'$.
\item[$Z_{i,j,k}$:]  
	Rotate row $A_{k}$ of matrix $A$ (when $a_{ii}=1$),
	changing only elements $i$ and $j$.
\end{description}


\begin{algorithm}
\begin{tabbing}
For \= For \= For \= each $A_{k}$ below $A_{i}$ xx \= \kill
For each row $A_{i}$ of $A$ ($i=1,\ldots,M$) \\
\> Procedure $W_{i,N}$ \> \> \> 
	[Equations \ref{d'i},\ref{d'j},\ref{Psiij},\ref{APsiA}] \\
\> \\
\> For each $A_{k}$ below $A_{i}$ ($k=i+1,\ldots,M$) \\
\> \> Procedure $X_{i,N,k}$ \> \>
	[Equations \ref{a'ki},\ref{a'kj}] \\
\> EndFor \\
\> \\
\> For each element $j$ of $A_{i}$ ($j=N-1,\ldots,i+1$) \\
\> \> Procedure $Y_{i,j}$ \> \>
	[Equations \ref{d'i},\ref{d'j},\ref{Psiij},\ref{APsiA}] \\
\> \> \\
\> \> For each $A_{k}$ below $A_{i}$ ($k=i+1,\ldots,M$) \\
\> \> \> Procedure $Z_{i,j,k}$ \>
	[Equations \ref{a'kj-opt},\ref{a'ki-opt}] \\
\> \> EndFor \\
\> \> \\
\> EndFor \\
EndFor 
\end{tabbing}
\caption{Condensed Description of Fast Givens Rotations Algorithm}
\label{givens-short}
\end{algorithm}

A summary of the
data used in the computation and the data changed by each procedure
is presented in Table~\ref{data-used}.
The primes have been dropped from the notation because the
primed variables are moved back into the unprimed variables as soon as all
the computations are completed.

\begin{table}
\begin{center}
\begin{tabular}{||c|c|c||}    \hline
Procedure & Data Used & Data Changed \\  \hline
$W_{i,N}$   & $A_{i}$, \, $D$ &  $A_{i}$, \, $D$, \, $\Psi _{i,N}$	\\
$X_{i,N,k}$ & $A_{k}$, \, $\Psi _{i,N}$	&       $A_{k}$		\\
$Y_{i,j}$     & $A_{i}$, \, $D$	&  $A_{i}$, \, $D$, \, $\Psi _{i,j}$	\\
$Z_{i,j,k}$   & $A_{k}$, \, $\Psi _{i,j}$	&       $A_{k}$		\\
	\hline
\end{tabular}
\end{center}
\caption{Data Used and Changed by Procedures in 
			Algorithm~\protect\ref{givens-short} }
\label{data-used}
\end{table}

From the table, it is apparent that procedure $W_{i,N}$ can be
executed by a cell which stores only $D$ and row $A_{i}$ of matrix $A$.
This cell computes $\Psi _{i,N}$ and communicates it to other cells.

It is also apparent that procedure $X_{i,N,k}$ can be executed by a cell
which can access the rotation matrix $\Psi _{i,N}$ and which stores
only row $A_{k}$ of matrix $A$.  Hence, the procedures $X_{i,N,k}$ 
($i < k \leq M$) can be executed by separate cells in parallel.

The data details for procedures $Y_{i,j}$ and $Z_{i,j,k}$ are similar to
the details for procedures $W_{i,N}$ and $X_{i,N,k}$, respectively.
The only difference is notational, where the rotation matrix
is represented by $\Psi _{i,j}$ rather than $\Psi _{i,N}$.

The above analysis leads to a natural mapping of the algorithm onto a
linear array.  Consider the problem of zeroing row $A_{i}$ of matrix $A$.
What is desired is an array where rows $A_{i}$ through $A_{M}$ are 
stored on a separate cells.  
\footnote{Recall that, in the triangularization algorithm, zeroing
row $A_{i}$ does not affect the rows above it in matrix $A$.  Therefore,
this storage is not considered here.}
Cell $i$ contains
$A_{i}$ and $D$ and performs procedure $W_{i,N}$, computing
$\Psi _{i,N}$ in the process.  Then $\Psi _{i,N}$ is passed to
cells $i$+1 through $M$ so that cell $k$ can appropriately rotate $A_{k}$
using procedure $X_{i,N,k}$.
Subsequently, for each remaining element of $A_{i}$ to be zeroed, 
\begin{enumerate}
\item cell $i$ performs procedure $Y_{i,j}$, 
\item cell $i$ sends $\Psi _{i,j}$ to all cells $k$ ($k=i+1,\ldots,M$), and
\item each cell $k$ performs procedure $Z_{i,j,k}$.
\end{enumerate}

The next step is to extend the above reasoning from the case of zeroing
one row to the case of zeroing all rows (Table~\ref{zero-matrix}).  
The first step of triangularizing
a matrix is zeroing the first row, so the above reasoning applies directly
($i$=1).  Hence, what is required is an array of
$n$+$m$ {\em a-cells}, where {\em a-cell}
$k$ contains row $A_{k}$ of matrix $A$.
Initially, the matrix $D$ is stored on {\em a-cell} 1.  
As described in the previous paragraph, {\em a-cell} 1
performs procedures $W$ and $Y$; {\em a-cells} 2 through $n$+$m$ perform
procedures $X$ and $Z$.  
The subscripts have been dropped for convenience.

\begin{table}
%\scriptsize
%\small
\begin{center}
\begin{tabular}{c|ccccc}
	\hline
Row   & {\em a-cell} 1 & {\em a-cell} 2 & {\em a-cell} 3 & $\cdots$ & 
	 {\em a-cell} $M$ \\ \hline
 1 & $A_{1}$,$D$ & $A_{2}$ & $A_{3}$ & $\cdots$ & 
		 $A_{M}$ \\
      & $W$,$Y$     & $X$,$Z$ & $X$,$Z$ & $\cdots$ & $X$,$Z$ \\
	&&&&& \\
 2 & $A_{1}$ & $A_{2}$,$D$ & $A_{3}$ & $\cdots$ 
		 & $A_{M}$ \\
      &             & $W$,$Y$ & $X$,$Z$ & $\cdots$ &  $X$,$Z$ \\
	&&&&& \\
 3 & $A_{1}$ & $A_{2}$ & $A_{3}$,$D$ & $\cdots$ & 
		 $A_{M}$ \\
      &             &         & $W$,$Y$ & $\cdots$ & $X$,$Z$ \\
  \vdots&&&&& \\
  \vdots&&&&& \\
 $M$-1 & $A_{1}$ & $A_{2}$ & $A_{3}$ & $\cdots$ & 
		 $A_{M}$ \\
      &             &         &  &                 &      $X$,$Z$ \\
        &&&&& \\
 $M$ & $A_{1}$ & $A_{2}$ & $A_{3}$ & $\cdots$ & 
		 $A_{M}$,$D$ \\
      &             &         &  &                 &          $W$,$Y$ \\
		\hline
\end{tabular}
\end{center}
\caption{Data and execution pattern of linear array throughout the
	 fast Givens algorithm.  The first column lists the row currently
	 being zeroed, and the remaining columns show the data stored
	 (first row) and the procedures executed (second row) 
	 on the {\em a-cells} of the array.}
\label{zero-matrix}
\end{table}

Once $A_{1}$ is zeroed, the next step is to zero $A_{2}$.  As shown in 
Table~\ref{zero-matrix}, this requires that {\em a-cell} 2 store matrix $D$.
Therefore, $D$ must be passed to {\em a-cell} 2 by {\em a-cell} 1 
before row $A_{2}$
can be zeroed.  Once this passage is complete, the zeroing process
follows the single row reasoning outlined above ($i$=2).  Hence, 
{\em a-cell} 2 now
performs procedures $W$ and $Y$, and {\em a-cells} 3 through $n$+$m$ perform
procedures $X$ and $Z$.  Since row $A_{1}$
will not be changed by subsequent rotations in the algorithm, {\em a-cell} 1
will be dormant.

This process continues for the zeroing of all rows, as shown in
Table~\ref{zero-matrix}.  Notice that zeroing $A_{n+m}$ does not require
the execution of procedures $X$ and $Z$ (there are no rows in $A$ below
row $A_{n+m}$).  When the triangularization process is complete, the
resulting matrix $A'$ (stored in $A$) is partitioned just as the original
matrix: row $k$ resides on {\em a-cell} $k$.  The new diagonal matrix $D'$ 
(stored in $D$) resides on {\em a-cell} $n$+$m$, 
whereas the initial diagonal matrix resided on {\em a-cell} 1.  
Thus, an algorithm is defined on an $n$+$m$-cell
linear array to compute a unit lower triangular $A'$ and a diagonal $D'$ 
such that Equation~\ref{M-A'D'A'} (repeated here for convenience)
  \[
	  S = A'D'(A')^{T}
  \]
is satisfied.

To set the $A$ matrix for Kalman filtering,
the $i$th {\em a-cell} always contains the following 
matrices:
\begin{center}
\begin{tabular}{rccccccc}
a-cell:	& 1 & 2 & $\cdots$ & $m$ & $m$+1 & $\cdots$ & $m$+$n$		\\
contents:& $Q,R$&&$\cdots$& & $\Phi _{1},G_{1}$ &$\cdots$& $\Phi _{n},G_{n}$,\\
\end{tabular}
\end{center}
where $\Phi _{k}$ and $G_{k}$ represent the $k$th rows of $\Phi$ and $G$,
respectively.  The first {\em a-cell} initializes $D$, so it must contain 
$Q$ and $R$.  Initially, the cells contain the rows of
matrix $L$:
\begin{center}
\begin{tabular}{rccccccc}
a-cell:	& 1 & 2 & $\cdots$ & $m$ & $m$+1 & $\cdots$ & $m$+$n$		\\
contents: & & & $\cdots$ & & $L_{1}$ & $\cdots$ & $L_{n}$,		\\
\end{tabular}
\end{center}
where $L_{k}$ represents the $k$th row of $L$.

To begin the covariance update computation, matrix $H$ is received from
the {\em x-cell} one row at a time such that $H_{k}$, the $k$th row of $H$,
is stored on the $k$th {\em a-cell}.
\begin{displaymath}
\cdots ~H_{2} ~H_{1} \rightarrow \framebox{1} \rightarrow \framebox{2} 
\rightarrow \cdots \rightarrow \framebox{m}
\end{displaymath}
Then the rows of matrix $L$ are distributed to all of the {\em a-cells} so
that the contents of the cells are:
\begin{center}
\begin{tabular}{rccccccc}
a-cell:	& 1 & 2 & $\cdots$ & $m$ & $m$+1 & $\cdots$ & $m$+$n$		\\
contents: & $H_{1},L$ & $H_{2},L$ & $\cdots$ & 
				$H_{m},L$ & $L$ & $\cdots$ & $L$	\\
\end{tabular}
\end{center}
At this point, each cell has all the information it needs to compute its
row of matrix $A$.

Once matrix $A$ is formed, we can triangularize the matrix by performing 
the appropriate fast Givens rotations, and the covariance update is 
complete.  However, it is useful to examine the triangularization process
in two stages:  zeroing the first $m$ rows of $A$ and zeroing the last
$n$ rows of $A$.  After completion of the first stage, the first $m$ rows
and columns of matrix $A$ will not be affected by subsequent rotations.
Since the matrices $L_{e}$ and $K_{t}L_{e}$ 
reside within the first $m$ columns of
the triangularized matrix $A'$, they are completely determined upon completion
of the first stage of the fast Givens process.  Hence, these matrices
may be sent to the {\em x-cell} before the second stage of the 
triangularization is performed.
\begin{displaymath}
L_{e} ~K_{t}L_{e} \leftarrow \framebox{1} \leftarrow
\framebox{2}
\leftarrow \cdots \leftarrow \framebox{n+m}
\end{displaymath}


