M. Cosnard et Em. Daoudi, OPTIMAL-ALGORITHMS FOR PARALLEL GIVENS FACTORIZATION ON A COARSE-GRAINED PRAM, Journal of the Association for Computing Machinery, 41(2), 1994, pp. 399-421
We study the complexity of the parallel Givens factorization of a squa
re matrix of size n on a shared memory architecture composed with p id
entical processors (coarse grained EREW PRAM). We show how to construc
t an asymptotically optimal algorithm. We deduce that the time complex
ity is equal to: T(opt)(p) = n2/2p + p + o(n) for 1 less-than-or-equal
-to p less-than-or-equal-to n/2 + square-root 2 + o(n) and that the mi
nimum number of processors in order to compute the Givens factorizatio
n in asymptotically optimal time (2n + o(n)) is equal to p(opt) = n/(2
+ square-root 2) + o(n). These results complete previous analysis pre
sented in the case where the number of processors is unlimited.