The Solution of Singular-Value and Symmetric Eigenvalue Problems on Multiprocessor Arrays
SIAM Journal on Scientific and Statistical ComputingPublished 1 January 1985
Richard P. Brent, Franklin T. Luk
Citations308
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Parallel Jacobi-like algorithms are presented for computing a singular-value decomposition of an $(m \geqq n) matrix and an eigenvalue decompositions of an $n \times n$ symmetric matrix.
Abstract
Parallel Jacobi-like algorithms are presented for computing a singular-value decomposition of an $m \times n$ matrix $(m \geqq n)$ and an eigenvalue decomposition of an $n \times n$ symmetric matrix. A linear array of $O(n)$ processors is proposed for the singular-value problem; the associated algorithm requires time $O(mnS)$, where S is the number of sweeps (typically $S \leqq 10$). A square array of $O(n^2 )$ processors with nearest-neighbor communication is proposed for the eigenvalue problem; the associated algorithm requires time $O(nS)$.
Keywords
Computer ScienceEngineering
IEEE Transactions on Acoustics Speech and Signal ProcessingSingular value decompositions and digital image processing
366 Citations1976Harry Andrews, Claude L. Patterson
Analysis and methods for obtaining a pseudoinverse of separable space variant point spread functions (SVPSF's) are presented with a variety of object and imaging system dagradations.
Journal of the Society for Industrial and Applied MathematicsInversion of Matrices by Biorthogonalization and Related Results
245 Citations1958Magnus R. Hestenes
Transactions of the American Mathematical SocietyThe cyclic Jacobi method for computing the principal values of a complex matrix
241 Citations1960George E. Forsythe, Peter Henrici
Mathematics of ComputationOn Jacobi and Jacobi-like algorithms for a parallel computer
138 Citations1971Ahmed Sameh
SIAM Journal on Scientific and Statistical ComputingNumerically Stable Solution of Dense Systems of Linear Equations Using Mesh-Connected Processors
94 Citations1984Adam W. Bojańczyk, Richard P. Brent +1 more
A multiprocessor structure for solving a dense system of n linear equations that is well suited for VLSI implementation as identical processors with a simple and regular interconnection pattern are required.
SIAM Journal on Scientific and Statistical ComputingSystolic Networks for Orthogonal Decompositions
67 Citations1983Don Heller, Ilse C. F. Ipsen
An orthogonally connected systolic array, consisting of a few types of simple processors, is constructed to perform the QR decomposition of a matrix and application is made to solution of linear systems and linear least squares problems as well asQL and LQ factorizations.
ACM Transactions on Mathematical SoftwareComputing the Singular-Value Decomposition on the ILLIAC IV
63 Citations1980Franklin T. Luk
A one-sided orthogonalization method is presented which makes very efficient use of the parallel computing abilities of the ILLIAC machine and is shown to be Jacobi-like and numerically stable.
Journal of the Society for Industrial and Applied MathematicsOn Cyclic Jacobi Methods
60 Citations1963Eldon Hansen
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Computation Of The Generalized Singular Value Decomposition Using Mesh-Connected Processors</title>
31 Citations1983Richard P. Brent, Franklin T. Luk +1 more
Numerical algorithms for both one-and two-dimensional systolic architectures are discussed and the syStolic array computation of the generalized singular value decomposition is discussed.
eCommons (Cornell University)Some Linear-Time Algorithms for Systolic Arrays
30 Citations1983Richard P. Brent, H. T. Kung +1 more
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Parallel Computation of Eigenvalues of Real Matrices
30 Citations1971David J. Kuck, Ahmed Sameh
The implementation of three standard matrix eigenvalue computation methods on an array machine with high efficiency is described, including Jacobi and Householder algorithms for real symmetric matrices, and the QR algorithm for real nonsymmetricMatrices.
eCommons (Cornell University)A Systolic Architecture for Almost Linear-Time Solution of the Symmetric Eigenvalue Problem
23 Citations1982Richard P. Brent, Franklin T. Luk
An algorithm is presented for computing the eigenvalues and eigenvectors of an n x n real symmetric matrix using a Jacobi method implemented on a two-dimensional systolic array of processors with nearest-neighbor communication between processors.
eCommons (Cornell University)A Systolic Architecture for the Singular Value Decomposition
16 Citations1982Richard P. Brent, Franklin T. Luk
A systolic architecture for computing a singular value decomposition of an m x n matrix, where m \geq n, is proposed, which is stable and requires only $O(mn)$ time on a linear array of O(n) processors.