Hermitian Diagonalization in Linear Precision

This paper presents an algorithm for Hermitian diagonalization running in near matrix multiplication time requiring only 2lg(1/ε ) + O (log(n ) + log log(1/ε )) bits of precision. Despite the widespread, highly successful use of various algorithms for Hermitian diagonalization in practice, the literature long lacked rigorous guarantees of their performance in finite arithmetic. The recent work of Banks, Garza-Vargas, Kulkarni, and Srivastava (FOCS 2020) changed this by providing an algorithm for diagonalizing any matrix up to backward error, and proving it requires no more than O (log4(n/ε ) log(n )) bits. This work improves upon their algorithm in the Hermitian setting to dramatically reduce the bit requirement.