TY - JOUR

T1 - Solving the generalized eigenvalue problem on a synchronous linear processor array

AU - Boley, Daniel

PY - 1986/5

Y1 - 1986/5

N2 - 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.

AB - 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.

KW - Linear algebra

KW - MIMD computer

KW - generalized eigenvalue problem

KW - parallel algorithm

KW - synchronous linear processor array

UR - http://www.scopus.com/inward/record.url?scp=0022720005&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022720005&partnerID=8YFLogxK

U2 - 10.1016/0167-8191(86)90032-3

DO - 10.1016/0167-8191(86)90032-3

M3 - Article

AN - SCOPUS:0022720005

VL - 3

SP - 153

EP - 166

JO - Parallel Computing

JF - Parallel Computing

SN - 0167-8191

IS - 2

ER -