SingularValueDecomposition

[Tyler Ward <wa...@gmail.com>]

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

Re: [math] Re: SingularValueDecomposition

[Simon Kitching <sk...@apache.org>]

On Mon, 2006-07-17 at 06:50 +0200, Luc Maisonobe wrote:
> Tyler Ward wrote :
> > 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?
> 
> By the way, could you add [math] as a marker in your subject for this 
> list (I forgot to fix it in my previous mail, sorry). The list is shared 
> among a lot of projects, so these markers help filtering the messages 
> for all subscribers.

And just as a reminder, the Apache Software Foundation is very careful
to respect copyrights, so any contribution of this sort cannot be based
on code published under another license. Hopefully most core math
algorithm can be implemented from the theory without great problems, but
copying code fragments from a textbook, etc. can be problematic I
believe.

I'll leave it up to the core maths people to determine what's ok.

Regards,

Simon



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org

[math] Re: SingularValueDecomposition

[Luc Maisonobe <Lu...@free.fr>]

Tyler Ward wrote :
> 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?

By the way, could you add [math] as a marker in your subject for this 
list (I forgot to fix it in my previous mail, sorry). The list is shared 
among a lot of projects, so these markers help filtering the messages 
for all subscribers.

Luc

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org

Re: SingularValueDecomposition

[Luc Maisonobe <Lu...@free.fr>]

Tyler Ward wrote :
> 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?

As far as I am concerned, yes.

> More specifically, the householder transformation is absolutely naieve,

Perhaps we should have a look to the various Householder transforms 
implementations we have. One has been added recently, one is hiding 
underneath the Levenberg-Marquardt algorithm in Mantissa to be added 
soon (I hope), and one is now provided by you. Some generalization 
around these three implementations may be worth a try.

Luc

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org