skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: GMRES, pseudospectra, and Crouzeix’s conjecture for shifted and scaled Ginibre matrices
We study the GMRES algorithm applied to linear systems of equations involving a scaled and shifted N ×<#comment/> N N\times 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 →<#comment/> ∞<#comment/> N\to \infty 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.  more » « less
Award ID(s):
2306438
PAR ID:
10503929
Author(s) / Creator(s):
; ;
Publisher / Repository:
AMS
Date Published:
Journal Name:
Mathematics of Computation
ISSN:
0025-5718
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We study regularity of solutions u u to ∂<#comment/> ¯<#comment/> u = f \overline \partial u=f on a relatively compact C 2 C^2 domain D D in a complex manifold of dimension n n , where f f is a ( 0 , q ) (0,q) form. Assume that there are either ( q + 1 ) (q+1) negative or ( n −<#comment/> q ) (n-q) positive Levi eigenvalues at each point of boundary ∂<#comment/> D \partial D . Under the necessary condition that a locally L 2 L^2 solution exists on the domain, we show the existence of the solutions on the closure of the domain that gain 1 / 2 1/2 derivative when q = 1 q=1 and f f is in the Hölder–Zygmund space Λ<#comment/> r ( D ) \Lambda ^r( D) with r > 1 r>1 . For q > 1 q>1 , the same regularity for the solutions is achieved when ∂<#comment/> D \partial D is either sufficiently smooth or of ( n −<#comment/> q ) (n-q) positive Levi eigenvalues everywhere on ∂<#comment/> D \partial D
    more » « less
  2. In this paper we consider which families of finite simple groups G G have the property that for each ϵ<#comment/> > 0 \epsilon > 0 there exists N > 0 N > 0 such that, if | G | ≥<#comment/> N |G| \ge N and S , T S, T are normal subsets of G G with at least ϵ<#comment/> | G | \epsilon |G| elements each, then every non-trivial element of G G is the product of an element of S S and an element of T T . We show that this holds in a strong and effective sense for finite simple groups of Lie type of bounded rank, while it does not hold for alternating groups or groups of the form P S L n ( q ) \mathrm {PSL}_n(q) where q q is fixed and n →<#comment/> ∞<#comment/> n\to \infty . However, in the case S = T S=T and G G alternating this holds with an explicit bound on N N in terms of ϵ<#comment/> \epsilon . Related problems and applications are also discussed. In particular we show that, if w 1 , w 2 w_1, w_2 are non-trivial words, G G is a finite simple group of Lie type of bounded rank, and for g ∈<#comment/> G g \in G , P w 1 ( G ) , w 2 ( G ) ( g ) P_{w_1(G),w_2(G)}(g) denotes the probability that g 1 g 2 = g g_1g_2 = g where g i ∈<#comment/> w i ( G ) g_i \in w_i(G) are chosen uniformly and independently, then, as | G | →<#comment/> ∞<#comment/> |G| \to \infty , the distribution P w 1 ( G ) , w 2 ( G ) P_{w_1(G),w_2(G)} tends to the uniform distribution on G G with respect to the L ∞<#comment/> L^{\infty } norm. 
    more » « less
  3. We show that every Borel graph G G of subexponential growth has a Borel proper edge-coloring with Δ<#comment/> ( G ) + 1 \Delta (G) + 1 colors. We deduce this from a stronger result, namely that an n n -vertex (finite) graph G G of subexponential growth can be properly edge-colored using Δ<#comment/> ( G ) + 1 \Delta (G) + 1 colors by an O ( log ∗<#comment/> ⁡<#comment/> n ) O(\log ^\ast n) -round deterministic distributed algorithm in theLOCALmodel, where the implied constants in the O ( ⋅<#comment/> ) O(\cdot ) notation are determined by a bound on the growth rate of G G
    more » « less
  4. Let f f be analytic on [ 0 , 1 ] [0,1] with | f ( k ) ( 1 / 2 ) | ⩽<#comment/> A α<#comment/> k k ! |f^{(k)}(1/2)|\leqslant A\alpha ^kk! for some constants A A and α<#comment/> > 2 \alpha >2 and all k ⩾<#comment/> 1 k\geqslant 1 . We show that the median estimate of μ<#comment/> = ∫<#comment/> 0 1 f ( x ) d x \mu =\int _0^1f(x)\,\mathrm {d} x under random linear scrambling with n = 2 m n=2^m points converges at the rate O ( n −<#comment/> c log ⁡<#comment/> ( n ) ) O(n^{-c\log (n)}) for any c > 3 log ⁡<#comment/> ( 2 ) / π<#comment/> 2 ≈<#comment/> 0.21 c> 3\log (2)/\pi ^2\approx 0.21 . We also get a super-polynomial convergence rate for the sample median of 2 k −<#comment/> 1 2k-1 random linearly scrambled estimates, when k / m k/m is bounded away from zero. When f f has a p p ’th derivative that satisfies a λ<#comment/> \lambda -Hölder condition then the median of means has error O ( n −<#comment/> ( p + λ<#comment/> ) + ϵ<#comment/> ) O( n^{-(p+\lambda )+\epsilon }) for any ϵ<#comment/> > 0 \epsilon >0 , if k →<#comment/> ∞<#comment/> k\to \infty as m →<#comment/> ∞<#comment/> m\to \infty . The proof techniques use methods from analytic combinatorics that have not previously been applied to quasi-Monte Carlo methods, most notably an asymptotic expression from Hardy and Ramanujan on the number of partitions of a natural number. 
    more » « less
  5. In this article we study base change of Poincaré series along a quasi-complete intersection homomorphism φ<#comment/> :<#comment/> Q →<#comment/> R \varphi \colon Q \to R , where Q Q is a local ring with maximal ideal m \mathfrak {m} . In particular, we give a precise relationship between the Poincaré series P M Q ( t ) \mathrm {P}^Q_M(t) of a finitely generated R R -module M M to P M R ( t ) \mathrm {P}^R_M(t) when the kernel of φ<#comment/> \varphi is contained in m a n n Q ( M ) \mathfrak {m}\,\mathrm {ann}_Q(M) . This generalizes a classical result of Shamash for complete intersection homomorphisms. Our proof goes through base change formulas for Poincaré series under the map of dg algebras Q →<#comment/> E Q\to E , with E E the Koszul complex on a minimal set of generators for the kernel of φ<#comment/> \varphi
    more » « less