SVD Woes

[Keith Nicewarner]

Not sure if anyone reads this list, but since I've noticed a steady increase in the
number of downloads, I thought I should at least give a heads up.

I'm not at all happy with the current SVD algorithm.  It doesn't converge when
there's a clear solution (and other apps like MATLAB converge no problem).
I think this is because svdcmp is old NR code that was designed for single-
precision math.  dsvdcmp (the double-precision version that I use) does nothing
more than replace "float" with "double" so the algorithm is still the same.  Yet they
are now testing for convergence using a double precision epsilon (DBL_EPSILON),
which is *very* tiny!

So I've looked around for another algorithm, and found one.  Ironically, it's from
a package also named LinAlg -- no relation, though!  :-)  This is freely available
from netlib.org, but it appears to have not changed since 1998, which means to
me it's probably no longer supported.  I'm not crazy about the matrix "stream"
concept that dominates the library -- which appears to do nothing more than
obfuscate the code.  But it does have an SVD algorithm.

I plan to adapt the SVD algorithm to my classes.  This change should occur in the
next week or so ...

Keith Nicewarner.

[Keith Nicewarner]

I've released 1.1.1 which now uses the new SVD algorithm.  I've also added better
testing to measure how good the SVD algorithm is.  The new one isn't as accurate
as the old one, but it converges faster.  I doubt anyone will notice the lower
accuracy, but if you do, let me know.

Keith Nicewarner.

[Michael Loehr]

Greeting Kieth;

I downloaded V 1.1.2 and had some dificulties with the compile.

Firstly the .dsw & .dsp files are in linux format and must be converted to dos format (CR/LF).  Opening in PFE32 and then save as with the dos format clicked works fine.

The test project doesn't create the test files for the svd or linalg tests.  I've split the .dsp into individual .dsp for each of the tests and the compile proceeds (minor edits).

Here's my output from the svd test:

E:\gts\linalg-1.1.2\msvc\test\Release>testsvd
Number of Iterations = 1000
max SVD residual = 0.000361101
max inv residual = 0.000361101

E:\gts\linalg-1.1.2\msvc\test\Release>testsvd
Number of Iterations = 10000
max SVD residual = 0.000430394
max inv residual = 0.000430394

E:\gts\linalg-1.1.2\msvc\test\Release>testsvd
Number of Iterations = 1
max SVD residual = 8.91206e-005
max inv residual = 8.91206e-005

E:\gts\linalg-1.1.2\msvc\test\Release>testsvd
Number of Iterations = 100000
max SVD residual = 0.000556589
max inv residual = 0.0243913

I made small changes to output the iterations and I adjusted the number of iterations and recompiled for each run.

It would appear that the algorithm still diverges.

Any thoughts?

Thanks for a great package.

Mike

[Keith Nicewarner]

Thanks for the comments on running under Windows.  I admit that I don't test on
Windows as much as Linux, which you could probably tell ... ;-)

Anyway, about the DOS/UNIX format, I'll double-check how I built the tar ball.
I might need to create a separate file for Windows and UNIX.  But I never had
to do that in the past (or with my other package tuoml).  Very strange ...

As for your residual, that's a far smaller residual than with the older SVD.
But regardless of SVD algorithms, some matrices are just ill-behaved.
You may have just hit on a really singular case.  It may be interesting to
see the matrix for that case to see what the issue is.  If you have access
to MATLAB or Mathematica, it'd be interesting to feed that matrix in and
see what they do with it.

Thanks for your interest,
Keith.