Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-1334

Resurrect Dhillon's algorithm for symmetric eigen-decomposition

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: 3.6
    • Fix Version/s: 4.X
    • Labels:
      None

      Description

      Hi everyone,

      From version 2.0 => 2.1, we seem to have replaced the algorithm for calculating the eigen-factorization of symmetric matrices.

      You guys were previously using this specialized algorithm from Mr. Dhillon (plus other stuff):

      "This implementation is based on Inderjit Singh Dhillon thesis A New O(n2) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem, on Beresford N. Parlett and Osni A. Marques paper An Implementation of the dqds Algorithm (Positive Case) and on the corresponding LAPACK routines (DLARRE, DLASQ2, DLAZQ3, DLAZQ4, DLASQ5 and DLASQ6)."

      Javadoc: https://commons.apache.org/proper/commons-math/javadocs/api-2.0/org/apache/commons/math/linear/EigenDecompositionImpl.html

      but mysteriously, they changed the algorithm on version 2.1; and that seems to have started the trend up to current version 3.6:

      "This implementation is based on the paper by A. Drubrulle, R.S. Martin and J.H. Wilkinson 'The Implicit QL Algorithm' in Wilksinson and Reinsch (1971) Handbook for automatic computation, vol. 2, Linear algebra, Springer-Verlag, New-York"

      https://commons.apache.org/proper/commons-math/javadocs/api-2.1/org/apache/commons/math/linear/EigenDecompositionImpl.html
      https://commons.apache.org/proper/commons-math/javadocs/api-3.6/org/apache/commons/math3/linear/EigenDecomposition.html

      I have tested the version 3.6 and 2.0 (with some manual patches you published), and the difference is quite significant. For a symmetric matrix of 867x867, the times following on my laptop:

      3.6: around 14 secs
      2.0: around 3 secs!

      Could we consider bringing back the specialized version for symmetric cases? I sort of feel we lost something here ;-|

      Thanks.

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              dariomx Dario Bahena
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated: