Abstract
In this paper, we present an algorithm for the reduction to block upper-Hessenberg form which can be used to solve the nonsymmetric eigenvalue problem on message-passing multicomputers. On such multicomputers, a nonsymmetric matrix can be distributed across processing nodes logically configured into a two-dimensional mesh using the block-cyclic data distribution. Based on the matrix partitioning and mapping, the algorithm employs both Householder reflectors and Givens rotations within each reduction step. We analyze the arithmetic and communication complexities and describe the implementation details of the algorithm on message-passing multicomputers. We discuss two different implementations - synchronous and asynchronous - and present performance results on the Intel iPSC/860 and DELTA. We conclude with an evaluation of the algorithm's communication cost, and suggest areas for further improvement.
| Original language | English |
|---|---|
| Pages (from-to) | 1189-1211 |
| Number of pages | 23 |
| Journal | Parallel Computing |
| Volume | 21 |
| Issue number | 8 |
| DOIs | |
| State | Published - Aug 1995 |
Funding
* This work is funded in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract DE-AC05840R21400, by the Defense Advanced Research Projects Agency under contract DAALO3-91-C-0047, administered by the Army Research Office, and by the National Science Foundation Science and Technology Center Cooperative Agreement No. CCR-8809615. * Corresponding author. Email: [email protected]
| Funders | Funder number |
|---|---|
| National Science Foundation Science and Technology Center | |
| Office of Energy Research | |
| U.S. Department of Energy | DE-AC05840R21400 |
| Army Research Office | |
| Defense Advanced Research Projects Agency | DAALO3-91-C-0047 |
Keywords
- Distributed-memory multiprocessors
- Hessenberg form
- Linear algebra
- Nonsymmetric eigenvalue problem