Deterministic Complexity Analysis of Hermitian Eigenproblems
OPEN ACCESS
Author / Producer
Date
2025-06-30
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. Recently, [BGVKS, FOCS 2020] proved that a (non-Hermitian) matrix A can be diagonalized with a randomized algorithm in O(n$^ω$ log$^2$($\frac{n}{ϵ}$)) arithmetic operations, where ω ≲ 2.371 is the square matrix multiplication exponent, and [Shah, SODA 2025] significantly improved the bit complexity for the Hermitian case. Our main goal is to obtain similar deterministic complexity bounds for various Hermitian eigenproblems. In the Real RAM model, we show that a Hermitian matrix can be diagonalized deterministically in O(n$^ω$ log(n) + n$^2$polylog($\frac{n}{ϵ}$)) arithmetic operations, improving the classic deterministic $\tilde{O}$(n$^3$) algorithms, and derandomizing the aforementioned state-of-the-art. The main technical step is a complete, detailed analysis of a well-known divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95], when accelerated with the Fast Multipole Method, asserting that it can accurately diagonalize a symmetric tridiagonal matrix in nearly-O(n$^2$) operations. In finite precision, we show that an algorithm by Schönhage [Sch72] to reduce a Hermitian matrix to tridiagonal form is stable in the floating point model, using O(log($\frac{n}{ϵ}$)) bits of precision. This leads to a deterministic algorithm to compute all the eigenvalues of a Hermitian matrix in O(n$^ω$F (log($\frac{n}{ϵ}$)) + n$^2$ polylog($\frac{n}{ϵ}$)) bit operations, where F(b) ∈ $\tilde{O}$(b) is the bit complexity of a single floating point operation on b bits. This improves the best known $\tilde{O}$(n$^3$) deterministic and O(n$^ω$log$^2$($\frac{n}{ϵ}$) F(log($\frac{n}{ϵ}$))) randomized complexities. We conclude with some other useful subroutines such as computing spectral gaps, condition numbers, and spectral projectors, and with some open problems.
Permanent link
Publication status
published
External links
Book title
52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
Volume
334
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Hermitian eigenproblem; eigenvalues; SVD; tridiagonal reduction; matrix multiplication time; diagonalization; bit complexity