On the numerical evaluation of Fredholm determinants
HTML articles powered by AMS MathViewer
- by Folkmar Bornemann PDF
- Math. Comp. 79 (2010), 871-915 Request permission
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 $\text {Airy}_1$ processes.References
- Mark J. Ablowitz and Athanassios S. Fokas, Complex variables: introduction and applications, 2nd ed., Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2003. MR 1989049, DOI 10.1017/CBO9780511791246
- Mark Adler and Pierre van Moerbeke, PDEs for the joint distributions of the Dyson, Airy and sine processes, Ann. Probab. 33 (2005), no. 4, 1326–1361. MR 2150191, DOI 10.1214/009117905000000107
- Sergio Albeverio and Raphael Höegh-Krohn, 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 (1977), no. 1, 59–106. MR 474436, DOI 10.1007/BF01389861
- Sheldon Axler, Down with determinants!, Amer. Math. Monthly 102 (1995), no. 2, 139–154. MR 1315593, DOI 10.2307/2975348
- Sheldon Axler, Linear algebra done right, 2nd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997. MR 1482226, DOI 10.1007/b97662
- Christopher T. H. Baker, The numerical treatment of integral equations, Monographs on Numerical Analysis, Clarendon Press, Oxford, 1977. MR 0467215
- Garrett Birkhoff (ed.), A source book in classical analysis, Harvard University Press, Cambridge, Mass., 1973. With the assistance of Uta Merzbach. MR 0469612
- Bornemann, F.: 2009, Asymptotic independence of the extreme eigenvalues of GUE, arXiv:0902.3870.
- Folkmar Bornemann, Patrik L. Ferrari, and Michael Prähofer, The $\textrm {Airy}_1$ process is not the limit of the largest eigenvalue in GOE matrix diffusion, J. Stat. Phys. 133 (2008), no. 3, 405–415. MR 2448629, DOI 10.1007/s10955-008-9621-0
- Alexei Borodin, Patrik L. Ferrari, Michael Prähofer, and Tomohiro Sasamoto, Fluctuation properties of the TASEP with periodic initial configuration, J. Stat. Phys. 129 (2007), no. 5-6, 1055–1080. MR 2363389, DOI 10.1007/s10955-007-9383-0
- Torsten Carleman, Über die Fourierkoeffizienten einer stetigen Funktion, Acta Math. 41 (1916), no. 1, 377–384 (German). Aus einem Brief an Herrn A. Wiman. MR 1555157, DOI 10.1007/BF02422951
- T. Carleman, Zur Theorie der linearen Integralgleichungen, Math. Z. 9 (1921), no. 3-4, 196–217 (German). MR 1544464, DOI 10.1007/BF01279029
- E. W. Cheney, Introduction to approximation theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR 1656150
- R. Courant and D. Hilbert, Methods of mathematical physics. Vol. I, Interscience Publishers, Inc., New York, N.Y., 1953. MR 0065391
- Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR 760629
- P. A. Deift, Orthogonal polynomials and random matrices: a Riemann-Hilbert approach, Courant Lecture Notes in Mathematics, vol. 3, New York University, Courant Institute of Mathematical Sciences, New York; American Mathematical Society, Providence, RI, 1999. MR 1677884
- Percy A. Deift, Alexander R. Its, and Xin Zhou, 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 (1997), no. 1, 149–235. MR 1469319, DOI 10.2307/2951834
- P. Deift, A. Its, and I. Krasovsky, Asymptotics of the Airy-kernel determinant, Comm. Math. Phys. 278 (2008), no. 3, 643–678. MR 2373439, DOI 10.1007/s00220-007-0409-x
- L. M. Delves and J. L. Mohamed, Computational methods for integral equations, Cambridge University Press, Cambridge, 1985. MR 837187, DOI 10.1017/CBO9780511569609
- Ronald A. DeVore and George G. Lorentz, Constructive approximation, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 303, Springer-Verlag, Berlin, 1993. MR 1261635
- Momar Dieng, Distribution functions for edge eigenvalues in orthogonal and symplectic ensembles: Painlevé representations, Int. Math. Res. Not. 37 (2005), 2263–2287. MR 2181265, DOI 10.1155/IMRN.2005.2263
- Jean Dieudonné, History of functional analysis, Notas de Matemática [Mathematical Notes], vol. 77, North-Holland Publishing Co., Amsterdam-New York, 1981. MR 605488
- Tobin A. Driscoll, Folkmar Bornemann, and Lloyd N. Trefethen, The chebop system for automatic solution of differential equations, BIT 48 (2008), no. 4, 701–723. MR 2465699, DOI 10.1007/s10543-008-0198-4
- N. Danford and Dž. Švarc, Lineĭ nye operatory. Chast′ II: Spektral′naya teoriya. Samosopryazhennye operatory v gil′bertovom prostranstve, Izdat. “Mir”, Moscow, 1966 (Russian). MR 0216304
- Freeman J. Dyson, Fredholm determinants and inverse scattering problems, Comm. Math. Phys. 47 (1976), no. 2, 171–183. MR 406201
- Eastham, M.: 1973, The spectral theory of periodic differential equations, Scottish Academic Press, Edinburgh.
- P. E. Falloon, P. C. Abbott, and J. B. Wang, Theory and computation of spheroidal wavefunctions, J. Phys. A 36 (2003), no. 20, 5477–5495. MR 1985521, DOI 10.1088/0305-4470/36/20/309
- 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.
- Ivar Fredholm, Sur une classe d’équations fonctionnelles, Acta Math. 27 (1903), no. 1, 365–390 (French). MR 1554993, DOI 10.1007/BF02421317
- 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.
- Walter Gautschi, Computation of Bessel and Airy functions and of related Gaussian quadrature formulae, BIT 42 (2002), no. 1, 110–118. MR 1896388, DOI 10.1023/A:1021974203359
- I. C. Gohberg and M. G. Kreĭn, Introduction to the theory of linear nonselfadjoint operators, Translations of Mathematical Monographs, Vol. 18, American Mathematical Society, Providence, R.I., 1969. Translated from the Russian by A. Feinstein. MR 0246142
- Israel Gohberg, Seymour Goldberg, and Marinus A. Kaashoek, Classes of linear operators. Vol. I, Operator Theory: Advances and Applications, vol. 49, Birkhäuser Verlag, Basel, 1990. MR 1130394, DOI 10.1007/978-3-0348-7509-7
- Israel Gohberg, Seymour Goldberg, and Nahum Krupnik, Traces and determinants of linear operators, Operator Theory: Advances and Applications, vol. 116, Birkhäuser Verlag, Basel, 2000. MR 1744872, DOI 10.1007/978-3-0348-8401-3
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- W. H. Greub, Multilinear algebra, Die Grundlehren der mathematischen Wissenschaften, Band 136, Springer-Verlag New York, Inc., New York, 1967. MR 0224623
- A. Grothendieck, La théorie de Fredholm, Bull. Soc. Math. France 84 (1956), 319–384 (French). MR 88665
- Wolfgang Hackbusch, Integral equations, International Series of Numerical Mathematics, vol. 120, Birkhäuser Verlag, Basel, 1995. Theory and numerical treatment; Translated and revised by the author from the 1989 German original. MR 1350296, DOI 10.1007/978-3-0348-9215-5
- Hadamard, J.: 1893, Résolution d’une question relative aux déterminants, Bull. Sci. Math. 17, 240–246.
- Jonas Hägg, Local Gaussian fluctuations in the Airy and discrete PNG processes, Ann. Probab. 36 (2008), no. 3, 1059–1092. MR 2408583, DOI 10.1214/07-AOP353
- S. P. Hastings and J. B. McLeod, A boundary value problem associated with the second Painlevé transcendent and the Korteweg-de Vries equation, Arch. Rational Mech. Anal. 73 (1980), no. 1, 31–51. MR 555581, DOI 10.1007/BF00283254
- Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
- 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.
- Einar Hille and J. D. Tamarkin, On the characteristic values of linear integral equations, Acta Math. 57 (1931), no. 1, 1–76. MR 1555331, DOI 10.1007/BF02403043
- Harry Hochstadt, Integral equations, Pure and Applied Mathematics, John Wiley & Sons, New York-London-Sydney, 1973. MR 0390680
- Michio Jimbo, Tetsuji Miwa, Yasuko Môri, and Mikio Sato, Density matrix of an impenetrable Bose gas and the fifth Painlevé transcendent, Phys. D 1 (1980), no. 1, 80–158. MR 573370, DOI 10.1016/0167-2789(80)90006-8
- Kurt Johansson, Shape fluctuations and random matrices, Comm. Math. Phys. 209 (2000), no. 2, 437–476. MR 1737991, DOI 10.1007/s002200050027
- Kurt Johansson, Discrete polynuclear growth and determinantal processes, Comm. Math. Phys. 242 (2003), no. 1-2, 277–329. MR 2018275, DOI 10.1007/s00220-003-0945-y
- R. Jost and A. Pais, On the scattering of a particle by a static potential, Phys. Rev. (2) 82 (1951), 840–851. MR 44404
- Nicholas M. Katz and Peter Sarnak, Random matrices, Frobenius eigenvalues, and monodromy, American Mathematical Society Colloquium Publications, vol. 45, American Mathematical Society, Providence, RI, 1999. MR 1659828, DOI 10.1090/coll/045
- Morris Kline, Mathematical thought from ancient to modern times, Oxford University Press, New York, 1972. MR 0472307
- Konrad Knopp, Theorie and Anwendung der unendlichen Reihen, Die Grundlehren der mathematischen Wissenschaften, Band 2, Springer-Verlag, Berlin-New York, 1964 (German). Fünfte berichtigte Auflage. MR 0183997
- Rainer Kress, Linear integral equations, 2nd ed., Applied Mathematical Sciences, vol. 82, Springer-Verlag, New York, 1999. MR 1723850, DOI 10.1007/978-1-4612-0559-3
- Dirk P. Laurie, Computation of Gauss-type quadrature formulas, J. Comput. Appl. Math. 127 (2001), no. 1-2, 201–217. Numerical analysis 2000, Vol. V, Quadrature and orthogonal polynomials. MR 1808574, DOI 10.1016/S0377-0427(00)00506-9
- Peter D. Lax, Functional analysis, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2002. MR 1892228
- Barry M. McCoy, Jacques H. H. Perk, and Robert E. Shrock, Time-dependent correlation functions of the transverse Ising chain at the critical magnetic field, Nuclear Phys. B 220 (1983), no. 1, , FS 8, 35–47. MR 702266, DOI 10.1016/0550-3213(83)90132-3
- Madan Lal Mehta, Random matrices, 3rd ed., Pure and Applied Mathematics (Amsterdam), vol. 142, Elsevier/Academic Press, Amsterdam, 2004. MR 2129906
- Carl Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. With 1 CD-ROM (Windows, Macintosh and UNIX) and a solutions manual (iv+171 pp.). MR 1777382, DOI 10.1137/1.9780898719512
- Moiseiwitsch, B.: 1977, Recent progress in atomic collisions theory, Rep. Prog. Phys. 40, 843–904.
- E. J. Nyström, Über Die Praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben, Acta Math. 54 (1930), no. 1, 185–204 (German). MR 1555306, DOI 10.1007/BF02547521
- Shin’ichi Oishi, Relationship between Hirota’s method and the inverse spectral method—the Korteweg-de Vries equation’s case, J. Phys. Soc. Japan 47 (1979), no. 3, 1037–1038. MR 548512, DOI 10.1143/JPSJ.47.1037
- Albrecht Pietsch, History of Banach spaces and linear operators, Birkhäuser Boston, Inc., Boston, MA, 2007. MR 2300779
- J. Plemelj, Zur Theorie der Fredholmschen Funktionalgleichung, Monatsh. Math. Phys. 15 (1904), no. 1, 93–128 (German). MR 1547272, DOI 10.1007/BF01692293
- Christoph Pöppe, The Fredholm determinant method for the KdV equations, Phys. D 13 (1984), no. 1-2, 137–160. MR 775282, DOI 10.1016/0167-2789(84)90274-4
- David Porter and David S. G. Stirling, Integral equations, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 1990. A practical treatment, from spectral theory to applications. MR 1111247, DOI 10.1017/CBO9781139172028
- Michael Prähofer and Herbert Spohn, Scale invariance of the PNG droplet and the Airy process, J. Statist. Phys. 108 (2002), no. 5-6, 1071–1106. Dedicated to David Ruelle and Yasha Sinai on the occasion of their 65th birthdays. MR 1933446, DOI 10.1023/A:1019791415147
- Michael Prähofer and Herbert Spohn, Exact scaling functions for one-dimensional stationary KPZ growth, J. Statist. Phys. 115 (2004), no. 1-2, 255–279. MR 2070096, DOI 10.1023/B:JOSS.0000019810.21828.fc
- Siegfried Prössdorf and Bernd Silbermann, Numerical analysis for integral and related operator equations, Mathematische Lehrbücher und Monographien, II. Abteilung: Mathematische Monographien [Mathematical Textbooks and Monographs, Part II: Mathematical Monographs], vol. 84, Akademie-Verlag, Berlin, 1991 (English, with English and German summaries). MR 1206476
- William P. Reinhardt and Attila Szabo, Fredholm method. I. A numerical procedure for elastic scattering, Phys. Rev. A (3) 1 (1970), 1162–1169. MR 266459, DOI 10.1103/PhysRevA.1.1162
- Jorge Rezende, Feynman integrals and Fredholm determinants, J. Math. Phys. 35 (1994), no. 8, 4357–4371. MR 1284645, DOI 10.1063/1.530857
- R. D. Riess and L. W. Johnson, Error estimates for Clenshaw-Curtis quadrature, Numer. Math. 18 (1971/72), 345–353. MR 305555, DOI 10.1007/BF01404685
- T. Sasamoto, Spatial correlations of the 1D KPZ surface on a flat substrate, J. Phys. A 38 (2005), no. 33, L549–L556. MR 2165697, DOI 10.1088/0305-4470/38/33/L01
- Barry Simon, Notes on infinite determinants of Hilbert space operators, Advances in Math. 24 (1977), no. 3, 244–273. MR 482328, DOI 10.1016/0001-8708(77)90057-3
- Barry Simon, Trace ideals and their applications, 2nd ed., Mathematical Surveys and Monographs, vol. 120, American Mathematical Society, Providence, RI, 2005. MR 2154153, DOI 10.1090/surv/120
- Smithies, F.: 1937, The eigen-values and singular values of integral equations, Proc. London Math. Soc. 43, 255–279.
- F. Smithies, Integral equations, Cambridge Tracts in Mathematics and Mathematical Physics, No. 49, Cambridge University Press, New York, 1958. MR 0104991
- Spohn, H.: 2008, Personal communication.
- G. W. Stewart, Matrix algorithms. Vol. I, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998. Basic decompositions. MR 1653546, DOI 10.1137/1.9781611971408
- 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.
- Paul N. Swarztrauber, On computing the points and weights for Gauss-Legendre quadrature, SIAM J. Sci. Comput. 24 (2002), no. 3, 945–954. MR 1950519, DOI 10.1137/S1064827500379690
- Craig A. Tracy and Harold Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys. 159 (1994), no. 1, 151–174. MR 1257246
- Craig A. Tracy and Harold Widom, Fredholm determinants and the mKdV/sinh-Gordon hierarchies, Comm. Math. Phys. 179 (1996), no. 1, 1–9. MR 1395215
- Craig A. Tracy and Harold Widom, Universality of the distribution functions of random matrix theory, Integrable systems: from classical to quantum (Montréal, QC, 1999) CRM Proc. Lecture Notes, vol. 26, Amer. Math. Soc., Providence, RI, 2000, pp. 251–264. MR 1791893, DOI 10.1090/crmp/026/12
- Lloyd N. Trefethen, Is Gauss quadrature better than Clenshaw-Curtis?, SIAM Rev. 50 (2008), no. 1, 67–87. MR 2403058, DOI 10.1137/060659831
- F. G. Tricomi, Integral equations, Pure and Applied Mathematics, Vol. V, Interscience Publishers, Inc., New York; Interscience Publishers Ltd., London, 1957. MR 0094665
- Vallée, O. and Soares, M.: 2004, Airy functions and applications to physics, Imperial College Press, London.
- Helge von Koch, Sur les déterminants infinis et les équations différentielles linéaires, Acta Math. 16 (1892), no. 1, 217–295 (French). MR 1554829, DOI 10.1007/BF02418991
- Jörg Waldvogel, Fast construction of the Fejér and Clenshaw-Curtis quadrature rules, BIT 46 (2006), no. 1, 195–202. MR 2214855, DOI 10.1007/s10543-006-0045-4
- Webster, A. G.: 1927, Partial differential equations of mathematical physics, G. E. Stechert & Co., New York.
- E. T. Whittaker and G. N. Watson, A course of modern analysis, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1996. An introduction to the general theory of infinite processes and of analytic functions; with an account of the principal transcendental functions; Reprint of the fourth (1927) edition. MR 1424469, DOI 10.1017/CBO9780511608759
- Harold Widom, On asymptotics for the Airy process, J. Statist. Phys. 115 (2004), no. 3-4, 1129–1134. MR 2054175, DOI 10.1023/B:JOSS.0000022384.58696.61
- Wilkinson, D.: 1978, Continuum derivation of the Ising model two-point function, Phys. Rev. D 17, 1629–1636.
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
- Received by editor(s): June 24, 2008
- Received by editor(s) in revised form: March 16, 2009
- Published electronically: September 24, 2009
- © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2600548