Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On the numerical evaluation of Fredholm determinants


Author: Folkmar Bornemann
Journal: Math. Comp. 79 (2010), 871-915
MSC (2000): Primary 65R20, 65F40; Secondary 47G10, 15A52
DOI: https://doi.org/10.1090/S0025-5718-09-02280-7
Published electronically: September 24, 2009
MathSciNet review: 2600548
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 Painlevé 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 Nyström 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 scaling limit 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 Airy$ _1$ processes.


References [Enhancements On Off] (What's this?)

  • Ablowitz, M. J. and Fokas, A. S.: 2003, Complex variables: Introduction and applications, 2nd edition, Cambridge University Press, Cambridge. MR 1989049 (2004f:30001)
  • Adler, M. and van Moerbeke, P.: 2005, PDEs for the joint distributions of the Dyson, Airy and sine processes, Ann. Probab. 33, 1326-1361. MR 2150191 (2006g:60118)
  • Albeverio, S. and Høegh-Krohn, R.: 1977, Oscillatory integrals and the method of stationary phase in infinitely many dimensions, with applications to the classical limit of quantum mechanics. I, Invent. Math. 40, 59-106. MR 0474436 (57:14076)
  • Axler, S.: 1995, Down with determinants!, Amer. Math. Monthly 102, 139-154. MR 1315593 (96d:15001)
  • Axler, S.: 1997, Linear algebra done right, 2nd edition, Springer-Verlag, New York. MR 1482226 (98i:15001)
  • Baker, C. T. H.: 1977, The numerical treatment of integral equations, Clarendon Press, Oxford. MR 0467215 (57:7079)
  • Birkhoff, G. (ed.): 1973, A source book in classical analysis, Harvard University Press, Cambridge. MR 0469612 (57:9395)
  • Bornemann, F.: 2009, Asymptotic independence of the extreme eigenvalues of GUE, arXiv:0902.3870.
  • Bornemann, F., Ferrari, P. L. and Prähofer, M.: 2008, The $ {\rm Airy}\sb 1$ process is not the limit of the largest eigenvalue in GOE matrix diffusion, J. Stat. Phys. 133, 405-415. MR 2448629
  • Borodin, A., Ferrari, P. L., Prähofer, M. and Sasamoto, T.: 2007, Fluctuation properties of the TASEP with periodic initial configuration, J. Stat. Phys. 129, 1055-1080. MR 2363389 (2009g:82048)
  • Carleman, T.: 1918, Über die Fourierkoeffizienten einer stetigen Function, Acta Math. 41, 377-384. MR 1555157
  • Carleman, T.: 1921, Zur Theorie der linearen Integralgleichungen, Math. Zeitschr. 9, 196-217. MR 1544464
  • Cheney, E. W.: 1998, Introduction to approximation theory, reprint of the 2nd (1982) edition, AMS Chelsea Publishing, Providence, RI. MR 1656150 (99f:41001)
  • Courant, R. and Hilbert, D.: 1953, Methods of mathematical physics. Vol. I, Interscience Publishers, Inc., New York. MR 0065391 (16:426a)
  • Davis, P. J. and Rabinowitz, P.: 1984, Methods of numerical integration, 2nd edition, Academic Press, Orlando, FL. MR 760629 (86d:65004)
  • Deift, P. A.: 1999, Orthogonal polynomials and random matrices: A Riemann-Hilbert approach, American Mathematical Society, Providence, RI. MR 1677884 (2000g:47048)
  • Deift, P. A., Its, A. R. and Zhou, X.: 1997, A Riemann-Hilbert approach to asymptotic problems arising in the theory of random matrix models, and also in the theory of integrable statistical mechanics, Ann. of Math. (2) 146, 149-235. MR 1469319 (98k:47097)
  • Deift, P., Its, A. and Krasovsky, I.: 2008, Asymptotics of the Airy-kernel determinant, Comm. Math. Phys. 278, 643-678. MR 2373439 (2008m:47061)
  • Delves, L. M. and Mohamed, J. L.: 1985, Computational methods for integral equations, Cambridge University Press, Cambridge. MR 837187 (87j:65159)
  • DeVore, R. A. and Lorentz, G. G.: 1993, Constructive approximation, Springer-Verlag, Berlin. MR 1261635 (95f:41001)
  • Dieng, M.: 2005, Distribution Functions for Edge Eigenvalues in Orthogonal and Symplectic Ensembles: Painlevé Representations, Ph.D. thesis, University of Davis.
    arXiv:math/0506586v2. MR 2181265 (2006h:60014)
  • Dieudonné, J.: 1981, History of functional analysis, North-Holland Publishing Co., Amsterdam. MR 605488 (83d:46001)
  • Driscoll, T. A., Bornemann, F. and Trefethen, L. N.: 2008, The chebop system for automatic solution of differential equations, BIT 48. MR 2465699
  • Dunford, N. and Schwartz, J. T.: 1963, Linear operators. Part II: Spectral theory, John Wiley & Sons. MR 0216304 (35:7139)
  • Dyson, F. J.: 1976, Fredholm determinants and inverse scattering problems, Comm. Math. Phys. 47, 171-183. MR 0406201 (53:9993)
  • Eastham, M.: 1973, The spectral theory of periodic differential equations, Scottish Academic Press, Edinburgh.
  • Falloon, P. E., Abbott, P. C. and Wang, J. B.: 2003, Theory and computation of spheroidal wavefunctions, J. Phys. A 36, 5477-5495. MR 1985521 (2004i:33035)
  • Fenyő, S. and Stolle, H.-W.: 1982-1984, Theorie und Praxis der linearen Integralgleichungen. Vol. I-IV, Birkhäuser, Basel.
  • Fredholm, I.: 1900, Sur une nouvelle méthode pour la résolution du problème de Dirichlet, Öfversigt Kongl. Vetenskaps-Akad. Förhandlingar 57, 39-46.
  • Fredholm, I.: 1903, Sur une classe d'équations fonctionnelles, Acta Math. 27, 365-390. MR 1554993
  • Fredholm, I.: 1909, Les équations intégrales linéaires, C. R. Congrés des Math. tenu à Stockholm 1909.
  • Gaudin, M.: 1961, Sur la loi limite de l'espacement des valeurs propres d'une matrice aléatoire, Nucl. Phys. 25, 447-458.
  • Gautschi, W.: 2002, Computation of Bessel and Airy functions and of related Gaussian quadrature formulae, BIT 42, 110-118. MR 1896388 (2003d:33010)
  • Gohberg, I. C. and Kreĭn, M. G.: 1969, Introduction to the theory of linear nonselfadjoint operators, Translations of Mathematical Monographs, vol. 18, American Mathematical Society, Providence, RI. MR 0246142 (39:7447)
  • Gohberg, I., Goldberg, S. and Kaashoek, M. A.: 1990, Classes of linear operators. Vol. I, Birkhäuser Verlag, Basel. MR 1130394 (93d:47002)
  • Gohberg, I., Goldberg, S. and Krupnik, N.: 2000, Traces and determinants of linear operators, Birkhäuser Verlag, Basel. MR 1744872 (2001b:47035)
  • Golub, G. H. and Van Loan, C. F.: 1996, Matrix computations, 3rd edition, Johns Hopkins University Press, Baltimore, MD. MR 1417720 (97g:65006)
  • Greub, W. H.: 1967, Multilinear algebra, Springer-Verlag, New York. MR 0224623 (37:222)
  • Grothendieck, A.: 1956, La théorie de Fredholm, Bull. Soc. Math. France 84, 319-384. MR 0088665 (19:558d)
  • Hackbusch, W.: 1995, Integral equations: Theory and numerical treatment, Birkhäuser Verlag, Basel. MR 1350296 (96h:45001)
  • Hadamard, J.: 1893, Résolution d'une question relative aux déterminants, Bull. Sci. Math. 17, 240-246.
  • Hägg, J.: 2008, Local Gaussian fluctuations in the Airy and discrete PNG processes, Ann. Probab. 36, 1059-1092. MR 2408583 (2009b:60299)
  • Hastings, S. P. and McLeod, J. B.: 1980, A boundary value problem associated with the second Painlevé transcendent and the Korteweg-de Vries equation, Arch. Rational Mech. Anal. 73, 31-51. MR 555581 (81i:34024)
  • Higham, N. J.: 2002, Accuracy and stability of numerical algorithms, 2nd edition, Society for Industrial and Applied Mathematics, Philadelphia, PA. MR 1927606 (2003g:65064)
  • Hilbert, D.: 1904, Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen. (Erste Mitteilung), Nachr. Ges. Wiss. Göttingen 1904, 49-91.
  • Hilbert, D.: 1912, Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen, Teubner, Leipzig, Berlin.
  • Hille, E. and Tamarkin, J. D.: 1931, On the characteristic values of linear integral equations, Acta Math. 57, 1-76. MR 1555331
  • Hochstadt, H.: 1973, Integral equations, John Wiley & Sons, New York. MR 0390680 (52:11503)
  • Jimbo, M., Miwa, T., Môri, Y. and Sato, M.: 1980, Density matrix of an impenetrable Bose gas and the fifth Painlevé transcendent, Phys. D 1, 80-158. MR 573370 (84k:82037)
  • Johansson, K.: 2000, Shape fluctuations and random matrices, Comm. Math. Phys. 209, 437-476. MR 1737991 (2001h:60177)
  • Johansson, K.: 2003, Discrete polynuclear growth and determinantal processes, Comm. Math. Phys. 242, 277-329. MR 2018275 (2004m:82096)
  • Jost, R. and Pais, A.: 1951, On the scattering of a particle by a static potential, Physical Rev. 82, 840-851. MR 0044404 (13:414e)
  • Katz, N. M. and Sarnak, P.: 1999, Random matrices, Frobenius eigenvalues, and monodromy, American Mathematical Society, Providence, RI. MR 1659828 (2000b:11070)
  • Kline, M.: 1972, Mathematical thought from ancient to modern times, Oxford University Press, New York. MR 0472307 (57:12010)
  • Knopp, K.: 1964, Theorie und Anwendung der unendlichen Reihen, 5th edition, Springer-Verlag, Berlin. MR 0183997 (32:1473)
  • Kress, R.: 1999, Linear integral equations, 2nd edition, Springer-Verlag, New York. MR 1723850 (2000h:45001)
  • Laurie, D. P.: 2001, Computation of Gauss-type quadrature formulas, J. Comput. Appl. Math. 127, 201-217. MR 1808574 (2001k:65051)
  • Lax, P. D.: 2002, Functional analysis, John Wiley & Sons, New York. MR 1892228 (2003a:47001)
  • McCoy, B. M., Perk, J. H. H. and Shrock, R. E.: 1983, Time-dependent correlation functions of the transverse Ising chain at the critical magnetic field, Nuclear Phys. B 220, 35-47. MR 702266 (85f:82054)
  • Mehta, M. L.: 2004, Random matrices, 3rd edition, Elsevier/Academic Press, Amsterdam. MR 2129906 (2006b:82001)
  • Meyer, C.: 2000, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA. MR 1777382
  • Moiseiwitsch, B.: 1977, Recent progress in atomic collisions theory, Rep. Prog. Phys. 40, 843-904.
  • Nyström, E.: 1930, Über die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben, Acta Math. 54, 185-204. MR 1555306
  • Oishi, S.: 1979, Relationship between Hirota's method and the inverse spectral method--the Korteweg-deVries equation's case, J. Phys. Soc. Japan 47, 1037-1038. MR 548512 (81e:35011)
  • Pietsch, A.: 2007, History of Banach spaces and linear operators, Birkhäuser, Boston. MR 2300779 (2008i:46002)
  • Plemelj, J.: 1904, Zur Theorie der Fredholmschen Funktionalgleichung, Monatsh. f. Math. 15, 93-128. MR 1547272
  • Pöppe, C.: 1984, The Fredholm determinant method for the KdV equations, Phys. D 13, 137-160. MR 775282 (86f:35165)
  • Porter, D. and Stirling, D. S. G.: 1990, Integral equations, Cambridge University Press, Cambridge. MR 1111247 (92d:45001)
  • Prähofer, M. and Spohn, H.: 2002, Scale invariance of the PNG droplet and the Airy process, J. Statist. Phys. 108, 1071-1106. MR 1933446 (2003i:82050)
  • Prähofer, M. and Spohn, H.: 2004, Exact scaling functions for one-dimensional stationary KPZ growth, J. Statist. Phys. 115, 255-279. MR 2070096 (2005d:82097)
  • Prössdorf, S. and Silbermann, B.: 1991, Numerical analysis for integral and related operator equations, Birkhäuser Verlag, Basel. MR 1206476 (94f:65126a)
  • Reinhardt, W. P. and Szabo, A.: 1970, Fredholm method. I. A numerical procedure for elastic scattering, Phys. Rev. A 1, 1162-1169. MR 0266459 (42:1365)
  • Rezende, J.: 1994, Feynman integrals and Fredholm determinants, J. Math. Phys. 35, 4357-4371. MR 1284645 (95h:58028)
  • Riess, R. D. and Johnson, L. W.: 1972, Error estimates for Clenshaw-Curtis quadrature, Numer. Math. 18, 345-353. MR 0305555 (46:4685)
  • Sasamoto, T.: 2005, Spatial correlations of the 1D KPZ surface on a flat substrate, J. Phys. A 38, L549-L556. MR 2165697 (2006c:82046)
  • Simon, B.: 1977, Notes on infinite determinants of Hilbert space operators, Advances in Math. 24, 244-273. MR 0482328 (58:2401)
  • Simon, B.: 2005, Trace ideals and their applications, 2nd edition, Math. Surveys and Monographs, vol. 120, American Mathematical Society, Providence, RI. MR 2154153 (2006f:47086)
  • Smithies, F.: 1937, The eigen-values and singular values of integral equations, Proc. London Math. Soc. 43, 255-279.
  • Smithies, F.: 1958, Integral equations, Cambridge University Press, Cambridge. MR 0104991 (21:3738)
  • Spohn, H.: 2008, Personal communication.
  • Stewart, G. W.: 1998, Matrix algorithms. Vol. I: Basic decompositions, Society for Industrial and Applied Mathematics, Philadelphia, PA. MR 1653546
  • Stratton, J. A., Morse, P. M., Chu, L. J., Little, J. D. C. and Corbató, F. J.: 1956, Spheroidal wave functions, including tables of separation constants and coefficients, John Wiley & Sons, New York.
  • Swarztrauber, P. N.: 2002, On computing the points and weights for Gauss-Legendre quadrature, SIAM J. Sci. Comput. 24, 945-954. MR 1950519 (2004a:65027)
  • Tracy, C. A. and Widom, H.: 1994, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159, 151-174. MR 1257246 (95e:82003)
  • Tracy, C. A. and Widom, H.: 1996, Fredholm determinants and the mKdV/sinh-Gordon hierarchies, Comm. Math. Phys. 179, 1-9. MR 1395215 (97d:58107)
  • Tracy, C. A. and Widom, H.: 2000, Universality of the distribution functions of random matrix theory, Integrable systems: From classical to quantum (Montréal, QC, 1999), Vol. 26 of CRM Proc. Lecture Notes, Amer. Math. Soc., Providence, RI, pp. 251-264. MR 1791893 (2002f:15036)
  • Trefethen, L. N.: 2008, Is Gauss quadrature better than Clenshaw-Curtis?, SIAM Rev. 50, 67-87. MR 2403058 (2009c:65061)
  • Tricomi, F. G.: 1957, Integral equations, Interscience Publishers, Inc., New York. MR 0094665 (20:1177)
  • Vallée, O. and Soares, M.: 2004, Airy functions and applications to physics, Imperial College Press, London.
  • von Koch, H.: 1892, Sur les déterminants infinis et les équations différentielles linéaires, Acta Math. 16, 217-295. MR 1554829
  • Waldvogel, J.: 2006, Fast construction of the Fejér and Clenshaw-Curtis quadrature rules, BIT 46, 195-202. MR 2214855 (2007k:65046)
  • Webster, A. G.: 1927, Partial differential equations of mathematical physics, G. E. Stechert & Co., New York.
  • Whittaker, E. T. and Watson, G. N.: 1927, A course of modern analysis, 4th edition, Cambridge University Press, Cambridge. MR 1424469 (97k:01072)
  • Widom, H.: 2004, On asymptotics for the Airy process, J. Statist. Phys. 115, 1129-1134. MR 2054175 (2005b:82071)
  • Wilkinson, D.: 1978, Continuum derivation of the Ising model two-point function, Phys. Rev. D 17, 1629-1636.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65R20, 65F40, 47G10, 15A52

Retrieve articles in all journals with MSC (2000): 65R20, 65F40, 47G10, 15A52


Additional Information

Folkmar Bornemann
Affiliation: Zentrum Mathematik – M3, Technische Universität München, Boltzmannstr. 3, 85747 Garching bei München, Germany
Email: bornemann@ma.tum.de

DOI: https://doi.org/10.1090/S0025-5718-09-02280-7
Received by editor(s): June 24, 2008
Received by editor(s) in revised form: March 16, 2009
Published electronically: September 24, 2009
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society