SOLVING THE GENERALIZED EIGENVALUE PROBLEM ON A SYNCHRONOUS LINEAR PROCESSOR ARRAY

作     者：BOLEY, D 

作者机构：Computer Science Department University of Minnesota Minneapolis MN 55455 U.S.A. 

出 版 物：《PARALLEL COMPUTING》 (并行计算)

年 卷 期：1986年第3卷第2期

页      面：153-166页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：generalized eigenvalue problem Linear algebra MIMD computer parallel algorithm synchronous linear processor array 

摘      要：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.