A parallel algorithm for computing the generalized singular value decomposition (Q1325981)

The paper describes a parallel algorithm for computing the generalized singular value decomposition of two squared matrices of order \(n\). The generalized singular value decomposition problem is a generalization of the singular value decomposition problem in that if the second matrix is the identity one, then the generalized problem of the two matrices is the singular value decomposition problem of the first matrix. The algorithm is divided into two stages: preprocessing of the matrices by computation of their trapezoidal form, and the parallel computation of the generalized singular value decomposition of their upper trapezoidal matrices. The described algorithm is designed for efficient implementation on distributed-memory parallel computer architectures and requires only a single triangular array of processors via message passing that is capable of performing all required matrix computations. Sections 1 presents the mathematical problem. Section 2 describes the parallel computation of the QR decomposition with column pivoting to reducing a general matrix to upper trapezoidal form. Section 4 reviews the parallel Kogbetliantz algorithm. Section 5 describes the parallel direct generalized singular value decomposition algorithm. Section 6 discusses the implementation of processors via message passing on a triangular network. The time cost is \(O(n^ 2)\) units for parallel preprocessing, and \(O(n^ 2/p)\) units for the decomposition of two upper trapezoidal matrices, where \(p\) is the dimension of the triangular array of processors.