NDLI: ScaLAPACK's MRRR algorithm

Content Provider	ACM Digital Library
Author	Vömel, Christof
Copyright Year	2010
Abstract	The (sequential) algorithm of Multiple Relatively Robust Representations, MRRR, is a more efficient variant of inverse iteration that does not require reorthogonalization. It solves the eigenproblem of an unreduced symmetric tridiagonal matrix $\textit{T}$ ∈ Rn × n at $O(n^{2})$ cost. The computed normalized eigenvectors are numerically orthogonal in the sense that the dot product between different vectors is $\textit{O}$ $(\textit{n}$ ε), where ε refers to the relative machine precision. This article describes the design of ScaLAPACK's parallel MRRR algorithm. One emphasis is on the critical role of the representation tree in achieving both adequate accuracy and parallel scalability. A second point concerns the favorable properties of this code: subset computation, the use of static memory, and scalability. Unlike ScaLAPACK's Divide & Conquer and QR, MRRR can compute subsets of eigenpairs at reduced cost. And in contrast to inverse iterations which can fail, it is guaranteed to produce a satisfactory answer while maintaining memory scalability. ParEig, the parallel MRRR algorithm for PLAPACK, uses dynamic memory allocation. This is avoided by our code at marginal additional cost. We also use a different representation tree criterion that allows for more accurate computation of the eigenvectors but can make parallelization more difficult.
Starting Page	1
Ending Page	35
Page Count	35
File Format	PDF
ISSN	00983500
e-ISSN	15577295
DOI	10.1145/1644001.1644002
Volume Number	37
Issue Number	1
Journal	ACM Transactions on Mathematical Software (TOMS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-01-22
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multiple relatively robust representations ScaLAPACK Design Implementation Numerical software Parallel computation Symmetric eigenvalue problem
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 design and implementation of the MRRR algorithm

LAPACK working note 168: pdsyevr. ScaLAPACK’s parallel MRRR algorithm for the symmetric eigenvalue problem (2005)

Lapack working note 195: scalapack’s mrrr algorithm christof v ömel∗ abstract. The sequential algorithm of multiple relatively robust representations, mrrr,.

Scalapack’s mrrr algorithm.

An Implementation of the MRRR Algorithm on a Data-Parallel Coprocessor (2008)

A Parallel Eigensolver for Dense Symmetric Matrices Based on Multiple Relatively Robust Representations

An Implementation of the MRRR Algorithm on a Data-Parallel Coprocessor (2008)

Algorithm 826: A parallel eigenvalue routine for complex Hessenberg matrices

A Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures

ScaLAPACK's MRRR algorithm

Similar Documents

The design and implementation of the MRRR algorithm

LAPACK working note 168: pdsyevr. ScaLAPACK’s parallel MRRR algorithm for the symmetric eigenvalue problem (2005)

Lapack working note 195: scalapack’s mrrr algorithm christof v ömel∗ abstract. The sequential algorithm of multiple relatively robust representations, mrrr,.

Scalapack’s mrrr algorithm.

An Implementation of the MRRR Algorithm on a Data-Parallel Coprocessor (2008)

A Parallel Eigensolver for Dense Symmetric Matrices Based on Multiple Relatively Robust Representations

An Implementation of the MRRR Algorithm on a Data-Parallel Coprocessor (2008)

Algorithm 826: A parallel eigenvalue routine for complex Hessenberg matrices

A Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures

ScaLAPACK's MRRR algorithm