QR Factorization of Block Low-rank Matrices with Weak Admissibility Condition
-
- Ida Akihiro
- The University of Tokyo
-
- Nakashima Hiroshi
- Kyoto University
-
- Hiraishi Tasuku
- Kyoto University
-
- Yamazaki Ichitaro
- Sandia National Laboratories
-
- Yokota Rio
- Tokyo Institute of Technology
-
- Iwashita Takeshi
- Hokkaido University
Abstract
<p>The QR factorization of a matrix is a fundamental operation in linear algebra and it is widely utilized in scientific simulations. Although the QR factorization requires a memory storage of O(N2) and the computational cost of O(N3), they can be reduced if the matrix could be approximated using low-rank structured matrices, such as hierarchical matrices (H-matrices). In this paper, we study the QR factorization based on the block low-rank (BLR-) matrix representation, which is a simplified variant of the H-matrix. We demonstrate how the BLR block size should be defined in such matrices and confirm that the memory and computational complexities of the BLR are O(N1.5) and O(N2) when using an appropriate block size. Furthermore, using the simple structure of BLR-matrices, we also present a parallel algorithm for the QR factorization of BLR-matrices on distributed memory systems. In numerical experiments performed, we observe that the accuracy of the QR factorization is controllable by the accuracy of the BLR-matrix approximation of the original matrix. Finally, we verify that our algorithm enables us to perform the QR factorization of matrices of several hundred thousand N within a reasonable amount of time using moderate computer resources.</p>
Journal
-
- Journal of Information Processing
-
Journal of Information Processing 27 (0), 831-839, 2019
Information Processing Society of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390565134805015040
-
- NII Article ID
- 130007762323
-
- ISSN
- 18826652
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed