You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Christopher Nix (JIRA)" <ji...@apache.org> on 2011/07/06 10:30:16 UTC
[jira] [Created] (MATH-611) A fast and stable SVD implementation
from JAMA
A fast and stable SVD implementation from JAMA
----------------------------------------------
Key: MATH-611
URL: https://issues.apache.org/jira/browse/MATH-611
Project: Commons Math
Issue Type: Improvement
Affects Versions: 3.0, Nightly Builds
Reporter: Christopher Nix
Fix For: 3.0, Nightly Builds
Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-611) A fast and stable SVD implementation
from JAMA
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13060433#comment-13060433 ]
Mikkel Meyer Andersen commented on MATH-611:
--------------------------------------------
Thanks a lot for adding this. I think that we should document in the comments to the code that it is based on JAMA.
We could maybe also contact JAMA and inform about our considerations of adopting/using the code. I can see that the last version is from 2005, but bugs might still be reported, and it would be great to benefit from this. And users of JAMA might also benefit from future improvements made by us.
Have you made any comparison with the existing in regards to speed?
Cheers, Mikkel.
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MATH-611) A fast and stable SVD
implementation from JAMA
Posted by "Mikkel Meyer Andersen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13060433#comment-13060433 ]
Mikkel Meyer Andersen edited comment on MATH-611 at 7/6/11 9:24 AM:
--------------------------------------------------------------------
Thanks a lot for adding this. I think that we should document in the comments to the code that it is based on JAMA.
We could maybe also contact JAMA and inform about our considerations of adopting/using the code. I can see that the last version is from 2005, but bugs might still be reported, and it would be great to benefit from this. And users of JAMA might also benefit from future improvements made by us. What do you think about this?
Have you made any comparison with the existing in regards to speed?
Cheers, Mikkel.
was (Author: mikl):
Thanks a lot for adding this. I think that we should document in the comments to the code that it is based on JAMA.
We could maybe also contact JAMA and inform about our considerations of adopting/using the code. I can see that the last version is from 2005, but bugs might still be reported, and it would be great to benefit from this. And users of JAMA might also benefit from future improvements made by us.
Have you made any comparison with the existing in regards to speed?
Cheers, Mikkel.
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-611) A fast and stable SVD implementation
from JAMA
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13064704#comment-13064704 ]
Luc Maisonobe commented on MATH-611:
------------------------------------
This looks good to me.
Many, many thanks for this much needed patch!
My only minor comment would be to replace the two occurrences of
double eps = FastMath.pow(2.0, -52.0);
and one occurrence of
double tiny = FastMath.pow(2.0, -966.0);
by static constants initialized using the power of two literal notation:
private static final EPS = 0x1.0p-52;
private static final TINY = 0x1.0p-966;
We should have looked back at JAMA earlier. We only used the principles of the API (using interfaces and extended it slightly), but not using the code was a mistake I should probably be blamed for.
Mikkel, do you want to commit this ?
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java, SingularValueDecompositionImpl.patch
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-611) A fast and stable SVD implementation
from JAMA
Posted by "Christopher Nix (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13060478#comment-13060478 ]
Christopher Nix commented on MATH-611:
--------------------------------------
With regard to speed, I've tried it on random arrays with up to 1,000,000 elements and it's definitely faster than the current SVD implementation.
The current SVD implementation is noticeably slowed by the implementations of AbstractRealMatrix and TriDiagonalTransformer that use setEntry and getEntry on matrices within loops. As such, matrix indices are checked to be in bounds at every iteration of a loop, when what we really should do is check the max and min indices only, if at all. (I've a further patch yet to submit on this).
If we remove the use of getEntry and setEntry in methods called by the current SVD implementation, and instead use direct array access, then the speed of the current implementation is improved significantly, however the stability remains unchanged. Even with this change, the JAMA code is about twice as fast to converge (according to my profiler) and it is demonstrably more accurate.
Chris.
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MATH-611) A fast and stable SVD implementation
from JAMA
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe resolved MATH-611.
--------------------------------
Resolution: Fixed
Fixed in subversion repository as of r1148714.
Thanks for the patch.
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java, SingularValueDecompositionImpl.patch
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-611) A fast and stable SVD implementation
from JAMA
Posted by "Christopher Nix (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Christopher Nix updated MATH-611:
---------------------------------
Attachment: SingularValueDecompositionImpl.patch
I have attached a patch file for the JAMA implementation, together with unit tests for MATH-327, MATH-465 and MATH-583.
Additionally, I have removed the unit test testMatricesValues1 that tested an implementation specific return value of getU() and getV().
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java, SingularValueDecompositionImpl.patch
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-611) A fast and stable SVD implementation
from JAMA
Posted by "Christopher Nix (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Christopher Nix updated MATH-611:
---------------------------------
Attachment: SingularValueDecompositionImpl.java
JAMA code wrapped into Commons Math API.
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-611) A fast and stable SVD implementation
from JAMA
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13062840#comment-13062840 ]
Phil Steitz commented on MATH-611:
----------------------------------
There is no problem incorporating JAMA code. We have already done this. I am +1 to replace SVD with this, assuming we can construct (and pass) unit tests demonstrating that it resolves the open SVD issues.
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MATH-611) A fast and stable SVD
implementation from JAMA
Posted by "Christopher Nix (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-611?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13060405#comment-13060405 ]
Christopher Nix edited comment on MATH-611 at 7/6/11 8:34 AM:
--------------------------------------------------------------
Attached SingularValueDecomposition.java containing JAMA code wrapped into Commons Math API.
was (Author: joubert):
JAMA code wrapped into Commons Math API.
> A fast and stable SVD implementation from JAMA
> ----------------------------------------------
>
> Key: MATH-611
> URL: https://issues.apache.org/jira/browse/MATH-611
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0, Nightly Builds
> Reporter: Christopher Nix
> Labels: patch
> Fix For: 3.0, Nightly Builds
>
> Attachments: SingularValueDecompositionImpl.java
>
>
> Common numerical stability issues with the current SVD implementation, ie MATH-327, MATH-383, MATH-465, MATH-583 can all be solved by co-opting JAMA code that is within the public domain.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira