An Optimal Algorithm for Gaussian Elimination of Band Matrices on a MIMD System

Abstract

This paper is concerned with determining an optimal number of processors in MIMD system, for LU decomposition of band matrix with a + b - 1 diagonals using Gaussian method of elimination. The obtained result represents the solution of general problem since band matrices with arbitrary number of diagonals were considered. Task scheduling algorithm is given and proved that it is optimal. We introduce orthogonal multiprocessor system with two-dimensional memory organization with r < 16 32/bit processors and r(r-1)/2 shared memory modules. The unique feature of the proposed system lies in this conflict/free access to shared memory modules.