2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | D.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
