Computation of the Singular Value Decomposition Using Mesh-Connected Processors
eCommons (Cornell University)Published 1 March 1983Open access
Richard P. Brent, Franklin T. Luk, Charles Van Loan
Citations181
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
A cyclic Jacobi method for computing the singular value decomposition of an $mxn$ matrix $(m \geq n)$ using systolic arrays is proposed.
Abstract
A cyclic Jacobi method for computing the singular value decomposition of an $mxn$ matrix $(m \\geq n)$ using systolic arrays is proposed. The algorithm requires $O(n^{2})$ processors and $O(m + n \\log n)$ units of time.
Keywords
Computer ScienceEngineering
Journal of the Society for Industrial and Applied Mathematics Series B Numerical AnalysisCalculating the Singular Values and Pseudo-Inverse of a Matrix
1,773 Citations1965Gene H. Golub, W. Kahan
The use of the pseudo-inverse $A^I = V\Sigma ^I U^* $ to solve least squares problems in a way which dampens spurious oscillation and cancellation is mentioned.
Lecture notes in computer scienceMatrix Eigensystem Routines — EISPACK Guide Extension
507 Citations1977B. S. Garbow, J. M. Boyle +2 more
The EISPACK subroutines and the handbook Algol procedures are compared to show the similarities and differences in execution times, as well as the differences in documentation and source listings.
SIAM Journal on Scientific and Statistical ComputingThe Solution of Singular-Value and Symmetric Eigenvalue Problems on Multiprocessor Arrays
308 Citations1985Richard P. Brent, Franklin T. Luk
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.
Transactions of the American Mathematical SocietyThe cyclic Jacobi method for computing the principal values of a complex matrix
241 Citations1960George E. Forsythe, Peter Henrici
ACM Transactions on Mathematical SoftwareAn Improved Algorithm for Computing the Singular Value Decomposition
238 Citations1982Tony F. Chan
An improved version of the original GR-SVD algorithm is presented, which works best for matrices with m >> n, but is more efficient even when m is only slightly greater than n and in some cases can achieve as much as 50 percent savings.
Mathematics of ComputationOn Jacobi and Jacobi-like algorithms for a parallel computer
138 Citations1971Ahmed Sameh
Journal of the Society for Industrial and Applied MathematicsOn Cyclic Jacobi Methods
60 Citations1963Eldon Hansen
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Optimizing synchronous systems
49 Citations2018Charles E. Leiserson, James B. Saxe
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
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Systolic Array Computation Of The Singular Value Decomposition</title>
16 Citations1982Alan Finn, Franklin T. Luk +1 more
The mapping of the algorithms to the architecture of a specific architecture of the singular value decomposition is demonstrated and the algorithms and architecture together have been verified by functional level and register transfer level simulation.
Linear or square array for eigenvalue and singular value decompositions
3 Citations1983S. Y. Kung, R. J. Gal-Ezer
The QR algorithm can be regarded as the best sequential algorithm available to date because it repeatedly applies a complicated similarity transformation to the result of the previous transformation, thereby producing a sequence of matrices that converges to a diagonal form.