English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We exhibit a randomized algorithm which given a matrix $A\in\mathbb{C}^{n\times n}$ with $\|A\|\le 1$ and $\delta>0$, computes with highprobability an invertible $V$ and diagonal $D$ such that $\|A-VDV^{-1}\|\le\delta$ using $O(T_{MM}(n)\log^2(n/\delta))$ arithmetic operations, in finitearithmetic with $O(\log^4(n/\delta)\log n)$ bits of precision. Here $T_{MM}(n)$is the number of arithmetic operations required to multiply two $n\times n$complex matrices numerically stably, known to satisfy$T_{MM}(n)=O(n^{\omega+\eta})$ for every $\eta>0$ where $\omega$ is theexponent of matrix multiplication (Demmel et al., Numer. Math., 2007). Ourresult significantly improves the previously best known provable running timesof $O(n^{10}/\delta^2)$ arithmetic operations for diagonalization of generalmatrices (Armentano et al., J. Eur. Math. Soc., 2018), and (with regards to thedependence on $n$) $O(n^3)$ arithmetic operations for Hermitian matrices(Dekker and Traub, Lin. Alg. Appl., 1971). It is the first algorithm to achievenearly matrix multiplication time for diagonalization in any model ofcomputation (real arithmetic, rational arithmetic, or finite arithmetic),thereby matching the complexity of other dense linear algebra operations suchas inversion and $QR$ factorization up to polylogarithmic factors.  The proof rests on two new ingredients. (1) We show that adding a smallcomplex Gaussian perturbation to any matrix splits its pseudospectrum into $n$small well-separated components. In particular, this implies that theeigenvalues of the perturbed matrix have a large minimum gap, a property ofindependent interest in random matrix theory. (2) We give a rigorous analysisof Roberts' Newton iteration method (Roberts, Int. J. Control, 1980) forcomputing the sign function of a matrix in finite arithmetic, itself an openproblem in numerical analysis since at least 1986.

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time