## Abstract

This paper proposes a few lower bounds for communication complexity of the Gaussian elimination algorithm on multiprocessors. Three types of architectures are considered: a bus architecture, a nearest neighbor ring network, and a nearest neighbor grid network. It is shown that for the bus and the ring architectures, the minimum communication time is O(N^{2}), independent of the number of processors, while for the grid it is reduced to O(k^{ built-1 2}N^{2})+O(k^{ built1 2}N) for a lock step Gaussian elimination algorithm, and to O(k^{ built-1 2}N^{2})+O(k^{ built1 2}) for any pipelined Gaussian elimination algorithm, where k is the total number of processors. The practical implications of these bounds are discussed.

Original language | English (US) |
---|---|

Pages (from-to) | 315-340 |

Number of pages | 26 |

Journal | Linear Algebra and Its Applications |

Volume | 77 |

Issue number | C |

DOIs | |

State | Published - May 1986 |

### Bibliographical note

Funding Information:*Revised version. Original version issued as Research Report YALEU/DCS/RR-348, January 1985. This work was supported in part by ONR grant NOO014-82.Kal84 and in part by a joint study with IBM/Kingston.