commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Rob Tompkins (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (MATH-1334) Resurrect Dhillon's algorithm for symmetric eigen-decomposition
Date Mon, 10 Apr 2017 14:45:41 GMT

     [ https://issues.apache.org/jira/browse/MATH-1334?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Rob Tompkins updated MATH-1334:
-------------------------------
    Fix Version/s: 4.X

> Resurrect Dhillon's algorithm for symmetric eigen-decomposition
> ---------------------------------------------------------------
>
>                 Key: MATH-1334
>                 URL: https://issues.apache.org/jira/browse/MATH-1334
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.6
>            Reporter: Dario Bahena
>             Fix For: 4.X
>
>
> 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.



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)

Mime
View raw message