[petsc-dev] Fwd: [dev at libelemental.org] (Sequential) templated Aggressive Early Deflation implementations

[Matthew Knepley]

Interesting performance comparison

  Matt

---------- Forwarded message ----------
From: Jack Poulson <jack.poulson at gmail.com>
Date: Fri, Jun 24, 2016 at 9:09 PM
Subject: [dev at libelemental.org] (Sequential) templated Aggressive Early
Deflation implementations
To: "dev@ >> Elemental ‎[dev at libelemental.org]‎" <dev at libelemental.org>
Cc: Tim Moon <tym1 at stanford.edu>


As of the following commit [1], Elemental has highly configurable [2]
sequential implementations of classical and Aggressive Early Deflation
Hessenberg QR algorithms [3] for the datatypes:

float, Complex<float>,
double, Complex<double>,
DoubleDouble, Complex<DoubleDouble>,
QuadDouble, Complex<QuadDouble>,
Quad, Complex<Quad>,
BigFloat, and Complex<BigFloat>.

You can find a test driver (which also compares performance to LAPACK
where possible) here [4]. A few performance corners still need to be
rounded for small matrices (especially those just over the minimum AED
threshold), perhaps in relation to avoiding excessive amounts of dynamic
memory allocation, but the performance results for float and double are
otherwise already competitive.

It is interesting to measure the number of total iterations and runtime
as the precision increases:

poulson at poulson-ASUS:~/Source/Internal/Elemental/build$
./bin/tests/lapack_like/HessenbergEig --n 200 --progress false
<SNIP>
Testing uniform Hessenberg with float
|| H ||_F = 81.7146
LAPACK HessenbergSchur: 0.194949 seconds
HessenbergQR: 0.10685 seconds
Convergence achieved after 20 iterations
|| H Z - Z T ||_F / || H ||_F = 2.41023e-06
Testing uniform Hessenberg with double
|| H ||_F = 82.0872
LAPACK HessenbergSchur: 0.323781 seconds
HessenbergQR: 0.175237 seconds
Convergence achieved after 28 iterations
|| H Z - Z T ||_F / || H ||_F = 7.14399e-15
Testing uniform Hessenberg with Quad
|| H ||_F = 8.231285e+01
HessenbergQR: 11.4225 seconds
Convergence achieved after 35 iterations
|| H Z - Z T ||_F / || H ||_F = 7.596771e-33
Testing uniform Hessenberg with DoubleDouble
|| H ||_F = 8.218725e+01
HessenbergQR: 3.40876 seconds
Convergence achieved after 37 iterations
|| H Z - Z T ||_F / || H ||_F = 7.129923e-30
Testing uniform Hessenberg with QuadDouble
|| H ||_F = 8.231451e+01
HessenbergQR: 36.6103 seconds
Convergence achieved after 45 iterations
|| H Z - Z T ||_F / || H ||_F = 2.253974e-62
Testing uniform Hessenberg with BigFloat
|| H ||_F =
82.3543043527144891509930917502847910735381397998167359073550861836927365335936
HessenbergQR: 84.1473 seconds
Convergence achieved after 46 iterations
|| H Z - Z T ||_F / || H ||_F =
7.91113813616780539739514751118499399272008582155767435672044799364497357463225e-76
<SNIP>

There is obviously a lot of work left to do (e.g., distributed versions
of the above, and similar implementations for the symmetric tridiagonal
EVP and bidiagonal SVD), but this is an important step forward for the
library. And it couples nicely with the high-performance pseudospectral
and triangular eigensolver work Tim Moon and I have been working
together on (which should hit arXiv soon).

Jack

[1]
https://github.com/elemental/Elemental/commit/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d

[2]
https://github.com/elemental/Elemental/blob/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/include/El/lapack_like/spectral.hpp#L369

[3]
https://github.com/elemental/Elemental/tree/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/src/lapack_like/spectral/HessenbergSchur

[4]
https://github.com/elemental/Elemental/blob/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/tests/lapack_like/HessenbergSchur.cpp



-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20160624/84c1353b/attachment.html>