A parallel algorithm for computing the generalized singular value decomposition
type: Item
instance of: scholarly article
title: A parallel algorithm for computing the generalized singular value decomposition
zbMATH Open document ID: 0797.65038
author: Zhaojun Bai
published in: Journal of Parallel and Distributed Computing
publication date: 1994-10-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 567835
zbMATH Keywords: parallel algorithm
zbMATH Keywords: generalized singular value decomposition
zbMATH Keywords: preprocessing
zbMATH Keywords: trapezoidal form
zbMATH Keywords: parallel computation
zbMATH Keywords: distributed-memory parallel computer architectures
zbMATH Keywords: QR decomposition
zbMATH Keywords: Kogbetliantz algorithm
reviewed by: Dana Petcu
MaRDI profile type: Publication
full work available at URL: jpdc.1994.1027
OpenAlex ID: W1980138050
DOI: 10.1006/JPDC.1994.1027
description: scientific article; zbMATH DE number 567835