Lattice rule algorithms for multivariate approximation in the average case setting. (English) Zbl 1141.65012
Lattice rule algorithms for the purpose of approximating continuous functions in several variables are studied. Here, the number of unknowns may be very large. The dependence of the function to be approximated on its various components can be weighted by a weight factor, which may mean that the function depends strongly or weakly on that component of its argument. The approximation is fixed by the function values at lattice points. The lattice is generated by an algorithm and depends on the approximand.
The tractability of the problem is of special interest, and necessary and sufficient conditions for tractability or strong tractability are derived. Methods for generating the lattice and for generating vectors e.g. for integration are provided, too. Many numerical results illustrate the theory.
The tractability of the problem is of special interest, and necessary and sufficient conditions for tractability or strong tractability are derived. Methods for generating the lattice and for generating vectors e.g. for integration are provided, too. Many numerical results illustrate the theory.
Reviewer: Martin D. Buhmann (Gießen)
MSC:
| 65D15 | Algorithms for approximation of functions |
| 41A30 | Approximation by other special function classes |
| 41A63 | Multidimensional problems |
Keywords:
multivariate approximation; lattice rule algorithms; average case error; tractability; numerical resultsReferences:
| [1] | F. J. Hickernell, G. W. Wasilkowski, H. Woźniakowski, Tractability of linear multivariate problems in the average case setting, in: A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi- Monte Carlo Methods 2006, Springer, to appear.; F. J. Hickernell, G. W. Wasilkowski, H. Woźniakowski, Tractability of linear multivariate problems in the average case setting, in: A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi- Monte Carlo Methods 2006, Springer, to appear. · Zbl 1141.65335 |
| [2] | Hickernell, F. J.; Woźniakowski, H., Integration and approximation in arbitrary dimensions, Adv. Comput. Math., 12, 25-58 (2000) · Zbl 0939.41004 |
| [3] | Kuo, F. Y., Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity, 19, 301-320 (2003) · Zbl 1027.41031 |
| [4] | Kuo, F. Y.; Sloan, I. H.; Woźniakowski, H., Lattice rules for multivariate approximation in the worst case setting, (Niederreiter, H.; Talay, D., Monte Carlo and Quasi-Monte Carlo Methods 2004 (2006), Springer: Springer Berlin), 289-330 · Zbl 1097.65133 |
| [5] | Li, D.; Hickernell, F. J., Trigonometric spectral collocation methods on lattices, (Cheng, S. Y.; Shu, C.-W.; Tang, T., Recent Advances in Scientific Computing and Partial Differential Equations, AMS Series in Contemporary Mathematics, vol. 330 (2003), American Mathematical Society: American Mathematical Society Providence, RI), 121-132 · Zbl 1036.65093 |
| [6] | Novak, E.; Sloan, I. H.; Woźniakowski, H., Tractability of approximation for weighted Korobov spaces on classical and quantum computers, Found. Comput. Math., 4, 121-156 (2004) · Zbl 1072.81014 |
| [7] | Novak, E.; Woźniakowski, H., When are integration and discrepancy tractable?, (DeVore, R. A.; Iserles, A.; Süli, E., Foundation of Computational Mathematics, Oxford 1999 (2001), Cambridge University Press: Cambridge University Press Cambridge), 211-266 · Zbl 0978.65014 |
| [8] | Nuyens, D.; Cools, R., Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces, Math. Comput., 75, 903-920 (2006) · Zbl 1094.65004 |
| [9] | Shilov, G. E.; Tin, F. D., Integral Measure and Derivative on Linear Spaces (1967), Nauka: Nauka Moscow, (in Russian) |
| [10] | Sloan, I. H.; Joe, S., Lattice Methods for Multiple Integration (1994), Oxford University Press: Oxford University Press Oxford · Zbl 0855.65013 |
| [11] | Sloan, I. H.; Kuo, F. Y.; Joe, S., On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces, Math. Comput., 71, 1609-1640 (2002) · Zbl 1011.65001 |
| [12] | Sloan, I. H.; Kuo, F. Y.; Joe, S., Constructing randomly shifted lattice rules in weighted Sobolev spaces, SIAM J. Numer. Anal., 40, 1650-1665 (2002) · Zbl 1037.65005 |
| [13] | Sloan, I. H.; Reztsov, A. V., Component-by-component construction of good lattice rules, Math. Comput., 71, 263-273 (2002) · Zbl 0985.65018 |
| [14] | Sloan, I. H.; Woźniakowski, H., Tractability of multivariate integration for weighted Korobov classes, J. Complexity, 17, 697-721 (2001) · Zbl 0998.65004 |
| [15] | Traub, J. F.; Wasilkowski, G. W.; Woźniakowski, H., Information-Based Complexity (1988), Academic Press: Academic Press New York · Zbl 0674.68039 |
| [16] | Traub, J. F.; Werschulz, A. G., Complexity and Information (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0917.68094 |
| [17] | Vakhania, N. N., Probability Distributions on Linear Spaces (1981), North-Holland: North-Holland New York · Zbl 0481.60002 |
| [18] | Wasilkowski, G. W.; Woźniakowski, H., On the power of standard information for weighted approximation, Found. Comput. Math., 1, 417-434 (2001) · Zbl 1001.41013 |
| [19] | Zeng, X. Y.; Leung, K. T.; Hickernell, F. J., Error analysis of splines for periodic problems using lattice designs, (Niederreiter, H.; Talay, D., Monte Carlo and Quasi-Monte Carlo Methods 2004 (2006), Springer: Springer Berlin), 501-514 · Zbl 1097.65027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
