PPubMed25 Jul 2025

A simple, randomized algorithm for diagonalizing normal matrices

Haoze He, Daniel Kressner

Abstract

We present and analyze a simple numerical method that diagonalizes a complex normal matrix A by diagonalizing the Hermitian matrix obtained from a random linear combination of the Hermitian and skew-Hermitian parts of A.

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

RandDiag is a simple randomized algorithm that diagonalizes normal matrices up to four‑to‑six times faster than Schur with only a modest loss of accuracy.

What’s new

i.Proposed the RandDiag algorithm that diagonalizes a normal matrix via a random linear combination of its Hermitian and skew‑Hermitian parts
ii.Provided theoretical proofs of almost‑sure correctness and robustness with explicit error bounds
iii.Demonstrated through extensive numerical experiments that RandDiag is 4–6× faster than Schur decomposition with comparable eigenvalue accuracy
iv.Released an open‑source Python implementation and data for reproducibility

How they did it

The method draws two independent standard‑normal scalars, forms the Hermitian matrix μ_H H + μ_S iS, and computes its eigenvectors using existing Hermitian eigensolvers. The resulting unitary matrix is shown to diagonalize the original normal matrix with probability one, and its robustness to finite‑precision perturbations is analyzed theoretically and experimentally.

What they found

RandDiag time 0.16 s vs Schur 0.64 s for n=500 (4× speedup), off‑diagonal error 1.42e‑10 vs 2.58e‑13
RandDiag time 0.58 s vs Schur 2.47 s for n=1000 (≈4× speedup), error 7.88e‑10 vs 4.84e‑13
RandDiag time 1.45 s vs Schur 6.50 s for n=1500 (≈4.5× speedup), error 1.24e‑9 vs 6.72e‑13
Thermal‑conductivity model (n=2048): RandDiag 3.49 s vs Schur 20.73 s (≈6× speedup), error 1.26e‑9 vs 9.24e‑13

Caveats

✕Off‑diagonal error is a few digits larger than Schur (loss of 3–5 digits)
✕The theoretical O(n^{3.5}) error bound is pessimistic; tightening it remains open
✕Algorithm assumes exact normality; finite‑precision perturbations can degrade normality
✕Random coefficients are essential; fixed choices can cause failure

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

A simple, randomized algorithm for diagonalizing normal matrices

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

The paper, in five minutes

Similar papers in all four archives