PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Numerical Evaluation of Fredholm Determinants

Folkmar Bornemann

arXiv:0804.2543v2math.NAmath.FA

TL;DR

Fredholm determinants are important in mathematical physics and random matrix theory, but their numerical evaluation has lacked a general systematic method. The paper develops a simple Nyström-based quadrature approach and proves convergence tied to kernel quadrature error. It obtains highly accurate evaluations and extends the method to two-point correlation functions of Airy and Airy1 processes.

  • Problem

    Numerical evaluation of Fredholm determinants lacks a systematic general treatment despite their importance in mathematical physics and random matrix theory.

  • Method

    The paper studies projection methods and develops a Nyström-based determinant approximation using Gauss–Legendre or Clenshaw–Curtis quadrature.

  • Results

    The method gives 15 accurate digits in 0.2 ms with m = 5 Gauss–Legendre points for a sine-kernel determinant and evaluates Airy and Airy1 two-point correlations.

  • Takeaways & Limitations

    The approach provides a simple general route for evaluating Fredholm determinants and quantities represented by systems of integral operators.

  • Takeaways & Limitations

    Projection error bounds require balancing singular-value decay against derivative growth, while Green’s-kernel arguments may establish only O(m−1) convergence.

Abstract

from arXiv · show

Some significant quantities in mathematics and physics are most naturally expressed as the Fredholm determinant of an integral operator, most notably many of the distribution functions in random matrix theory. Though their numerical values are of interest, there is no systematic numerical treatment of Fredholm determinants to be found in the literature. Instead, the few numerical evaluations that are available rely on eigenfunction expansions of the operator, if expressible in terms of special functions, or on alternative, numerically more straightforwardly accessible analytic expressions, e.g., in terms of Painleve transcendents, that have masterfully been derived in some cases. In this paper we close the gap in the literature by studying projection methods and, above all, a simple, easily implementable, general method for the numerical evaluation of Fredholm determinants that is derived from the classical Nystrom method for the solution of Fredholm equations of the second kind. Using Gauss-Legendre or Clenshaw-Curtis as the underlying quadrature rule, we prove that the approximation error essentially behaves like the quadrature error for the sections of the kernel. In particular, we get exponential convergence for analytic kernels, which are typical in random matrix theory. The application of the method to the distribution functions of the Gaussian unitary ensemble (GUE), in the bulk and the edge scaling limit, is discussed in detail. After extending the method to systems of integral operators, we evaluate the two-point correlation functions of the more recently studied Airy and Airy1 processes for the first time.

1. Introduction.

The paper addresses the lack of a systematic numerical treatment for Fredholm determinants, which arise in operator theory, mathematical physics, and random matrix theory. It develops a simple Nyström-based method and demonstrates accurate evaluations, including quantities previously difficult to compute.

  • Fredholm determinants remain important in operator theory and mathematical physics, including applications to random matrix distribution functions.
  • Numerical evaluations have generally required explicitly known eigenfunctions or case-specific analytic formulas, leaving no general procedure.
  • The proposed method approximates a Fredholm determinant by the determinant of an m × m matrix constructed from a Nyström discretization.
  • The method uses standard quadrature rules, has computational cost O(m^3), and can be implemented in a few lines of Matlab or Mathematica.
  • With m = 5 Gauss–Legendre quadrature points, the sine-kernel determinant achieves 15 accurate digits in 0.2 ms.
  • Extending the method to systems of integral operators enables evaluation of two-point correlation functions for the Airy and Airy1 processes.

2. Trace Class and Hilbert–Schmidt Operators.

This section establishes the operator-theoretic framework needed for Fredholm determinants, focusing on Hilbert–Schmidt and trace class operators. It relates integral kernels and operator properties while identifying criteria that ensure trace class membership.

  • The product of two Hilbert–Schmidt operators is trace class, motivating factorization-based criteria for integral operators.
  • Hilbert–Schmidt operators on L2(a, b) correspond exactly to integral operators with square-integrable kernels.
  • Trace class operators support an absolutely convergent sum of singular values, making them the natural class for defining operator determinants.
  • A continuous kernel guarantees a Hilbert–Schmidt operator but does not generally guarantee that the induced operator is trace class.
  • Smooth kernels, suitable Hölder regularity, and selfadjoint positive-semidefinite operators provide sufficient conditions for trace class membership.

3. Definition and Properties of Fredholm and Operator Determinants.

The section defines determinants for trace class operators and connects them to Fredholm’s determinant for integral operators. It also distinguishes the trace class setting from the broader Hilbert–Schmidt setting, where regularization may be required.

  • For a trace class operator A, the operator determinant det(I + zA) is an entire function of z with equivalent standard constructions.
  • The operator determinant satisfies a multiplication formula and vanishes exactly when I + A is noninvertible.
  • For a continuous kernel inducing a trace class operator, the operator determinant agrees with Fredholm’s integral expression.
  • Fredholm’s kernel formula can remain meaningful for continuous kernels even when the induced operator is not trace class.
  • For Hilbert–Schmidt operators that are not trace class, Hilbert–Carleman regularization supplies an entire determinant because the unregularized eigenvalue product need not converge.

4. Perturbation Bounds.

The section derives perturbation bounds for operator and matrix determinants and uses them to characterize numerical conditioning. In general, determinant accuracy is governed by absolute perturbations, with sharper behavior for certain positive selfadjoint operators.

  • The determinant perturbation estimate bounds absolute determinant changes by the determinant value, inverse norm, and trace class norm of the perturbation.
  • For selfadjoint positive-semidefinite A with λ1(A) < 1, the determinant det(I − A) is well conditioned with respect to absolute errors.
  • Backward-stable matrix determinant algorithms introduce componentwise perturbations that can be bounded using the Frobenius norm.
  • The resulting a priori estimates quantify roundoff error in numerical determinant evaluations.
  • When det(I − A) is much smaller than ||A||J2, full floating-point precision may be unattainable and digits can be lost, especially in distribution tails.

5. Projection Methods.

Projection methods approximate Fredholm determinants through finite-dimensional operator projections. Their convergence follows from trace-class approximation, with rates depending on the subspaces, kernel regularity, and projection errors.

  • General convergence: Determinants of finite-rank Galerkin projections can be calculated using a finite-dimensional matrix representation.For an orthonormal basis of the approximation space, the projected operator determinant reduces to a finite-dimensional expression.
  • General convergence: Dense subspaces ensure Galerkin approximations of trace-class operator determinants converge uniformly for bounded z.The projections converge pointwise to the identity, which is equivalent to consistency of the subspaces.
  • Error estimates: Quantitative projection bounds balance singular-value truncation against collective approximation of the leading singular functions.Choosing the truncation index requires knowledge of singular-value decay and singular-function regularity; growing truncation indices can slow convergence.
  • Error estimates: For analytic kernels, the projection-method error estimate improves beyond the algebraic-regularity case and exhibits exponential-type decay.The sharper estimate applies when the kernel is bounded analytic on the specified pair of ellipses.
  • An example: Poisson’s equation: For Poisson’s equation, Ritz–Galerkin uses subspaces spanned by the operator’s sine eigenfunctions, while Galerkin uses algebraic polynomials.The sine basis yields an explicit spectral decomposition; polynomial approximation exploits the smoothness of the eigenfunctions.
  • An example: Poisson’s equation: The Galerkin determinant approximation for the Green’s kernel has actual convergence rate O(m^-2), compared with O(m^-1) for the projection methods.Figure 1 reports that the Ritz–Galerkin upper bound overestimates its determinant error by about 20%.

6. Quadrature Methods.

The paper develops a Nyström-type quadrature method for Fredholm determinants and proves convergence under general quadrature assumptions. Smoothness transfers quadrature rates to determinant approximations, while numerical examples show superconvergence for Poisson’s equation.

  • Method: The Nyström-type approximation rewrites the Fredholm determinant’s defining series as product-quadrature approximations of multidimensional kernel integrals.This provides both the method’s construction and the basis for its error analysis.
  • Convergence: If quadrature rules converge for continuous functions, the corresponding Nyström-type Fredholm determinant approximations converge uniformly for bounded z.The theorem establishes convergence without requiring kernel smoothness beyond continuity.
  • Error estimates: For smooth kernels, determinant errors essentially inherit the convergence rates of quadrature applied to one-variable sections of the kernel.The stated estimate covers kernels in Ck−1,1 and positive-weight quadrature rules of order ν ⩾ k.
  • Error estimates: For bounded analytic kernels, the error estimate yields exponential convergence for positive-weight quadrature rules.The analytic-kernel estimate uses approximation on an ellipse Eρ and supports the random-matrix applications developed later.
  • Poisson’s equation: O(m−2) convergence occurs numerically for Poisson’s Green’s kernel with Gauss–Legendre and Clenshaw–Curtis quadrature, despite a general estimate of O(m−1).The faster rate follows from piecewise-linear section shapes, whose Chebyshev coefficients decay as O(m−2), producing quadrature errors of the same order.
  • Poisson’s equation: The method’s superconvergence can outperform projection methods because those methods are governed by kernel regularity and induced-operator singular-value decay.Figure 2 compares the Nyström-type results with Ritz–Galerkin approximations for Poisson’s equation.

7. Application to Some Entire Kernels of Random Matrix Theory.

The paper applies its quadrature framework to entire kernels from random matrix theory, where exponential convergence is predicted. For the sine-kernel determinant, Nyström approximations are compared with Ritz–Galerkin calculations and asymptotic information.

  • Entire kernels: Entire kernels imply exponential convergence for Nyström-type approximations based on Gauss–Legendre or Clenshaw–Curtis quadrature.The predicted rate is O(e−cm) for any fixed c > 0.
  • The sine kernel: The GUE bulk gap probability E2(0; s) is represented by the Fredholm determinant of the sine-kernel operator on L2(0, s).The quantity is the probability that an interval of length s contains no eigenvalue in the bulk scaling limit.
  • The sine kernel: The sine kernel is Hermitian and entire, making its associated operator selfadjoint and trace class and supporting rapid determinant convergence.The kernel’s factorization also implies positivity and maximal eigenvalue less than one.
  • Ritz–Galerkin comparison: The Ritz–Galerkin comparison uses Gaudin’s construction based on radial prolate spheroidal wave functions sharing eigenfunctions with a commuting differential operator.This provides a special-function benchmark unavailable as a general recipe for arbitrary kernels.

2 , nFF

The paper develops a general Nyström-type approach for Fredholm determinants and applies it to GUE distributions, including the Airy-kernel edge limit. Smooth and analytic kernels support rapid convergence, while Airy-kernel computations require handling infinite intervals and truncation.

  • The Nyström-type method offers a general, simple alternative to eigenfunction expansions and Painlevé-based evaluations of Fredholm determinants.It is applicable from kernel continuity alone, while entire kernels guarantee exponentially fast convergence.
  • Gauss–Legendre convergence for E2(0; 1) and E2(0; 2) is exponentially fast, while Clenshaw–Curtis requires about twice the dimension for comparable accuracy.This agrees with the respective quadrature orders ν = 2m and ν = m.
  • The Nyström-type method outperforms Ritz–Galerkin in generality, implementation simplicity, and computing time, requiring milliseconds rather than several minutes.Ritz–Galerkin also depends on detailed eigenvalue information and numerical access to spheroidal wave functions.
  • For the Airy kernel on an infinite interval, the method uses transformations or truncation; truncation at T = 16 is sufficiently safe for F2(s) on [−8, 2].The truncation error is bounded through a perturbation estimate, and Figure 6 displays that bound as a function of T.
  • The transformed Airy-kernel experiments show exponential convergence despite essential complex singularities, although the general theory guarantees only super-algebraic convergence.The recommended general-purpose transformation is straightforward and requires no problem-specific construction.

8. Extension to Systems of Integral Operators.

The paper extends the Fredholm determinant framework and Nyström-type quadrature method from single operators to systems of integral operators. It then applies the extension to Airy-process correlation functions, obtaining high-accuracy numerical results over broad time ranges.

  • 8. Extension to Systems of Integral Operators.: A system of N coupled integral equations is represented as a single operator equation on a combined space of interval functions.The construction assumes disjoint intervals for convenience and uses a natural isometric isomorphism.
  • 8. Extension to Systems of Integral Operators.: The system Fredholm determinant is expressed through the kernels Kij and remains a well-defined entire function for continuous kernels, even without trace-classness of the associated operator.
  • 8. Extension to Systems of Integral Operators.: The Nyström-type system method approximates each multidimensional integral in the determinant's power series with product quadrature rules.Positive-weight quadrature formulas are used to construct the finite-dimensional approximation.
  • 8. Extension to Systems of Integral Operators.: For kernels in C^{k−1,1}, Theorem 8.1 provides a uniform error estimate for bounded z when the quadrature formulas have common order ν ⩾ k.For bounded analytic kernels, a separate estimate gives the corresponding rapid-convergence result.
  • 8.3. Examples from random matrix theory.: The method is applied to two 2 × 2 systems of integral operators arising in random matrix theory, including the Airy and Airy1 processes.Infinite intervals are transformed to [0, 1], kernels are quadrature-evaluated, and joint probabilities are computed by the system Nyström method.
  • 8.3. Examples from random matrix theory.: The Airy-process correlation is computed for 0 ⩽ t ⩽ 100 in steps of 0.1 with absolute error ±10−10.Each single-time evaluation takes about 20 minutes on average, with exponential convergence from analyticity.
  • 8.3. Examples from random matrix theory.: The Airy1 correlation is computed for 0 ⩽ t ⩽ 2.5 in steps of 0.025 with absolute error ±10−10.Each single-time evaluation takes about 5 minutes on average; the result provided evidence against Airy1 being the GOE matrix-diffusion limit.

A.1. Quadrature Rules.

This section introduces one- and multidimensional quadrature rules, their convergence and error estimates, and their use in the paper’s numerical methods. Gauss–Legendre and Clenshaw–Curtis rules provide the principal quadrature choices, with implementation and efficiency considerations.

  • One-dimensional quadrature: Quadrature rules approximate integrals on a finite interval using weighted function evaluations at prescribed points.The appendix defines quadrature-rule norms and discusses convergence for continuous functions.
  • One-dimensional quadrature: A positive-weight quadrature rule of order ν is exact for polynomials of degree at most ν −1 and supports error estimates for sufficiently smooth functions.For f ∈Ck−1,1 and ν ⩾k, the stated estimate uses a constant depending only on k.
  • One-dimensional quadrature: For bounded analytic functions, quadrature error estimates apply under analyticity in an ellipse Eρ containing the interval.The appendix states a corresponding estimate for quadrature rules of order ν with positive weights.
  • Multidimensional quadrature: Product quadrature rules extend one-dimensional rules to n-dimensional integrals and inherit convergence and smoothness-based error bounds from coordinate sections.The reduction uses quadrature errors of one-dimensional sections; analogous results are stated for Ck−1,1 and Cρ functions.
  • Gauss–Legendre and Clenshaw–Curtis: With m points, Clenshaw–Curtis has order ν = m, whereas Gauss–Legendre has order ν = 2m; both therefore fall under the stated convergence theory.The appendix also supplies Matlab implementations for both rules.
  • Gauss–Legendre and Clenshaw–Curtis: The supplied Gauss–Legendre implementation requires O(m3) operations because it forms the full Jacobi-matrix eigenvector matrix instead of computing only its first components.The text notes that more accurate and efficient alternatives may exist.

A.2. Determinantal bounds.

This section establishes regularity bounds for determinant-based functions generated from a continuous kernel. Multilinearity of the determinant and Hadamard’s inequality provide the key estimates, including analytic regularity.

  • Determinantal bounds: If K is bounded analytic on Eρ × Eρ, then K_n is of class Cρ and satisfies the corresponding analytic bound.The class Cρ is defined through analyticity in each variable and uniform boundedness on the ellipse.
  • Determinantal bounds: Multilinearity of the determinant expands the relevant derivatives into determinant terms involving derivatives of kernel entries.The displayed matrix products encode these differentiated determinant terms.
  • Determinantal bounds: Hadamard’s inequality bounds the resulting determinant expressions and yields the asserted smoothness estimates.The paper also relates this inequality to Fredholm’s original theory.

A.3. Properties of a certain function used in Theorem 6.2.

This section studies an entire function used in Theorem 6.2 and derives bounds for it. The enclosure is sharp, with its limiting lower-bound constant identified numerically.

  • Function definition: The function Ψ introduced in Lemma A.5 is defined by an expression involving z, e^{z^2/4}, and erf(z).The lemma states that this expression defines an entire function on C.
  • Bounds: The proof analyzes the function for x > 0 and shows that the upper bound occurs at n = 1 while the lower bound is approached as n →∞.These endpoint behaviors establish the enclosure used later in the argument.
  • Bounds: The enclosure is sharp, with the limiting constant √e/π = 0.93019 · · ·.The text identifies this value as evidence of sharpness.
Loading 0804.2543v2…