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

Abstract

Abstract We exhibit a randomized algorithm which, given a square matrix $$A\in \mathbb {C}^{n\times n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> with $$\Vert A\Vert \le 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mi>A</mml:mi> <mml:mo>‖</mml:mo> <mml:mo>≤</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> and $$\delta &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , computes with high probability an invertible V and diagonal D such that $$ \Vert A-VDV^{-1}\Vert \le \delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mi>A</mml:mi> <mml:mo>-</mml:mo> <mml:mi>V</mml:mi> <mml:mi>D</mml:mi> </mml:mrow> <mml:msup> <mml:mi>V</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mo>≤</mml:mo> <mml:mi>δ</mml:mi> </mml:mrow> </mml:mrow> </mml:math> using $$O(T_\mathsf {MM}(n)\log ^2(n/\delta ))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>MM</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mi>δ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> arithmetic operations, in finite arithmetic with $$O(\log ^4(n/\delta )\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>4</mml:mn> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mi>δ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> bits of precision. The computed similarity V additionally satisfies $$\Vert V\Vert \Vert V^{-1}\Vert \le O(n^{2.5}/\delta )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mi>V</mml:mi> <mml:mo>‖</mml:mo> <mml:mo>‖</mml:mo> </mml:mrow> <mml:msup> <mml:mi>V</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mo>≤</mml:mo> <mml:mi>O</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>2.5</mml:mn> </mml:mrow> </mml:msup> <mml:mo>/</mml:mo> <mml:mi>δ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . Here $$T_\mathsf {MM}(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>MM</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> is the number of arithmetic operations required to multiply two $$n\times n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> complex matrices numerically stably, known to satisfy $$T_\mathsf {MM}(n)=O(n^{\omega +\eta })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>MM</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>ω</mml:mi> <mml:mo>+</mml:mo> <mml:mi>η</mml:mi> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> for every $$\eta &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>η</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> where $$\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> is the exponent of matrix multiplication (Demmel et al. in Numer Math 108(1):59–91, 2007). The algorithm is a variant of the spectral bisection algorithm in numerical linear algebra (Beavers Jr. and Denman in Numer Math 21(1-2):143–169, 1974) with a crucial Gaussian perturbation preprocessing step. Our result significantly improves the previously best-known provable running times of $$O(n^{10}/\delta ^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">

Topics & Concepts