Solving the generalized eigenvalue problem on a synchronous linear processor array

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We present a parallel method to solve the generalized eigenvalue problem on a linear array of processors, each connected to their nearest neighbors and operating synchronously. We also include a wrap-around connection from end to end. Our method is based on the well-known QZ algorithm of Moler and Stewart, which simultaneously reduces two n × n matrices to upper triangular form by orthogonal or unitary transformations. We show how this algorithm may be partitioned and distributed of n + 1 processors, achieving a speed-up over the serial algorithm of O(n). We use the concept of windows to describe the action of each processor at each step. We show how to incorporate singles shifts, and how to apply orthogonal plane rotations on either side of a matrix without the need to transpose the matrix itself.

Original languageEnglish (US)
Pages (from-to)153-166
Number of pages14
JournalParallel Computing
Issue number2
StatePublished - May 1986


  • Linear algebra
  • MIMD computer
  • generalized eigenvalue problem
  • parallel algorithm
  • synchronous linear processor array


Dive into the research topics of 'Solving the generalized eigenvalue problem on a synchronous linear processor array'. Together they form a unique fingerprint.

Cite this