The least squares estimate detailed in [6] assumes that the observations of the GMRF image obey the model

where is a zero mean correlated noise sequence with variance and correlation with the following structure:

The conditional distribution is given in (11). Then, for , the LSE are:

where is the complete set of pixels, and toroidal wrap-around is assumed.

For an image of size , step 1.1 has a computational complexity of O parallel steps and a communication complexity of O . Step 1.2 runs in O parallel steps. Step 3 takes O parallel steps. Steps 2 and 4 contain a reduction over the entire array, specifically, finding the sum of the elements in a given parallel variable. As this is a scan operation, we refer the reader to Subsection 2.4\ for algorithm analysis. Thus, step 2 runs is O computational parallel steps with O communications, and steps 4 and 6 run in O parallel steps with O

communications. Solving the linear system of equations in step 5 takes O computational steps.

The computational complexity of the Least Squares Estimator for an image of size is

and the communication complexity is

using processors.

David A. Bader

dbader@umiacs.umd.edu