×
Luk, Franklin T.

A triangular processor array for computing singular values. (English) Zbl 0587.65028

Linear Algebra Appl. 77, 259-273 (1986).
A triangular processor array for computing the singular values of an \(m\times n\) (m\(\geq n)\) matrix is proposed. A Jacobi-type algorithm is used to first triangularize the given matrix and then diagonalize the resultant triangular form. The requirements are \((1/4)n^ 2+O(n)\) processors and \(O(m+nS)\) time, where S denotes the number of sweeps. The ”triangular” array can be extended to a ”rectangular” one with \(mn+O(m)\) processors for the computation of singular vectors.

Cited in 1 Review
Cited in 18 Documents

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices

Keywords:

QR decomposition; singular values; Jacobi-type algorithm

Software:

LINPACK
Cite Review PDF
Full Text: DOI

References:

[1] Ahmed, H. M.; Delosme, J.-M.; Morf, M., Highly concurrent computing structures for matrix arithmetic and signal processing, Computer, 15, 1, 65-82 (Jan. 1982)
[2] Bojanczyk, A.; Brent, R. P.; Kung, H. T., Numerically stable solution of dense systems of linear equations using mesh-connected processors, SIAM J. Sci. Statist. Comput., 5, 95-104 (1984) · Zbl 0574.65020
[3] Brent, R. P.; Luk, F. T., The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays, SIAM J. Sci. Statist. Comput., 6, 69-84 (1985) · Zbl 0575.65027
[4] R.P. Brent, F.T. Luk, and C. Van Loan, Computation of the singular value decomposition using mesh-connected processors, J. VLSI Computer Systems; R.P. Brent, F.T. Luk, and C. Van Loan, Computation of the singular value decomposition using mesh-connected processors, J. VLSI Computer Systems · Zbl 0597.65029
[5] Bromley, K.; Speiser, J. M., Signal processing algorithms, architectures, and application, Tutorial 31. Tutorial 31, SPIE 27th Annual Internat. Symp. (Aug. 1983), San Diego, Calif.
[6] Chan, T. F., An improved algorithm for computing the singular value decomposition, ACM Trans. Math. Software, 8, 72-83 (1982) · Zbl 0477.65032
[7] Dongarra, J. J.; Moler, C. B.; Bunch, J. R.; Stewart, G. W., LINPACK User’s Guide (1979), SIAM: SIAM Philadelphia
[8] Finn, A. M.; Luk, F. T.; Pottle, C., Systolic array computation of the singular value decomposition, Real-Time Signal Processing V. Real-Time Signal Processing V, Proc. SPIE, Vol. 341, 35-43 (1982)
[9] Gentleman, W. M.; Kung, H. T., Matrix triangularization by systolic arrays, Real Time Signal Processing IV. Real Time Signal Processing IV, Proc. SPIE, Vol. 298, 19-26 (1981)
[10] Golub, G. H.; Luk, F. T., Singular value decomposition: applications and computation, Transactions of the 22nd Conference of Army Mathematicians. Transactions of the 22nd Conference of Army Mathematicians, ARO Report 77-1, 577-605 (1977)
[11] Golub, G. H.; Loan, C. Van, Matrix Computations (1983), Johns Hopkins Press: Johns Hopkins Press Baltimore · Zbl 0559.65011
[12] Heller, D. E.; Ipsen, I. C.F., Systolic networks for orthogonal equivalence transformations and their applications, (Proceedings of the 1982 Conference on Advanced Research in VLSI (Jan. 1982), MIT: MIT Cambridge, Mass), 113-122
[13] Heller, D. E.; Ipsen, I. C.F., Systolic networks for orthogonal decompositions, SIAM J. Sci. Statist. Comput., 4, 261-269 (1983) · Zbl 0532.65029
[14] Johnsson, L., A computational array for the QR-method, (Proceedings of the 1982 Conference on Advanced Research in VLSI (Jan. 1982), MIT: MIT Cambridge, Mass), 123-129
[15] Luk, F. T., Computing the singular-value decomposition on the ILLIAC IV, ACM Trans. Math. Software, 6, 524-539 (1980) · Zbl 0471.65019
[16] F.T. Luk, A rotation method for computing the QR-decomposition, SIAM J. Sci. Statist. Comput.; F.T. Luk, A rotation method for computing the QR-decomposition, SIAM J. Sci. Statist. Comput. · Zbl 0616.65045
[17] O’Leary, D. P.; Stewart, G. W., Data-flow algorithms for parallel matrix computations, Commun. ACM, 28, 840-853 (1985) · Zbl 0606.65029
[18] Sameh, A. H., On Jacobi and Jacobi-like algorithms for a parallel computer, Math. Comp., 25, 579-590 (1971) · Zbl 0222.65046
[19] Sameh, A. H., Solving the linear least squares problem on a linear array of processors, W. Lafayette, Indiana. W. Lafayette, Indiana, Proceedings of the Purdue Workshop on Algorithmically-Specialized Computer Organization (Sept. 1982.)
[20] Schreiber, R., A systolic architecture for singular value decomposition, Paris, France. Paris, France, Proceedings of the 1st International Colloquium on Vector and Parallel Computation in Scientific Application, 143-148 (Mar. 1983)
[21] Schreiber, R., On the systolic arrays of Brent, Luk, and Van Loan, Real-Time Signal Processing VI. Real-Time Signal Processing VI, Proc. SPIE, Vol. 431, 72-76 (1983)
[22] G.W. Stewart, A Jacobi-like algorithm for computing the Schur decomposition of a non-Hermitian matrix, SIAM J. Sci. Statist. Comput.; G.W. Stewart, A Jacobi-like algorithm for computing the Schur decomposition of a non-Hermitian matrix, SIAM J. Sci. Statist. Comput. · Zbl 0601.65024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.