\section{Square Root Filter on Linear Array}

The problem of interest is systematic design of parallel square root     
Kalman filtering algorithms for a linear array of computational cells.  
For our purposes, a linear array is a collection of separately 
programmable cells, each of which communicates with at most two other
cells.  Linear
arrays have traditionally been applied to regular and uniform computations.
For example, efficient parallel algorithms are known for vector-matrix
multiplications and matrix-matrix multiplications.
The problem of interest here is the mapping of an irregular and non-uniform
computation with specific structure onto a linear array.  

A high-level diagram of a linear array for the filtering algorithm is given
in Figure~\ref{sqr-array}.  The boxes represent computational cells and
the arrows represent unidirectional buffered communication cells.
The measurement vector ${\bf y}_{t}$ arrives from an
unspecified host along the upper channel, and the updated state vector
${\bf \hat{x}}_{t+1}$ is sent back to the host along the lower channel.  The
algorithm uses $n$+$m$+1 computational cells, where $n$+$m$ {\em a-cells}
perform the combined covariance update and a single {\em x-cell} performs
the combined state update.  The details of the mapping are discussed in
reference \cite{itzkowitz}.  
%  The update algorithms are described in the sections below.

\begin{figure}
\setlength{\unitlength}{0.175in}
\begin{center}
\begin{picture}(20,5)(1,0)
\scriptsize
\put(5,1){\framebox(2,2){\em x-cell}}
\put(8,1){\framebox(2,2){\shortstack{{\em a-cell}\\{\em 1}}}}
\put(11,1){\framebox(2,2){\shortstack{{\em a-cell}\\{\em 2}}}}
\put(14,1){\makebox(2,2){$\cdots$}}
\put(17,1){\framebox(2,2){\shortstack{{\em a-cell}\\{\em n+m}}}}
\put(3,2.5){\vector(1,0){2}}
\put(5,1.5){\vector(-1,0){2}}
\put(4,3.1){\makebox(0,0){${\bf y}_{t}$}}
\put(4,1.1){\makebox(0,0){${\bf \hat{x}}_{t+1}$}}
\multiput(7,2.5)(3,0){4}{\vector(1,0){1}}
\multiput(8,1.5)(3,0){4}{\vector(-1,0){1}}
\end{picture}
\end{center}
\caption{High-level View of Linear Array}
\label{sqr-array}
\end{figure}


\input{map-covariance}
\input{map-state}


