research-article

A Proof of Convergence for Two Parallel Jacobi SVD Algorithms

Authors:

F. T. Luk,

H. ParkAuthors Info & Claims

IEEE Transactions on Computers, Volume 38, Issue 6

Pages 806 - 811

https://doi.org/10.1109/12.24289

Published: 01 June 1989 Publication History

Publisher Site

Abstract

The authors consider two parallel Jacobi algorithms, due to R.P. Brent et al. (J. VLSI Comput. Syst., vol.1, p.242-70, 1985) and F.T. Luk (1986 J. Lin. Alg. Applic., vol.77, p.259-73), for computing the singular value decomposition of an n*n matrix. By relating the algorithms to the cyclic-by-rows Jacobi method, they prove convergence of the former for odd n and of the latter for any n. The authors also give a nonconvergence example for the former method for all even n 4.

References

[1]

{1} R. P. Brent and F. T. Luk, "The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays," SIAM J. Sci. Statist. Comput. , vol. 6, pp. 69-84, 1985.

Digital Library

Google Scholar

[2]

{2} R. P. Brent, F. T. Luk, and C. F. Van Loan, "Computation of the singular value decomposition using mesh-connected processors," J. VLSI Comput. Syst. , vol. 1, pp. 242-270, 1985.

Google Scholar

[3]

{3} G. E. Forsythe and P. Henrici, "The cyclic Jacobi method for computing the principal values of a complex matrix," Trans. Amer. Math. Soc. , vol. 94, pp. 1-23, 1960.

Crossref

Google Scholar

[4]

{4} W. M. Gentleman, "Error analysis of QR decompositions by Givens transformations," J. Lin. Alg. Appl. , vol. 10, pp. 189-197, 1975.

Crossref

Google Scholar

[5]

{5} E. R. Hansen, "On cyclic Jacobi methods," J. SIAM , vol. 11, pp. 448-459, 1963.

Google Scholar

[6]

{6} F. T. Luk, "A triangular processor array for computing singular values," J. Lin. Alg. Appl. , vol. 77, pp. 259-273, 1986.

Crossref

Google Scholar

[7]

{7} F. T. Luk and H. Park, "On parallel Jacobi orderings," SIAM J. Sci. Statist. Comput. , vol. 10, pp. 18-26, 1989.

Digital Library

Google Scholar

[8]

{8} J. J. Modi and J. D. Pryce, "Efficient implementation of Jacobi's diagonalization method on the DAP," Numer. Math. , vol. 46, pp. 443-454, 1985.

Digital Library

Google Scholar

[9]

{9} H. Park, "On the equivalence and convergence of parallel Jacobi SVD algorithms," Ph.D. dissertation, Dep. Comput. Sci., Cornell Univ., 1987.

Crossref

Google Scholar

[10]

{10} A. Sameh, "Solving the linear least squares problem on a linear array of processors," in Algorithmically Specialized Parallel Computers , L. Snyder, L. Jamieson, D. Gannon, and H. Siegel, Eds. New York: Academic, 1985, pp. 191-200.

Google Scholar

[11]

{11} U. Schwiegelshohn and L. Thiele, "A systolic array for cyclic-by-rows Jacobi algorithms," J. Parallel Distrib. Comput. , vol. 4, pp. 334- 340, 1987.

Digital Library

Google Scholar

[12]

{12} G. W. Stewart, "A Jacobi-like algorithm for computing the Schur decomposition of a non-Hermitian matrix," SIAM J. Sci. Statist. Comput. , vol. 6, pp. 853-864, 1985.

Digital Library

Google Scholar

[13]

{13} J. J. Symanski, "Architecture of the systolic linear algebra parallel processor," in Real Time Signal Processing IX , W. J. Miceli, Ed., Proc. SPIE , vol. 698, 1986, pp. 17-22.

Google Scholar

[14]

{14} R. A. Whiteside, N. S. Ostlund, and P. G. Hibbard, "A parallel Jacobi diagonalization algorithm for a loop multiple processor system," IEEE Trans. Comput. , vol. C-33, pp. 409-413, 1984.

Google Scholar

Cited By

View all

Hari V(2021)On the global convergence of the block Jacobi method for the positive definite generalized eigenvalue problemCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-021-00415-858:2Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10092-021-00415-8
Huang RYu TLiu SZhang XZhao Y(2021)A Batched Jacobi SVD Algorithm on GPUs and Its Application to Quantum Lattice SystemsParallel and Distributed Computing, Applications and Technologies10.1007/978-3-030-96772-7_7(69-80)Online publication date: 17-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-96772-7_7
Okša GYamamoto YBečka MVajteršic M(2018)Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matricesBIT10.1007/s10543-018-0711-358:4(1099-1123)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10543-018-0711-3
Show More Cited By

Index Terms

A Proof of Convergence for Two Parallel Jacobi SVD Algorithms

Recommendations

Convergence to Singular Triplets in the Two-Sided Block-Jacobi SVD Algorithm with Dynamic Ordering

We study the convergence of computed quantities to singular triplets in the serial and parallel block-Jacobi singular value decomposition (SVD) algorithm with dynamic ordering. After eliminating possible zero singular values by two finite decompositions of ...
On iterative QR pre-processing in the parallel block-Jacobi SVD algorithm

An efficient version of the parallel two-sided block-Jacobi algorithm for the singular value decomposition of an mxn matrix A includes the pre-processing step, which consists of the QR factorization of A with column pivoting followed by the optional LQ ...
An Efficient Jacobi-Like Algorithm for Parallel Eigenvalue Computation

A very fast Jacobi-like algorithm for the parallel solution of symmetric eigenvalue problems is proposed. It becomes possible by not focusing on the realization of the Jacobi rotation with a CORDIC processor, but by applying approximate rotations and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 38, Issue 6

June 1989

170 pages

ISSN:0018-9340

Editor:
M. T. Liu
Ohio State Univ., Columbus

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 June 1989

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hari V(2021)On the global convergence of the block Jacobi method for the positive definite generalized eigenvalue problemCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-021-00415-858:2Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10092-021-00415-8
Huang RYu TLiu SZhang XZhao Y(2021)A Batched Jacobi SVD Algorithm on GPUs and Its Application to Quantum Lattice SystemsParallel and Distributed Computing, Applications and Technologies10.1007/978-3-030-96772-7_7(69-80)Online publication date: 17-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-96772-7_7
Okša GYamamoto YBečka MVajteršic M(2018)Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matricesBIT10.1007/s10543-018-0711-358:4(1099-1123)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10543-018-0711-3
Rapetti LCrivellaro SDe Momi EFerrigno GNiederberger CLuciano CFjeld MFratarcangeli MSjölie DStaadt OUnger J(2017)Virtual reality navigation system for prostate biopsyProceedings of the 23rd ACM Symposium on Virtual Reality Software and Technology10.1145/3139131.3139162(1-4)Online publication date: 8-Nov-2017
https://dl.acm.org/doi/10.1145/3139131.3139162
Torun MYilmaz OAkansu A(2016)FPGA, GPU, and CPU implementations of Jacobi algorithm for eigenanalysisJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.05.01496:C(172-180)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.05.014
Hari V(2015)Convergence to diagonal form of block Jacobi-type methodsNumerische Mathematik10.1007/s00211-014-0647-8129:3(449-481)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00211-014-0647-8
Singer SSinger SNovaković VUšćumlić ADunjko V(2012)Novel modifications of parallel Jacobi algorithmsNumerical Algorithms10.1007/s11075-011-9473-659:1(1-27)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1007/s11075-011-9473-6
Park HHari V(1993)A real algorithm for the Hermitian eigenvalue decompositionBIT10.1007/BF0199035133:1(158-171)Online publication date: 1-Mar-1993
https://dl.acm.org/doi/10.1007/BF01990351
Bunse-Gerstner AFassbender H(1991)On the Generalized Schur Decomposition of a Matrix Pencil for Parallel ComputationSIAM Journal on Scientific and Statistical Computing10.5555/3037621.303762212:4(911-939)Online publication date: 1-Jul-1991
https://dl.acm.org/doi/10.5555/3037621.3037622
Park HEwerbring L(1991)An algorithm for the generalized singular value decomposition on massively parallel computersProceedings of the 5th international conference on Supercomputing10.1145/109025.109065(136-145)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/109025.109065
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Convergence to Singular Triplets in the Two-Sided Block-Jacobi SVD Algorithm with Dynamic Ordering

On iterative QR pre-processing in the parallel block-Jacobi SVD algorithm

An Efficient Jacobi-Like Algorithm for Parallel Eigenvalue Computation

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations