Search for: All records

Abstract Motivated by Fredholm theory, we develop a framework to establish the convergence of spectral methods for operator equations $$\mathcal L u = f$$. The framework posits the existence of a left-Fredholm regulator for $$\mathcal L$$ and the existence of a sufficiently good approximation of this regulator. Importantly, the numerical method itself need not make use of this extra approximant. We apply the framework to Fourier finite-section and collocation-based numerical methods for solving differential equations with periodic boundary conditions and to solving Riemann–Hilbert problems on the unit circle. We also obtain improved results concerning the approximation of eigenvalues of differential operators with periodic coefficients. 

Abstract We establish a new perturbation theory for orthogonal polynomials using a Riemann–Hilbert approach and consider applications in numerical linear algebra and random matrix theory. This new approach shows that the orthogonal polynomials with respect to two measures can be effectively compared using the difference of their Stieltjes transforms on a suitably chosen contour. Moreover, when two measures are close and satisfy some regularity conditions, we use the theta functions of a hyperelliptic Riemann surface to derive explicit and accurate expansion formulae for the perturbed orthogonal polynomials. In contrast to other approaches, a key strength of the methodology is that estimates can remain valid as the degree of the polynomial grows. The results are applied to analyze several numerical algorithms from linear algebra, including the Lanczos tridiagonalization procedure, the Cholesky factorization, and the conjugate gradient algorithm. As a case study, we investigate these algorithms applied to a general spiked sample covariance matrix model by considering the eigenvector empirical spectral distribution and its limits. For the first time, we give precise estimates on the output of the algorithms, applied to this wide class of random matrices, as the number of iterations diverges. In this setting, beyond the first order expansion, we also derive a new mesoscopic central limit theorem for the associated orthogonal polynomials and other quantities relevant to numerical algorithms. 

We study the GMRES algorithm applied to linear systems of equations involving a scaled and shifted $N\times <\#comment/>N$matrix whose entries are independent complex Gaussians. When the right-hand side of this linear system is independent of this random matrix, the $N\to <\#comment/>\mathrm{\infty <\#comment/>}$behavior of the GMRES residual error can be determined exactly. To handle cases where the right hand side depends on the random matrix, we study the pseudospectra and numerical range of Ginibre matrices and prove a restricted version of Crouzeix’s conjecture. 

We compute the Tracy-Widom distribution describing the asymptotic distribution of the largest eigenvalue of a large random matrix by solving a boundary-value problem posed by Bloemendal in his Ph.D. Thesis (2011). The distribution is computed in two ways. The first method is a second-order finite-difference method and the second is a highly accurate Fourier spectral method. Since $$\beta$$ is simply a parameter in the boundary-value problem, any $$\beta> 0$$ can be used, in principle. The limiting distribution of the $$n$$th largest eigenvalue can also be computed. Our methods are available in the Julia package TracyWidomBeta.jl. 

Abstract We present a probabilistic analysis of two Krylov subspace methods for solving linear systems. We prove a central limit theorem for norms of the residual vectors that are produced by the conjugate gradient and MINRES algorithms when applied to a wide class of sample covariance matrices satisfying some standard moment conditions. The proof involves establishing a four‐moment theorem for the so‐called spectral measure, implying, in particular, universality for the matrix produced by the Lanczos iteration. The central limit theorem then implies an almost‐deterministic iteration count for the iterative methods in question. © 2022 Wiley Periodicals LLC. 

Abstract We develop a numerical method for computing with orthogonal polynomials that are orthogonal on multiple, disjoint intervals for which analytical formulae are currently unknown. Our approach exploits the Fokas–Its–Kitaev Riemann–Hilbert representation of the orthogonal polynomials to produce an method to compute the firstNrecurrence coefficients. The method can also be used for pointwise evaluation of the polynomials and their Cauchy transforms throughout the complex plane. The method encodes the singularity behavior of weight functions using weighted Cauchy integrals of Chebyshev polynomials. This greatly improves the efficiency of the method, outperforming other available techniques. We demonstrate the fast convergence of our method and present applications to integrable systems and approximation theory. 

We implement the numerical unified transform method to solve the nonlinear Schrödinger equation on the half-line. For the so-called linearizable boundary conditions, the method solves the half-line problems with comparable complexity as the numerical inverse scattering transform solves whole-line problems. In particular, the method computes the solution at any x and t without spatial discretization or time stepping. Contour deformations based on the method of nonlinear steepest descent are used so that the method’s computational cost does not increase for large x , t and the method is more accurate as x , t increase. Our ideas also apply to some cases where the boundary conditions are not linearizable.