# commons-dev mailing list archives

##### Site index · List index
Message view
Top
From "Tyler Ward (JIRA)" <j...@apache.org>
Subject [jira] Commented: (MATH-157) Add support for SVD.
Date Thu, 02 Nov 2006 01:35:17 GMT
```    [ http://issues.apache.org/jira/browse/MATH-157?page=comments#action_12446421 ]

Tyler Ward commented on MATH-157:
---------------------------------

I think I see the confusion. Take a look at my first comment here. You don't want to invert
(or find eigenvectors of) the original matrix. Say the original matrix is A (and A` is A-transpose,
with row and column labels flipped), which is NxM (N > M), you want to construct eigenvectors
for...

B = A`A [NxN square symmetric matrix]

You can do most of this by performing a QR decomposition on B, and then producing T = QBQ`.
Unfortunately, T is not diagonal, it will be tridiagonal (three rows of values), so you need
to reduce it the rest of the way to diagonal form by multiplying by a matrix P.

Finding which matrix does this however is a chore, it requires givens reductions, explained
above. In the end, you want to produce a matrix P such that D = PQBQ`P` is diagonal. This
should be reversible, B = Q`P`DPQ should be the B you started with. If you can do that, then
you're  home free, just a few matrix multiplications will finish the job.

When you get to the step of needing givens reductions, let me know. I can probably give you
some formulas and such that will make it really easy. If you let me know how you're doing
with this, I can definitely help. I can't however contribute code (work forbids it), but I
can help a lot with anything else, even formulas.

So I'd say try this. Use the QR decomposition they already have to get to the point of being
able to produce T, and reverse T to get the B that you started with. Do that, and I can give
you a PDF that will make the givens step very easy, it's really only a couple dozen lines
of code, but requires some care that I can walk you through.

> --------------------
>
>                 Key: MATH-157
>                 URL: http://issues.apache.org/jira/browse/MATH-157
>             Project: Commons Math
>          Issue Type: New Feature
>            Reporter: Tyler Ward
>         Attachments: svd.tar.gz
>
>
> SVD is probably the most important feature in any linear algebra package, though also
one of the more difficult.
> In general, SVD is needed because very often real systems end up being singular (which
can be handled by QR), or nearly singular (which can't). A good example is a nonlinear root
finder. Often the jacobian will be nearly singular, but it is VERY rare for it to be exactly
singular. Consequently, LU or QR produces really bad results, because they are dominated by
rounding error. What is needed is a way to throw out the insignificant parts of the solution,
and take what improvements we can get. That is what SVD provides. The colt SVD algorithm has
a serious infinite loop bug, caused primarily by Double.NaN in the inputs, but also by underflow
and overflow, which really can't be prevented.
> If worried about patents and such, SVD can be derrived from first principals very easily
with the acceptance of two postulates.
> 1) That an SVD always exists.
> 2) That Jacobi reduction works.
> Both are very basic results from linear algebra, available in nearly any text book. Once
that's accepted, then the rest of the algorithm falls into place in a very simple manner.

--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-