Jc. Bermond et al., PARALLELIZATION OF THE GAUSSIAN-ELIMINATION ALGORITHM ON SYSTOLIC ARRAYS, Journal of parallel and distributed computing, 33(1), 1996, pp. 69-75
Citations number
12
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.