<div dir="ltr">Interesting performance comparison<div><br></div><div> Matt</div><div><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Jack Poulson</b> <span dir="ltr"><<a href="mailto:jack.poulson@gmail.com">jack.poulson@gmail.com</a>></span><br>Date: Fri, Jun 24, 2016 at 9:09 PM<br>Subject: [<a href="mailto:dev@libelemental.org">dev@libelemental.org</a>] (Sequential) templated Aggressive Early Deflation implementations<br>To: "dev@ >> Elemental [<a href="mailto:dev@libelemental.org">dev@libelemental.org</a>]" <<a href="mailto:dev@libelemental.org">dev@libelemental.org</a>><br>Cc: Tim Moon <<a href="mailto:tym1@stanford.edu">tym1@stanford.edu</a>><br><br><br>As of the following commit [1], Elemental has highly configurable [2]<br>
sequential implementations of classical and Aggressive Early Deflation<br>
Hessenberg QR algorithms [3] for the datatypes:<br>
<br>
float, Complex<float>,<br>
double, Complex<double>,<br>
DoubleDouble, Complex<DoubleDouble>,<br>
QuadDouble, Complex<QuadDouble>,<br>
Quad, Complex<Quad>,<br>
BigFloat, and Complex<BigFloat>.<br>
<br>
You can find a test driver (which also compares performance to LAPACK<br>
where possible) here [4]. A few performance corners still need to be<br>
rounded for small matrices (especially those just over the minimum AED<br>
threshold), perhaps in relation to avoiding excessive amounts of dynamic<br>
memory allocation, but the performance results for float and double are<br>
otherwise already competitive.<br>
<br>
It is interesting to measure the number of total iterations and runtime<br>
as the precision increases:<br>
<br>
poulson@poulson-ASUS:~/Source/Internal/Elemental/build$<br>
./bin/tests/lapack_like/HessenbergEig --n 200 --progress false<br>
<SNIP><br>
Testing uniform Hessenberg with float<br>
|| H ||_F = 81.7146<br>
LAPACK HessenbergSchur: 0.194949 seconds<br>
HessenbergQR: 0.10685 seconds<br>
Convergence achieved after 20 iterations<br>
|| H Z - Z T ||_F / || H ||_F = 2.41023e-06<br>
Testing uniform Hessenberg with double<br>
|| H ||_F = 82.0872<br>
LAPACK HessenbergSchur: 0.323781 seconds<br>
HessenbergQR: 0.175237 seconds<br>
Convergence achieved after 28 iterations<br>
|| H Z - Z T ||_F / || H ||_F = 7.14399e-15<br>
Testing uniform Hessenberg with Quad<br>
|| H ||_F = 8.231285e+01<br>
HessenbergQR: 11.4225 seconds<br>
Convergence achieved after 35 iterations<br>
|| H Z - Z T ||_F / || H ||_F = 7.596771e-33<br>
Testing uniform Hessenberg with DoubleDouble<br>
|| H ||_F = 8.218725e+01<br>
HessenbergQR: 3.40876 seconds<br>
Convergence achieved after 37 iterations<br>
|| H Z - Z T ||_F / || H ||_F = 7.129923e-30<br>
Testing uniform Hessenberg with QuadDouble<br>
|| H ||_F = 8.231451e+01<br>
HessenbergQR: 36.6103 seconds<br>
Convergence achieved after 45 iterations<br>
|| H Z - Z T ||_F / || H ||_F = 2.253974e-62<br>
Testing uniform Hessenberg with BigFloat<br>
|| H ||_F =<br>
82.3543043527144891509930917502847910735381397998167359073550861836927365335936<br>
HessenbergQR: 84.1473 seconds<br>
Convergence achieved after 46 iterations<br>
|| H Z - Z T ||_F / || H ||_F =<br>
7.91113813616780539739514751118499399272008582155767435672044799364497357463225e-76<br>
<SNIP><br>
<br>
There is obviously a lot of work left to do (e.g., distributed versions<br>
of the above, and similar implementations for the symmetric tridiagonal<br>
EVP and bidiagonal SVD), but this is an important step forward for the<br>
library. And it couples nicely with the high-performance pseudospectral<br>
and triangular eigensolver work Tim Moon and I have been working<br>
together on (which should hit arXiv soon).<br>
<br>
Jack<br>
<br>
[1]<br>
<a href="https://github.com/elemental/Elemental/commit/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d" rel="noreferrer" target="_blank">https://github.com/elemental/Elemental/commit/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d</a><br>
<br>
[2]<br>
<a href="https://github.com/elemental/Elemental/blob/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/include/El/lapack_like/spectral.hpp#L369" rel="noreferrer" target="_blank">https://github.com/elemental/Elemental/blob/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/include/El/lapack_like/spectral.hpp#L369</a><br>
<br>
[3]<br>
<a href="https://github.com/elemental/Elemental/tree/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/src/lapack_like/spectral/HessenbergSchur" rel="noreferrer" target="_blank">https://github.com/elemental/Elemental/tree/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/src/lapack_like/spectral/HessenbergSchur</a><br>
<br>
[4]<br>
<a href="https://github.com/elemental/Elemental/blob/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/tests/lapack_like/HessenbergSchur.cpp" rel="noreferrer" target="_blank">https://github.com/elemental/Elemental/blob/a95d62152fb9eb25dfdbc67e24097108cd5f9d7d/tests/lapack_like/HessenbergSchur.cpp</a><br>
</div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>-- Norbert Wiener</div>
</div></div>