search

elemental / Elemental

Distributed-memory, arbitrary-precision, dense and sparse-direct linear algebra, conic optimization, and lattice reduction
Other
504 stars 111 forks source link

HJLS and PSLQ support #130

Open poulson opened 8 years ago

poulson commented 8 years ago

Now that Elemental supports searching for (integer) relations using LLL and/or BKZ, it would make sense to implement the HJLS and/or PSLQ algorithms. There is some contention as to whether or not these algorithms are distinct [1], but it would appear that the latter is more accurate when using finite-precision arithmetic.

[1] http://perso.ens-lyon.fr/damien.stehle/downloads/PSLQHJLS.pdf

poulson commented 8 years ago

Also, for the sake of making the historical connection, the need for higher-precision within PSLQ appears to be one of the reasons that Bailey et al. wrote their higher-precision arithmetic packages (with QD also incorporating techniques from the code of Briggs and Kahan).