Deterministic regularisation of the nonsymmetric eigenproblem

We give a deterministic algorithm for pseudospectral shattering in exact arithmetic. This resolves an important open problem in the complexity of the nonsymmetric eigenproblem. Given a complex contraction $A$ of order $n\ge2$ and $0<\delta<1/2$, we compute a perturbation $E$ with $\|E\|<\delta$ such that $A+E$ has simple spectrum. The ratio of its eigenbasis condition number to its minimum eigenvalue gap is at most $C(n/\delta)^{20/3}$. The algorithm also computes an exact eigensystem of $A+E$. It uses $O(n^3\log^d(n/\delta))$ real-field operations and comparisons, where $C$ and $d$ are absolute constants. We choose the rank-one perturbations using a lower bound on the circle mean of the logarithm of the discriminant modulus. A quadratic penalty controls how far the accumulated updates move the matrix. By using the same reference eigenbasis for several updates, we can estimate all the current projector norms while recovering only the directions needed for the next perturbation.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-21
DOI
https://doi.org/10.5281/zenodo.24413261
Primary Topic
Matrix Theory and Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Deterministic regularisation of the nonsymmetric eigenproblem

Matthew J. Colbrook
Zenodo (CERN European Organization for Nuclear Research)
Matrix Theory and Algorithms
preprint

Deterministic regularisation of the nonsymmetric eigenproblem

Matthew J. Colbrook
preprint en

Abstract

We give a deterministic algorithm for pseudospectral shattering in exact arithmetic. This resolves an important open problem in the complexity of the nonsymmetric eigenproblem. Given a complex contraction $A$ of order $n\ge2$ and $0<\delta<1/2$, we compute a perturbation $E$ with $\|E\|<\delta$ such that $A+E$ has simple spectrum. The ratio of its eigenbasis condition number to its minimum eigenvalue gap is at most $C(n/\delta)^{20/3}$. The algorithm also computes an exact eigensystem of $A+E$. It uses $O(n^3\log^d(n/\delta))$ real-field operations and comparisons, where $C$ and $d$ are absolute constants. We choose the rank-one perturbations using a lower bound on the circle mean of the logarithm of the discriminant modulus. A quadratic penalty controls how far the accumulated updates move the matrix. By using the same reference eigenbasis for several updates, we can estimate all the current projector norms while recovering only the directions needed for the next perturbation.

Zenodo (CERN European Organization for Nuclear Research)
University of Cambridge (GB)
Matrix Theory and Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Deterministic regularisation of the nonsymmetric eigenproblem — Matthew J. Colbrook · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS