Acceleration of iterative refinement for singular value decomposition

Yuki Uchino, Takeshi Terao, Katsuhisa Ozaki

Research output: Contribution to journalArticlepeer-review

Abstract

We propose fast numerical algorithms to improve the accuracy of singular vectors for a real matrix. Recently, Ogita and Aishima proposed an iterative refinement algorithm for singular value decomposition that is constructed with highly accurate matrix multiplications carried out six times per iteration. The algorithm runs for the problem that has no multiple and clustered singular values. In this study, we show that the same algorithm can be run with highly accurate matrix multiplications carried out five times. Also, we proposed four algorithms constructed with highly accurate matrix multiplications, two algorithms with the multiplications carried out four times, and the other two with the multiplications carried out five times. These algorithms adopt the idea of a mixed-precision iterative refinement method for linear systems. Numerical experiments demonstrate speed-up and quadratic convergence of the proposed algorithms. As a result, the fastest algorithm is 1.7 and 1.4 times faster than the Ogita-Aishima algorithm per iteration on a CPU and GPU, respectively.

Original languageEnglish
Pages (from-to)979-1009
Number of pages31
JournalNumerical Algorithms
Volume95
Issue number2
DOIs
Publication statusPublished - 2024 Feb

Keywords

  • Accurate numerical computation
  • Iterative refinement
  • Mixed-precision computation
  • Singular value decomposition

ASJC Scopus subject areas

  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Acceleration of iterative refinement for singular value decomposition'. Together they form a unique fingerprint.

Cite this