Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
I/O Efficient Algorithms for Block Hessenberg Reduction Using Panel Approach
verfasst von : Sraban Kumar Mohanty, Gopalan Sajith
Erschienen in: Big Data Analytics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Reduction to Hessenberg form is a major performance bottleneck in the computation of the eigenvalues of a nonsymmetric matrix; which takes
O
(
N
3
) flops. All the known blocked and unblocked direct Hessenberg reduction algorithms have an I/O complexity of
O
(
N
3
/
B
). To improve the performance by incorporating matrix-matrix operations in the computation, usually the Hessenberg reduction is computed in two steps: the first reducing the matrix to a banded Hessenberg form, and the second further reducing it to Hessenberg form. We propose and analyse the first step of the reduction, i.e., reduction of a nonsymmetric matrix to banded Hessenberg form of bandwidth
t
for varying values of
N
and
M
(the size of the internal memory), on external memory model introduced by Aggarwal and Vitter for the I/O complexity and show that the reduction can be performed in
$O(N^3/\min\{t,\sqrt{M}\}B)$
I/Os.