commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Tyler Ward" <ward.ty...@gmail.com>
Subject SingularValueDecomposition
Date Mon, 17 Jul 2006 03:28:58 GMT
Hi guys, I haven't sent mail to this list before. I've noticed that apache
doesn't have an SVD algorithm, so I put one together. Are you guys
interested?

This is entirely of my creation, I didn't copy or examine code from
anywhere. I wrote all the transformations by hand just browsing through
linear algebra sites on the web, and you'll see that the code is obviously
original. I'm willing to assign the copyrights and all that.

More specifically, the householder transformation is absolutely naieve, so
it takes something like N^4 time. There are improvements, but I thought we
could start with an implementation, then make optimizations later. The
Givens rotations I wrote up myself, and as they're much simpler, I also put
together an optimized version by just multiplying out by hand, so those are
pretty good.

The code is organized into a few classes.

1) Symmetric to tridiagonal decomposer.
2) Tridiagonal to diagonal decomposer.
3) Symmetric Eigenvalue decomposer (just does the naieve symmetric ->
tridiagonal -> diagonal for now, should add some inverse iteration to refine
numbers and remove rounding errors in the future.)
4) SVD decomposer (Computes At * A, computes eigenvectors (V), computes
singular values (w), then right multiplies A twice against vTranspose and
w^-1 to produce U.

Anyway, Interested?


-Tyler

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message