PARALLELIZATION OF THE GAUSSIAN-ELIMINATION ALGORITHM ON SYSTOLIC ARRAYS

We study the parallel implementation of the Gaussian elimination schem e on systolic arrays. We first show that the time (resp. area) complex ity of the algorithm is T = 3n - 1 (resp. S = (n(2)/4) + O(n)), where n is the size of the linear system. Then we exhibit three algorithms. The two first ones are optimal in time. The first one corresponds to a n orthogonally connected array of size 3(n(2)/8) + O(n). The second ne twork is smaller, S = 3(n(2)/10) + O(n), but two layers are necessary in order to obtain a regular layout with local communications. The thi rd one is hexagonally connected, has size (n(2)/3) + O(n), and is almo st optimal in time. (C) 1996 Academic Press, Inc.