Details

    • Type: Improvement Improvement
    • Status: Open
    • Priority: Minor Minor
    • Resolution: Unresolved
    • Affects Version/s: 2.0, 2.1
    • Fix Version/s: None
    • Labels:

      Description

      There has been a lot of recent activity on the SVD algorithm for Commons Math. The SVD has also been in the news lately because of the development of a new algorithm that is both faster and more accurate than previous algorithms. Given the importance of the SVD in many applications it would be useful to have a Java implementation of this new algorithm in Commons Math.

      News article on the new algorithm:
      http://www.siam.org/pdf/news/1696.pdf

      Manuscripts on the new algorithm:
      http://www.netlib.org/lapack/lawnspdf/lawn169.pdf
      http://www.netlib.org/lapack/lawnspdf/lawn170.pdf

      Implementation in LAPACK 3.2.1
      dgesvj.f

        Activity

        Bruce A Johnson created issue -
        Hide
        Phil Steitz added a comment -

        Anyone interested in implementing this? Should we move this to the wishlist?

        Show
        Phil Steitz added a comment - Anyone interested in implementing this? Should we move this to the wishlist?
        Phil Steitz made changes -
        Field Original Value New Value
        Affects Version/s 2.1 [ 12313444 ]
        Affects Version/s 2.0 [ 12312686 ]
        Hide
        Bruce A Johnson added a comment -

        Wish list is OK with me, though I'd love to see it implemented. I added it because it seemed an important enough advance that it ought to be noted somewhere in Commons Math project so developers were aware of it. Unfortunately, I have at present, neither the time, nor probably the expertise, to implement it.

        Bruce

        Show
        Bruce A Johnson added a comment - Wish list is OK with me, though I'd love to see it implemented. I added it because it seemed an important enough advance that it ought to be noted somewhere in Commons Math project so developers were aware of it. Unfortunately, I have at present, neither the time, nor probably the expertise, to implement it. Bruce
        Luc Maisonobe made changes -
        Fix Version/s 3.0 [ 12314824 ]
        Hide
        Christopher Nix added a comment -

        I've been having a think about this, though I'm far from an expert.

        My understanding is as follows: The implementation in question applies the Jacobi method to a matrix that has been pre-conditioned by QR-decomposition (with perhaps an additional LQ-factorisation of the resulting R factor). This gains a good start to the Jacobi method by localizing the Frobenius norm close to the diagonal.

        There are some clever steps in the analysis of the intermediate matrices as the Jacobi method converges that I don't yet understand. However, as a starter, it seems that an implementation of a Jacobi rotation and LQ-factorisation would be useful.

        I will gladly have a crack at these parts, since I can't spot anything sufficient within the package at this time to do these things.

        Any comments?

        Chris

        Show
        Christopher Nix added a comment - I've been having a think about this, though I'm far from an expert. My understanding is as follows: The implementation in question applies the Jacobi method to a matrix that has been pre-conditioned by QR-decomposition (with perhaps an additional LQ-factorisation of the resulting R factor). This gains a good start to the Jacobi method by localizing the Frobenius norm close to the diagonal. There are some clever steps in the analysis of the intermediate matrices as the Jacobi method converges that I don't yet understand. However, as a starter, it seems that an implementation of a Jacobi rotation and LQ-factorisation would be useful. I will gladly have a crack at these parts, since I can't spot anything sufficient within the package at this time to do these things. Any comments? Chris
        Hide
        Luc Maisonobe added a comment -

        I didn't read the algorithm yet. However, I think any step forward to have at least a stable SVD implementation is a good thing. Also Jacobi rotation and LQ-factorization are probably interesting on their own.

        Show
        Luc Maisonobe added a comment - I didn't read the algorithm yet. However, I think any step forward to have at least a stable SVD implementation is a good thing. Also Jacobi rotation and LQ-factorization are probably interesting on their own.
        Hide
        Luc Maisonobe added a comment -

        Do we consider that this issue is superseded by MATH-611 that was recently solved ?

        Show
        Luc Maisonobe added a comment - Do we consider that this issue is superseded by MATH-611 that was recently solved ?
        Hide
        Bruce A Johnson added a comment -

        I would consider the issue of having a good SVD algorithm in Commons Math solved by MATH-611 so this issue shouldn't hold up a 3.0 release. Longer term it may still be desirable to have the Jacobi based method present. I'm curious how far Christopher Nix got in implementing it.

        Show
        Bruce A Johnson added a comment - I would consider the issue of having a good SVD algorithm in Commons Math solved by MATH-611 so this issue shouldn't hold up a 3.0 release. Longer term it may still be desirable to have the Jacobi based method present. I'm curious how far Christopher Nix got in implementing it.
        Hide
        Christopher Nix added a comment -

        I have a partial implementation that is still missing some pre-processing to improve performance. Currently, it fails to beat the JAMA code, hence my patch on MATH-611. I don't believe that the performance of my code can be improved to beat JAMA, though I am willing to continue development slow time.

        If I understand correctly, the algorithm in question is not necessarily the best SVD algorithm available, it merely pushes the boundaries of what Jacobi methods for SVD are capable of achieving compared to, say, bi- or tri-diagonalisation methods.

        I would certainly not regard this as 'Major' issue anymore. I could pursue development further if it is considered useful to have another implementation within ACM (raising a new issue later if required to submit).

        Chris.

        Show
        Christopher Nix added a comment - I have a partial implementation that is still missing some pre-processing to improve performance. Currently, it fails to beat the JAMA code, hence my patch on MATH-611 . I don't believe that the performance of my code can be improved to beat JAMA, though I am willing to continue development slow time. If I understand correctly, the algorithm in question is not necessarily the best SVD algorithm available, it merely pushes the boundaries of what Jacobi methods for SVD are capable of achieving compared to, say, bi- or tri-diagonalisation methods. I would certainly not regard this as 'Major' issue anymore. I could pursue development further if it is considered useful to have another implementation within ACM (raising a new issue later if required to submit). Chris.
        Hide
        Bruce A Johnson added a comment -

        Hi Chris,

        Thanks for the update. I'm happy now that you've done the JAMA code. If there is not a clear benefit of the Jacobi method then it shouldn't be a priority. At this point, I personally am more interested in seeing an implementation of SVD for complex matrices, but that may not be of relevance to many others.

        Bruce

        Show
        Bruce A Johnson added a comment - Hi Chris, Thanks for the update. I'm happy now that you've done the JAMA code. If there is not a clear benefit of the Jacobi method then it shouldn't be a priority. At this point, I personally am more interested in seeing an implementation of SVD for complex matrices, but that may not be of relevance to many others. Bruce
        Hide
        Phil Steitz added a comment -

        If we do decide to add another impl or enhance SVD further, this can wait until 3.1

        Show
        Phil Steitz added a comment - If we do decide to add another impl or enhance SVD further, this can wait until 3.1
        Phil Steitz made changes -
        Fix Version/s 3.1 [ 12317576 ]
        Fix Version/s 3.0 [ 12314824 ]
        Hide
        Gilles added a comment -

        As there are more no bug reports on the current SVD implementation, this issue is not high priority.

        Show
        Gilles added a comment - As there are more no bug reports on the current SVD implementation, this issue is not high priority.
        Gilles made changes -
        Fix Version/s 3.1 [ 12317576 ]
        Priority Major [ 3 ] Minor [ 4 ]

          People

          • Assignee:
            Unassigned
            Reporter:
            Bruce A Johnson
          • Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

            • Created:
              Updated:

              Development