commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dario Bahena (JIRA)" <>
Subject [jira] [Commented] (MATH-1334) Resurrect Dhillon's algorithm for symmetric eigen-decomposition
Date Wed, 09 Mar 2016 16:56:40 GMT


Dario Bahena commented on MATH-1334:

Sure. I just made a quick adaptation to make it work on 3.6 code base and run my experiment,
but agree an official patch should aim for cleaner integration.

I will email that list asking for the reason of the algorithm change indeed; as you suggested,
that may be the main point to discuss here.


> Resurrect Dhillon's algorithm for symmetric eigen-decomposition
> ---------------------------------------------------------------
>                 Key: MATH-1334
>                 URL:
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.6
>            Reporter: Dario Bahena
> 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
> "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
> Javadoc:
> 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"
> 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

View raw message