𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Impact of communications on the complexity of the Parallel Gaussian Elimination

✍ Scribed by E. Bampis; J.C. Konig; D. Trystram

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
275 KB
Volume
17
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents an extension to the complexity analysis of parallel algorithms on MIMD computers with a shared-memory system which takes into account communications. This analysis shows that the well-known asymptotically optimal results are insufficient because we show that the overhead is in O(n3). The optimal parallel time with O(n) processors is only O(n2). The new scheduling algorithm that we have proposed in this paper reduces the overhead to only O(n z) with the same parallel time.

πŸ“œ SIMILAR VOLUMES

Parallelization of the Gaussian Eliminat
Parallelization of the Gaussian Elimination Algorithm on Systolic Arrays
✍ J-C. Bermond; C. Peyrat; I. Sakho; M. TchuentΓ© πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 284 KB

Step 2: combination for elimination of the a i,k 's for Therefore the algorithm is the following (the a k,k 's are supposed nonzero

The Communication Complexity of Enumerat
The Communication Complexity of Enumeration, Elimination, and Selection
✍ Andris Ambainis; Harry Buhrman; William Gasarch; Bala Kalyanasundaram; Leen Tore πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 278 KB

Let k, n Β₯ N and f: {0, 1} n Γ— {0, 1} n Q {0, 1}. Assume Alice has x 1 , ..., x k Β₯ {0, 1} n , Bob has y 1 , ..., y k Β₯ {0, 1} n , and they want to compute municating as few bits as possible. The direct sum conjecture (henceforth DSC) n (log log(n))(log(n)) ) bits. This establishes a weak randomize