NDLI: Optimally packed chains of bulges in multishift QR algorithms

Content Provider	ACM Digital Library
Author	Kressner, Daniel Karlsson, Lars Lang, Bruno
Copyright Year	2014
Abstract	The QR algorithm is the method of choice for computing all eigenvalues of a dense nonsymmetric matrix $\textit{A}.$ After an initial reduction to Hessenberg form, a QR iteration can be viewed as chasing a small bulge from the top left to the bottom right corner along the subdiagonal of $\textit{A}.$ To increase data locality and create potential for parallelism, modern variants of the QR algorithm perform several iterations simultaneously, which amounts to chasing a chain of several bulges instead of a single bulge. To make effective use of level 3 BLAS, it is important to pack these bulges as tightly as possible within the chain. In this work, we show that the tightness of the packing in existing approaches is not optimal and can be increased. This directly translates into a reduced chain length by 33% compared to the state-of-the-art LAPACK implementation of the QR algorithm. To demonstrate the impact of our idea, we have modified the LAPACK implementation to make use of the optimal packing. Numerical experiments reveal a uniform reduction of the execution time, without affecting stability or robustness.
Starting Page	1
Ending Page	15
Page Count	15
File Format	PDF
ISSN	00983500
e-ISSN	15577295
DOI	10.1145/2559986
Volume Number	40
Issue Number	2
Journal	ACM Transactions on Mathematical Software (TOMS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-03-05
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multishift QR algorithms Implicit shifts Level 3 BLAS
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Multishift QR Algorithm. Part I: Maintaining Well-Focused Shifts and Level 3 Performance

Stability of block algorithms with fast level-3 BLAS

Optimally packed chains of bulges in multishift qr algorithms ∗ (2012).

Algorithm 953: Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation

Algorithm 784: GEMM-based level 3 BLAS: portability and optimization issues

Using Level 3 BLAS in Rotation-Based Algorithms

The RISC BLAS: a blocked implementation of level 3 BLAS for RISC processors

GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark

A parallel block implementation of Level-3 BLAS for MIMD vector processors

Optimally packed chains of bulges in multishift QR algorithms

Similar Documents

The Multishift QR Algorithm. Part I: Maintaining Well-Focused Shifts and Level 3 Performance

Stability of block algorithms with fast level-3 BLAS

Optimally packed chains of bulges in multishift qr algorithms ∗ (2012).

Algorithm 953: Parallel Library Software for the Multishift QR Algorithm with Aggressive Early Deflation

Algorithm 784: GEMM-based level 3 BLAS: portability and optimization issues

Using Level 3 BLAS in Rotation-Based Algorithms

The RISC BLAS: a blocked implementation of level 3 BLAS for RISC processors

GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark

A parallel block implementation of Level-3 BLAS for MIMD vector processors

Optimally packed chains of bulges in multishift QR algorithms