OPTIMAL-ALGORITHMS FOR PARALLEL GIVENS FACTORIZATION ON A COARSE-GRAINED PRAM

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.