Analysis and design of parallel algorithms and implementations of matrix multiplications for image and signal processing

Parallel matrix multiplication algorithms (based on the common data distribution formats) used in pattern recognition, image processing, and signal processing applications are discussed. A novel algorithm is introduced and is shown to be the fastest one for a determined class of applications. The algorithms are analyzed for performance as a function of array dimension, data distribution formats, and the architecture of the computer upon which the algorithms are executed. Performance bounds and speedups (linear in the number of processors) are established. The results of the analysis are given both as characterizations of executions on selected classes of architectures and also in the form of theorems which establish the relative performance of the algorithms across classes of data distributions and architectures.<>