Source author record

Jorge Garza-Vargas

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NA Numerical Analysis Data Structures and Algorithms math.PR math.CO math.FA Computational Complexity math.OA

Catalog footprint

Research overview

6works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

We develop a framework for proving rapid convergence of shifted QR algorithms which use Ritz values as shifts, in finite arithmetic. Our key contribution is a dichotomy result which addresses the known forward-instability issues surrounding the shifted QR iteration [Parlett and Le 1993]: we give a procedure which provably either computes a set of approximate Ritz values of a Hessenberg matrix with good forward stability properties, or leads to early decoupling of the matrix via a small number of QR steps. Using this framework, we show that the shifting strategy introduced in Part I of this series [Banks, Garza-Vargas, and Srivastava 2021] converges rapidly in finite arithmetic with a polylogarithmic bound on the number of bits of precision required, when invoked on matrices of controlled eigenvector condition number and minimum eigenvalue gap.

preprint2022arXiv

Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration

We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix $M\in\mathbb{C}^{n\times n}$ up to backward error $δ\|M\|$ in $O(n^4+n^3\log^2(n/δ)+\log(n/δ)^2\log\log(n/δ))$ floating point operations using $O(\log^2(n/δ))$ bits of precision. While the $O(n^4)$ complexity is prohibitive for large matrices, the algorithm is simple and may be useful for provably computing the eigenvalues of small matrices using controlled precision, in particular for computing Ritz values in shifted QR algorithms as in (Banks, Garza-Vargas, Srivastava, 2022).

preprint2022arXiv

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

We exhibit a randomized algorithm which given a matrix $A\in \mathbb{C}^{n\times n}$ with $\|A\|\le 1$ and $δ>0$ , computes with high probability an invertible $V$ and diagonal $D$ such that $\|A-VDV^{-1}\|\le δ$ using $O(T_{MM}(n)\log^2(n/δ))$ arithmetic operations, in finite arithmetic with $O(\log^4(n/δ)\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^{ω+η})$ for every $η>0$ where $ω$ is the exponent of matrix multiplication (Demmel et al., Numer. Math., 2007). Our result significantly improves the previously best known provable running times of $O(n^{10}/δ^2)$ arithmetic operations for diagonalization of general matrices (Armentano et al., J. Eur. Math. Soc., 2018), and (with regards to the dependence on $n$ ) $O(n^3)$ arithmetic operations for Hermitian matrices (Dekker and Traub, Lin. Alg. Appl., 1971). It is the first algorithm to achieve nearly matrix multiplication time for diagonalization in any model of computation (real arithmetic, rational arithmetic, or finite arithmetic), thereby matching the complexity of other dense linear algebra operations such as inversion and $QR$ factorization up to polylogarithmic factors. The proof rests on two new ingredients. (1) We show that adding a small complex Gaussian perturbation to any matrix splits its pseudospectrum into $n$ small well-separated components. In particular, this implies that the eigenvalues of the perturbed matrix have a large minimum gap, a property of independent interest in random matrix theory. (2) We give a rigorous analysis of Roberts' Newton iteration method (Roberts, Int. J. Control, 1980) for computing the sign function of a matrix in finite arithmetic, itself an open problem in numerical analysis since at least 1986.

preprint2022arXiv

Spectra of infinite graphs via freeness with amalgamation

We use tools from free probability to study the spectra of Hermitian operators on infinite graphs. Special attention is devoted to universal covering trees of finite graphs. For operators on these graphs we derive a new variational formula for the spectral radius and provide new proofs of results due to Sunada and Aomoto using free probability. With the goal of extending the applicability of free probability techniques beyond universal covering trees, we introduce a new combinatorial product operation on graphs and show that, in the non-commutative probability context, it corresponds to the notion of freeness with amalgamation. We show that Cayley graphs of amalgamated free products of groups, as well as universal covering trees, can be constructed using our graph product.

preprint2020arXiv

The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output

We study the Lanczos algorithm where the initial vector is sampled uniformly from $\mathbb{S}^{n-1}$ . Let $A$ be an $n \times n$ Hermitian matrix. We show that when run for few iterations, the output of Lanczos on $A$ is almost deterministic. More precisely, we show that for any $\varepsilon \in (0, 1)$ there exists $c >0$ depending only on $\varepsilon$ and a certain global property of the spectrum of $A$ (in particular, not depending on $n$ ) such that when Lanczos is run for at most $c \log n$ iterations, the output Jacobi coefficients deviate from their medians by $t$ with probability at most $\exp(-n^\varepsilon t^2)$ for $t<\Vert A \Vert$ . We directly obtain a similar result for the Ritz values and vectors. Our techniques also yield asymptotic results: Suppose one runs Lanczos on a sequence of Hermitian matrices $A_n \in M_n(\mathbb{C})$ whose spectral distributions converge in Kolmogorov distance with rate $O(n^{-\varepsilon})$ to a density $μ$ for some $\varepsilon > 0$ . Then we show that for large enough $n$ , and for $k=O(\sqrt{\log n})$ , the Jacobi coefficients output after $k$ iterations concentrate around those for $μ$ . The asymptotic setting is relevant since Lanczos is often used to approximate the spectral density of an infinite-dimensional operator by way of the Jacobi coefficients; our result provides some theoretical justification for this approach. In a different direction, we show that Lanczos fails with high probability to identify outliers of the spectrum when run for at most $c' \log n$ iterations, where again $c'$ depends only on the same global property of the spectrum of $A$ . Classical results imply that the bound $c' \log n$ is tight up to a constant factor.

preprint2016arXiv

Polytopality of Maniplexes

Given an abstract polytope $\cal P$ , its flag graph is the edge-coloured graph whose vertices are the flags of $\cal P$ and the $i$ -edges correspond to $i$ -adjacent flags. Flag graphs of polytopes are maniplexes. On the other hand, given a maniplex $\cal M$ , on can define a poset $\cal P_M$ by means of the non empty intersection of its faces. In this paper we give necessary and sufficient conditions (in terms of graphs) on a maniplex $\cal M$ in order for $\cal P_M$ to be an abstract polytope. Moreover, in such case, we show that $\cal M$ is isomorphic to the flag graph of $\cal P_M$ . This in turn gives necessary and sufficient conditions for a maniplex to be (isomorphic to) the flag graph of a polytope.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jorge Garza-Vargas

Research overview

Is this your work?

6 publications

Global Convergence of Hessenberg Shifted QR II: Numerical Stability

Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration

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

Spectra of infinite graphs via freeness with amalgamation

The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output

Polytopality of Maniplexes

See the researcher in context

Building this map preview