A flexible multicomputer algorithm for elementary matrix operations

In the present study we introduce and test a new flexible multicomputer (FM) algorithm for matrix calculations on a distributed memory computer. The FM-algorithm also performs matrix addition, subtraction, and scalar multiplication on both dense and sparse matrices. The FM-algorithm was designed to meet the need for a high-performance flexible software tool for implementing different parallel optimization algorithms. Special consideration has been taken to ensure the usability and portability of the algorithm. A preliminary flexibility test is conducted on an IBM SP2 (Cactus) machine. On the principal level, we will compare the FM-algorithm with another high-performance algorithm Summa and look at an improvement of Summa by combining it with the Strassen algorithm. On the empirical level, we will compare a chained version of the FM-algorithm with the parallel ScaLAPACK code in a set of huge matrix multiplications on a Cray T3E machine. Our results demonstrate that the FM-algorithm performs as well as the parallel ScaLAPACK code for dense matrices. FM is fully scalable for large, sparse matrices. The FM-algorithm is efficient with respect to sequential matrix multiplication. In contrast to ScaLAPACK, the fully scalable FM-algorithm is independent of mesh structure. Arbitrarily large matrices can be processed with a single processor.