Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Log in
Learn more about individual access
Request company access
Electric Powertrains and Energy Systems 2025 | 26 + 27 March 2025

19th International MTZ Congress on Future Powertrains

Take this opportunity to attend the conference. Experts from the automotive industry, energy providers, and grid operators will meet up with representatives from politics and science to discuss important topics for this sector.
EXTENDED SEARCH
Log in
Top
Published in:
Read chapter Read first chapter

2024 | OriginalPaper | Chapter

Optimal Algorithms for Numerical Integration: Recent Results and Open Problems

Author : Erich Novak

Published in: Monte Carlo and Quasi-Monte Carlo Methods

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present recent results on optimal algorithms for numerical integration and several open problems. The paper has six parts:
1.
Introduction
 
2.
Lower Bounds
 
3.
Universality
 
4.
General Domains
 
5.
IID Information
 
6.
Concluding Remarks.
 

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Lattice-Based Kernel Approximation and Serendipitous Weights for Parametric PDEs in Very High Dimensions
next chapter Minimum Kernel Discrepancy Estimators
Footnotes
1
In particular, the optimal order for \(e^\textrm{ran} (A_n, H^{k,{\textrm{mix}}}_d )\), observe that there are no log terms, is a new result of Ullrich [112].
 
Literature
1.
Babenko, V.F., Babenko, Y.V., Kovalenko, O.V.: On asymptotically optimal cubatures for multidimensional Sobolev spaces. Res. Math. 29(2), 15–27 (2021)
2.
Bakhvalov, N.S.: On the approximate calculation of multiple integrals. Vestnik MGU, Ser. Math. Mech. Astron. Phys. Chem. 4, 3–18: in Russian. English translation: J. Compl. 31(502–516), 2015 (1959)
3.
Bakhvalov, N.S.: An estimate of the mean remainder term in quadrature formulae. Zh. Vych. Mat. 1(1), 64–77 (1961)
4.
Bakhvalov, N.S.: On the rate of convergence of indeterministic integration processes within the functional classes \(W^{(l)}_p\). Theor. Probab. Appl. 7, 227 (1962)
5.
Berner, J., Grohs, Ph., Kutyniok, G., Petersen, P.H.: The modern mathematics of deep learning. In: Mathematical Aspects of Deep Learning, pp. 1–111, Cambridge University Press (2022). arXiv:​2105:​04026
6.
Bartel, F., Schäfer, M., Ullrich, T.: Constructive subsampling of finite frames with applications in optimal function recovery. Appl. Comput. Harmonic Anal. 65, 209–248 (2023). arXiv:​2202.​12635
7.
Barthelmann, V., Novak, E., Ritter, K.: High dimensional polynomial interpolation on sparse grids. Adv. Comput. Math. 12, 273–288 (1999)MathSciNetCrossRef
8.
Brandolini, L., Choirat, C.H.R., Colzani, L., Gigante, G., Seri, R., Travaglini, G.: Quadrature rules and distribution of points on manifolds. Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 13, 889–923 (2014)
9.
Chernaya, E.V.: On the optimization of weighted cubature formulae on certain classes of continuous functions. East J. Approx. 1, 47–60 (1995)MathSciNet
10.
Clancy, N., Ding, Y., Hamilton, C., Hickernell, F.J., Zhang, Y.: The cost of deterministic, adaptive, automatic algorithms: cones, not balls. J. Complex. 30, 21–45 (2014)MathSciNetCrossRef
11.
Cobos, F., Kühn, Th., Sickel, W.: Optimal approximation of multivariate periodic Sobolev functions in the sup-norm. J. Funct. Anal. 270, 4196–4212 (2016)MathSciNetCrossRef
12.
13.
Creutzig, J., Wojtaszczyk, P.: Linear vs. nonlinear algorithms for linear problems. J. Complex. 20, 807–820 (2004)
14.
Dick, J.: Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series. J. Approx. Th. 183, 14–30 (2014)CrossRef
15.
Dick, J., Goda, T.: Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm. J. Comput. Appl. Math. 382, 113062 (2021). arXiv:​1912.​10651
16.
Dick, J., Goda, T., Suzuki, K.: Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate. Math. Comput. 91, 2771–2801 (2022). arXiv:​2109.​11694
17.
Dick, J., Kritzer, P., Pillichshammer, F.: Lattice Rules. Numerical Integration, Approximation, and Discrepancy. Springer Series in Computational Mathematics, vol. 58. Springer (2022)
18.
Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press (2010)
19.
Dick, J., Pillichshammer, F.: Discrepancy theory and quasi-Monte Carlo integration. In: Chen, W., Srivastav, A., Travaglini, G. (eds.), Panorama in Discrepancy Theory. Lecture Notes in Mathematics 2107, pp. 539–619. Springer (2014)
20.
Dolbeault, M., Krieg, D., Ullrich, M.: A sharp upper bound for sampling numbers in \(L_{2}\). Appl. Comput. Harmonic Anal. 63, 113–134 (2023). arXiv:​2204.​12621
21.
Dũng, D., Temlyakov, V.N., Ullrich, T.: Hyperbolic cross approximation. Advanced Courses in Mathematics—CRM Barcelona. Springer International Publishing (2018)
22.
Ebert, A., Kritzer, P., Nuyens, D., Osisiogu, O.: Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness. J. Complex. 66, 101555 (2021)MathSciNetCrossRef
23.
Ebert, A., Pillichshammer, F.: Tractability of approximation in the weighted Korobov space in the worst case setting—a complete picture. J. Complex. 67, 101571 (2021)MathSciNetCrossRef
24.
Ehler, M., Gräf, M., Oates, C.J.: Optimal Monte Carlo integration on closed manifolds. Stat. Comput. 29, 1203–1214 (2019)MathSciNetCrossRef
25.
Gnewuch, M., Wnuk, M.: Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration. J. Approx. Theory 251, 105342 (2020)MathSciNetCrossRef
26.
27.
Goda, T.: Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series. Proc. AMS 151, 3925–3933 (2023). arXiv:​2210.​06185
28.
29.
Goda, T., Dick, J.: Construction of interlaced scrambled polynomial lattice rules of arbitrary high order. Found. Comput. Math. 15, 1245–1278. arXiv:​1301.​6441
30.
Goda, T., L’Ecuyer, P.: Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights. SIAM J. Sci. Comput. 44, A2765–A2788. arXiv:​2201.​09413
31.
Goda, T., Suzuki, K.: Recent advances in higher order quasi-Monte Carlo methods. In: Discrepancy Theory, De Gruyter, pp. 69–102 (2020)
32.
33.
Goda, T., Suzuki, K., Yoshiki, T.: Optimal order quadrature error bounds for infinite-dimensional higher order digital sequences. Found. Comput. Math. 18, 433–458. arXiv:​1603.​08638
34.
35.
Heinrich, S.: Randomized approximation of Sobolev embeddings. In: Keller, A., Heinrich, S., Niederreiter, H. (eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, pp. 445–459. Springer, Berlin, Heidelberg (2008)
36.
37.
38.
39.
Heinrich, S., Novak, E., Wasilkowski, G.W., Woźniakowski, H.: The inverse of the star-discrepancy depends linearly on the dimension. Acta Arithmetica 96, 279–302 (2001)MathSciNetCrossRef
40.
Hinrichs, A., Krieg, D., Novak, E., Prochno, J., Ullrich, M.: On the power of random information. In: Hickernell, F.J., Kritzer, P. (eds.) Multivariate Algorithms and Information-Based Complexity, pp. 43–64. De Gruyter, Berlin/Boston (2020)CrossRef
41.
Hinrichs, A., Krieg, D., Novak, E., Prochno, J., Ullrich, M.: Random sections of ellipsoids and the power of random information. Trans. AMS 374, 8691–8713 (2021)MathSciNetCrossRef
42.
Hinrichs, A., Krieg, D., Novak, E., Vybíral, J.: Lower bounds for the error of quadrature formulas for Hilbert spaces. J. Complex. 65, 101544 (2021)MathSciNetCrossRef
43.
Hinrichs, A., Krieg, D., Novak, E., Vybíral, J.: Lower bounds for integration and recovery in \(L_2\). spaces. J. Complex. 72, 101662 (2022)
44.
Hinrichs, A., Novak, E., Ullrich, M.: On weak tractability of the Clenshaw Curtis Smolyak algorithm. J. Approx. Theory 183, 31–44 (2014)MathSciNetCrossRef
45.
Hinrichs, A., Novak, E., Ullrich, M., Woźniakowski, H.: The curse of dimensionality for numerical integration of smooth functions. Math. Comput. 83, 2853–2863 (2014)MathSciNetCrossRef
46.
Hinrichs, A., Novak, E., Ullrich, M., Woźniakowski, H.: The curse of dimensionality for numerical integration of smooth functions II. J. Complex. 30, 117–143 (2014)MathSciNetCrossRef
47.
Hinrichs, A., Novak, E., Ullrich, M., Woźniakowski, H.: Product rules are optimal for numerical integration in classical smoothness spaces. J. Complex. 38, 39–49 (2017)MathSciNetCrossRef
48.
Hinrichs, A., Prochno, J., Ullrich, M.: The curse of dimensionality for numerical integration on general domains. J. Complex. 50, 25–42 (2019)MathSciNetCrossRef
49.
Huber, M., Jones, B.: Faster estimates of the mean of bounded random variables. Math. Comput. Simul. 161, 93–101 (2019)MathSciNetCrossRef
50.
Kämmerer, L., Ullrich, T., Volkmer, T.: Worst-case recovery guarantees for least squares approximation using random samples. Constr. Approx. 54, 295–352 (2021)MathSciNetCrossRef
51.
Krieg, D.: Tensor power sequences and the approximation of tensor product operators. J. Complex. 44, 30–51 (2018)MathSciNetCrossRef
52.
53.
Krieg, D.: Uniform recovery of high dimensional \(C^r\)-functions. J. Complex. 50, 116–126 (2019)CrossRef
54.
55.
56.
Krieg, D., Novak, E.: A universal algorithm for multivariate integration. Found. Comput. Math. 17, 895–916 (2017)MathSciNetCrossRef
57.
Krieg, D., Novak, E., Sonnleitner, M.: Recovery of Sobolev functions restricted to IID sampling. Math. Comput. 91, 2715–2738 (2022). arXiv:​2108.​02055
58.
Krieg, D., Siedlecki, P., Ullrich, M., Woźniakowski, H.: Exponential tractability of \(L_2\)-approximation with function values. Adv. Comput. Math. 49, 18 (2023). arXiv:​2205.​04141
59.
Krieg, D., Sonnleitner, M.: Random points are optimal for the approximation of Sobolev functions. IMA J. Num. Anal. 00, 1–26 (2023). arXiv:​2009.​11275
60.
61.
Krieg, D., Ullrich, M.: Function values are enough for \(L_2\)-approximation. Found. Comput. Math. 21, 1141–1151 (2021). arXiv:​1905.​02516
62.
Krieg, D., Ullrich, M.: Function values are enough for \(L_2\)-approximation: part II. J. Complex. 66, 101569 (2021)CrossRef
63.
Krieg, D., Vybíral, J.: New lower bounds for the integration of periodic functions. J. Fourier Anal. Appl. 29, 41 (2023). arXiv:​2302.​02639
64.
Kritzer, P., Kuo, F.Y., Nuyens, D., Ullrich, M.: Lattice rules with random \(n\) achieve nearly the optimal \(\cal{O} (n^{-\alpha -1/2})\) error independently of the dimension. J. Approx. Theory 240, 96–113 (2019)MathSciNetCrossRef
65.
Kritzer, P., Woźniakowski, H.: Simple characterizations of exponential tractability for linear multivariate problems. J. Complex. 51, 110–128 (2019)MathSciNetCrossRef
66.
Kühn, T., Sickel, W., Ullrich, T.: Approximation numbers of Sobolev embeddings—sharp constants and tractability. J. Complex. 30, 95–116 (2014)MathSciNetCrossRef
67.
Kühn, T., Sickel, W., Ullrich, T.: Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence. Constr. Approx. 42, 353–398 (2015)MathSciNetCrossRef
68.
Kunsch, R.J., Novak, E., Rudolf, D.: Solvable integration problems and optimal sample size selection. J. Complex. 53, 40–67 (2019)MathSciNetCrossRef
69.
Kunsch, R.J., Rudolf, D.: Optimal confidence for Monte Carlo integration of smooth functions. Adv. Comput. Math. 45, 3095–3122 (2019)MathSciNetCrossRef
70.
Kuo, F.Y., Nuyens, D., Wilkes, L.: Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration. J. Complex. 79, 101785 (2023)MathSciNetCrossRef
71.
Leobacher, G., Pillichshammer, F.: Introduction to Quasi-Monte Carlo Integration and Applications. Springer (2014)
72.
Lu, Wanting, Wang, H.: On the power of standard information for tractability for \(L_2\)-approximation in the average case setting. J. Complex. 70, 101618 (2022)CrossRef
73.
Mathé, P.: Random approximation of Sobolev embeddings. J. Complex. 7, 261–281 (1991)
74.
Maz’ya, V.G.: Sobolev spaces with applications to elliptic partial differential equations. Grundlehren der Mathematischen Wissenschaften, vol. 342. Springer, Berlin (2011)
75.
Migliorati, G., Nobile, F.: Stable high-order randomized cubature formulae in arbitrary dimension. J. Approx. Theory 275, 105706 (2022). arXiv:​1812.​07761
76.
Müller-Gronbach, T.H., Novak, E., Ritter, K.: Monte-Carlo-Algorithmen. Springer (2012)
77.
Nagel, N., Schäfer, M., Ullrich, T.: A new upper bound for sampling numbers. Found. Comput. Math. 22, 445–468 (2020). arXiv:​2010.​00327
78.
Narcowich, F.J., Ward, J.D., Wendland, H.: Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting. Math. Comput. 74, 743–763 (2004)MathSciNetCrossRef
79.
80.
Novak, E.: Deterministic and Stochastic Error Bounds in Numerical Analysis. Lecture Notes in Mathematics 1349, Springer (1988)
81.
82.
Novak, E.: Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials. J. Complex. 15, 299–316 (1999)MathSciNetCrossRef
83.
Novak, E.: Some results on the complexity of numerical integration. In: Cools, R., Nuyens, D. (eds.), Monte Carlo and Quasi-Monte Carlo Methods, p. 163. Springer Proceedings in Mathematics and Statistics (2016)
84.
85.
Novak, E., Pillichshammer, F.: The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\). J. Complex. 79, 101760 (2023). arXiv:​2303.​01787
86.
Novak, E., Ritter, K.: High dimensional integration of smooth functions over cubes. Numer. Math. 75, 79–97 (1996)MathSciNetCrossRef
87.
Novak, E., Ritter, K.: The curse of dimension and a universal method for numerical integration. In: Nürnberger, G., Schmidt, J.W., Walz, G. (eds.), Multivariate Approximation and Splines, pp. 177–188. ISNM 125, Birkhäuser (1997)
88.
Novak, E., Ritter, K.: Simple cubature formulas with high polynomial exactness. Constr. Approx. 15, 499–522 (1999)MathSciNetCrossRef
89.
90.
Novak, E., Triebel, H.: Function spaces in Lipschitz domains and optimal rates of convergence for sampling. Constr. Approx. 23, 325–350 (2006)MathSciNetCrossRef
91.
Novak, E., Ullrich, M., Woźniakowski, H.: Complexity of oscillatory integration for univariate Sobolev spaces. J. Complex. 31, 15–41 (2015)MathSciNetCrossRef
92.
Novak, E., Ullrich, M., Woźniakowski, H., Zhang, S.: Complexity of oscillatory integrals on the real line. Adv. Comput. Math. 43, 537–553 (2017)MathSciNetCrossRef
93.
Novak, E., Ullrich, M., Woźniakowski, H., Zhang, S.: Reproducing kernels of Sobolev spaces on \({\mathbb{R}}^d\) and applications to embedding constants and tractability. Anal. Appl. 16, 693–715 (2018)
94.
Novak, E., Woźniakowski, H.: Intractability results for integration and discrepancy. J. Complex. 17, 388–441 (2001)MathSciNetCrossRef
95.
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems, Volume I: Linear Information. European Mathematical Society (2008)
96.
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems, Volume II: Standard Information for Functionals. European Mathematical Society (2010)
97.
Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems, Volume III: Standard Information for Operators. European Mathematical Society (2012)
98.
Pan, Z., Owen, A.B.: Super-polynomial accuracy of one dimensional randomized nets using the median-of-means. Math. Comput. 92, 805–837 (2023)MathSciNetCrossRef
99.
Plaskota, L.: Automatic integration using asymptotically optimal adaptive Simpson quadrature. Numer. Math. 131, 173–198 (2015)MathSciNetCrossRef
100.
Plaskota, L., Wasilkowski, G.W.: The power of adaptive algorithms for functions with singularities. J. Fixed Point Theory Appl. 6, 227–248 (2009)MathSciNetCrossRef
101.
Pozharska, K., Ullrich, T.: A note on sampling recovery of multivariate functions in the uniform norm. SIAM J. Num. Anal. 60, 1363–1384 (2022). arXiv:​2103.​11124
102.
Rudolf, D.: Explicit error bounds for Markov chain Monte Carlo. Dissertationes Mathematicae 485 (2012)
103.
Shalev-Shwartz, S.H., Ben-David, S.H.: Understanding Machine Learning. Cambridge University Press (2014)
104.
105.
Steinwart, I., Christmann, A.: Support Vector Machines. Springer, New York (2008)
106.
107.
Traub, J.F., Wasilkowski, G.W., Woźniakowski, H.: Information-Based Complexity. Academic Press (1988)
108.
Traub, J.F., Woźniakowski, H.: A General Theory of Optimal Algorithms. Academic Press (1980)
109.
Triebel, H.: Function Spaces and Wavelets on Domains. European Mathematical Society (EMS), Zürich (2008)CrossRef
110.
Triebel, H.: Bases in Function Spaces, Sampling, Discrepancy, Numerical Integration. European Mathematical Society (EMS), Zürich (2010)CrossRef
111.
Triebel, H.: Function Spaces with Dominating Mixed Smoothness. European Mathematical Society (EMS), Zürich (2019)CrossRef
112.
Ullrich, M.: A Monte Carlo method for integration of multivariate smooth functions. SIAM J. Numer. Anal. 55, 1188–1200 (2017)MathSciNetCrossRef
113.
Ullrich, M.: On the worst-case error of least squares algorithms for \(L_2\)-approximation with high probability. J. Complex. 60 (2020)
114.
115.
116.
Vybíral, J.: Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions. J. Complex. 30, 48–55 (2014)MathSciNetCrossRef
117.
118.
119.
Weyl, H.: Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen. Math. Ann. 71, 441–479 (1912)MathSciNetCrossRef
120.
Wu, Z., Graham, I.G., Ma, D., Zhang, Z.: A Filon-Clenshaw-Curtis-Smolyak rule for multi-dimensional oscillatory integrals with application to a UQ problem for the Helmholtz equation. arXiv:​2208.​10078
121.
Xu, Guiqiao: On weak tractability of the Smolyak algorithm for approximation problems. J. Approx. Theory 192, 347–361 (2015)MathSciNetCrossRef
122.
Zhang, J.: Modern Monte Carlo methods for efficient uncertainty quantification and propagation: a survey. WIREs Comput. Stat. 13, 5, 1939–5108. arXiv:​2011.​00680
123.
Zhang, S., Novak, E.: Optimal quadrature formulas for the Sobolev space \(H^1\). J. Sci. Comput. 78, 274–289 (2019)MathSciNetCrossRef
Metadata
Title
Optimal Algorithms for Numerical Integration: Recent Results and Open Problems
Author
Erich Novak
Copyright Year
2024
Book
Monte Carlo and Quasi-Monte Carlo Methods

Print ISBN: 978-3-031-59761-9

Electronic ISBN: 978-3-031-59762-6

Copyright Year: 2024

DOI
https://doi.org/10.1007/978-3-031-59762-6_5

Premium Partner

    Image Credits