Jacobi SVD algorithm implementation

Question

Is this implementation of Jacobi SVD algorithm according to the standard algorithm? Please verify.

Is this Hestenes Jacobi method?

I have seen pseudo code of Jacobi algorithm like here which appears quite different from how it is done here. I want to know Is this the best implementation or can it be made more efficient?

Answer 1

In 1975 I published a one-sided Jacobi code in the Computer Journal. Seymour Shlien and I extended this in the same journal in 1987. It is also used in a rather different way for long, skinny matrices in an Applied Statistics paper in 1976, and both were part of my 1979 Compact Numerical Methods for Computers, republished in 1990. There have been other approaches (2 sided, variants for parallel computing, etc.) but the original code, updated in a few small ways, is still very short and appears to be adaptable for extended precision. In 2019, I've made a few more improvements, as it appears NASA is using it for a situation needing such precision, and I've worked out how to avoid requiring the user to provide tolerances.

As far as I am aware (from asking around over the years), Hestenes may never have actually run his method as a program. Chartres said he did some experiments on the Silliac. However, my step-and-description and BASIC and Fortran codes of the 1970s were, I think, the first transferable technology for the one-sided Jacobi. By then the faster but more complicated Golub and Reisch code had been widely adopted, and mine was used for special applications. Also when being able to tinker easily was desired.

John Nash

Answer 2

The Hestenes method for computing the SVD applies orthogonal transformations from the left (alternatively, from right). Thus, it is often known as the One Sided Jacobi Method. The paper by Hestenes is the primary reference for One Sided Jacobi methods.

The original Jacobi method for the symmetric eigenvalue problem uses the same transformation from the left and the right to keep the matrix symmetric (which is not required in SVD computations). The direct extension of the Jacobi method for the SVD is called the Kogbetliantz method or the Double-Sided Jacobi SVD method. Please use these keywords in google scholar (or in a similar database) to find the citations (there are many).

Hestenes method is suitable for parallel computers while Jacobi methods became popular in the 1980's due to systolic array chips and computers. Jacobi methods could give more accurate results but they are generally slow.