## Abstract

This paper describes a prototype parallel algorithm for approximating eigenvalues of a dense nonsymmetric matrix on a linear, synchronous processor array. The algorithm is parallel implementation of the explicitly-shifted QR, employing n distributed-memory processors to deliver all eigenvalues in O(n^{2}) time. The algorithm uses Givens rotations to generate a series of unitary similarity transformations. The rotations are passed between neibouring processors and applied, in pipeline fashion, to columns of the matrix. The rotations are also accumulated in a unitary transformation matrix, enabling the solution of eigenvectors via back-substitution and back-transformation. The algorithm involves only local communication, and confronts the problems of convergence, splitting and updating the shift in a pipelined scheme. The algorithm is implemented on a hypercube, using a ring of processors to simulate a systolic array. Experimental results on the NCUBE/seven hypercube show O(n) speedup over competing sequential codes, despite the overhead of interprocessor communication. Speedup and efficiency are estimated by comparing with EISPACK performance.

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

Pages (from-to) | 61-70 |

Number of pages | 10 |

Journal | Computer Physics Communications |

Volume | 53 |

Issue number | 1-3 |

DOIs | |

State | Published - May 1989 |

### Bibliographical note

Funding Information:* This research was partially supported by NSF grants DCR 8420935 and DCR-8519029 and by the Minnesota Super-computer Institute,