A Parallel Ring Ordering Algorithm for Efficient One-Sided Jacobi SVD Computations

✍ Scribed by B.B. Zhou; R.P. Brent

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 141 KB
• Volume: 42
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1304

✦ Synopsis

In this paper we give evidence to show that in one-sided Jacobi SVD computation the sorting of column norms in each sweep is very important. An efficient parallel ring Jacobi ordering for computing singular value decomposition is described. This ordering can generate n(n -1)/2 different index pairs and sort column norms at the same time. The one-sided Jacobi SVD algorithm using this parallel ordering converges in about the same number of sweeps as the sequential cyclic Jacobi algorithm. The issue of equivalence of orderings for one-sided Jacobi is also discussed. We show how an ordering which does not sort column norms into order may still perform efficiently as long as it can generate the same index pairs at the same step as one which does sorting. Some experimental results on a Fujitsu AP1000 are presented.