On the numerical integration of Walsh series by number-theoretic methods

Larcher, Gerhard; Traunfellner, Claudia

doi:10.1090/S0025-5718-1994-1234426-9

On the numerical integration of Walsh series by number-theoretic methods
HTML articles powered by AMS MathViewer

by Gerhard Larcher and Claudia Traunfellner PDF

Math. Comp. 63 (1994), 277-291 Request permission

Abstract:

In analogy to the theory of good lattice points for the numerical integration of rapidly converging Fourier series, a theory for the fast numerical integration of Walsh series is developed. The basis for this theory is provided by a class of very well-distributed point sets in the s-dimensional unit cube, the so-called (t, m, s)-nets.

References

N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3–18 (Russian). MR 0115275
H. E. Chrestenson, A class of generalized Walsh functions, Pacific J. Math. 5 (1955), 17–31. MR 68659
Tom Hansen, Gary L. Mullen, and Harald Niederreiter, Good parameters for a class of node sets in quasi-Monte Carlo integration, Math. Comp. 61 (1993), no. 203, 225–234. MR 1182244, DOI 10.1090/S0025-5718-1993-1182244-1
Edmund Hlawka, Zur angenäherten Berechnung mehrfacher Integrale, Monatsh. Math. 66 (1962), 140–151 (German). MR 143329, DOI 10.1007/BF01387711
Loo Keng Hua and Yuan Wang, Applications of number theory to numerical analysis, Springer-Verlag, Berlin-New York; Kexue Chubanshe (Science Press), Beijing, 1981. Translated from the Chinese. MR 617192
N. M. Korobov, Approximate evaluation of repeated integrals, Dokl. Akad. Nauk SSSR 124 (1959), 1207–1210 (Russian). MR 0104086

Number-theoretical methods in approximate analysis

L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
Gerhard Larcher, Nets obtained from rational functions over finite fields, Acta Arith. 63 (1993), no. 1, 1–13. MR 1201615, DOI 10.4064/aa-63-1-1-13
Klaus Niederdrenk, Die endliche Fourier- und Walsh-Transformation mit einer Einführung in die Bildverarbeitung, Friedr. Vieweg & Sohn, Braunschweig, 1982 (German). Eine anwendungsorientierte Darstellung mit FORTRAN 77-Programmen. [An applications-oriented treatment with FORTRAN 77 programs]. MR 735256, DOI 10.1007/978-3-663-14178-5
Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 476679, DOI 10.1016/0001-8708(77)90028-7
Harald Niederreiter, Existence of good lattice points in the sense of Hlawka, Monatsh. Math. 86 (1978/79), no. 3, 203–219. MR 517026, DOI 10.1007/BF01659720
Harald Niederreiter, Dyadic fractions with small partial quotients, Monatsh. Math. 101 (1986), no. 4, 309–315. MR 851952, DOI 10.1007/BF01559394
Harald Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), no. 4, 273–337. MR 918037, DOI 10.1007/BF01294651
Harald Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), no. 1, 51–70. MR 960233, DOI 10.1016/0022-314X(88)90025-X
Harald Niederreiter, Low-discrepancy point sets obtained by digital constructions over finite fields, Czechoslovak Math. J. 42(117) (1992), no. 1, 143–166. MR 1152177

Existence theorems for efficient lattice rules

I. F. Šarygin, Lower bounds for the error of quadrature formulas on classes of functions, Ž. Vyčisl. Mat i Mat. Fiz. 3 (1963), 370–376 (Russian). MR 150952
I. M. Sobol′, Distribution of points in a cube and approximate evaluation of integrals, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 784–802 (Russian). MR 219238
I. M. Tsobol′, Mnogomernye kvadraturnye formuly i funktsii Khaara, Izdat. “Nauka”, Moscow, 1969 (Russian). MR 0422968
S. K. Zaremba, La méthode des “bons treillis” pour le calcul des intégrales multiples, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 39–119 (French, with English summary). MR 0343530