Technical Program

Paper Detail

Paper IDD.2.1
Paper Title Coded QR Decomposition
Authors Quang Minh Nguyen, National University of Singapore, Singapore; Haewon Jeong, Pulkit Grover, Carnegie Mellon University, United States
Session D.2: Coding for Specialized Computations
Presentation Lecture
Track Coded and Distributed Computation
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract QR decomposition of a matrix is one of the essential operations that is used for solving linear equations and finding least-squares solutions. We propose a coded computing strategy for parallel QR decomposition with applications to the high- performance computing (HPC) setup. Our strategy is based on the parallel Gram-Schmidt algorithm, which is one of the three commonly used algorithms for QR decomposition. Protecting QR decomposition from failures consists of two parts: protecting the left factor Q (orthogonal) and the right factor R (upper- triangular). For protecting Q, we prove a condition for a generator matrix to preserve the orthogonality of the matrix Q and construct a generator matrix for single-node failures. For protecting R, we derive a lower bound on the amount of checksums required under the in-node checksum storage setting, where checksums are stored in original nodes, and propose an encoding scheme that meets the lower bound.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!