SOLVING TRIDIAGONAL LINEAR SYSTEMS ON MIMD COMPUTERS

A partitioning algorithm for solving tridiagonal system of linear equations which is suitable for implementation on multiprocessor systems with small to moderate number of processors is described in this paper. The method is based on decomposing a matrix of order n×n into p partitions of size n×k, where n=pk. The fundamental idea of the proposed algorithm is that the elimination is performed using alternatively superdiagonal and subdiagonal elements, contrary to the Gaussian elimination which uses main diagonal elements. Performance results obtained when the proposed algorithm is implemented on the p-processor orthogonal and linear arrays, both of MIMD type, are presented.