Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


A multivariate fast discrete Walsh transform with an application to function interpolation
HTML articles powered by AMS MathViewer

by Kwong-Ip Liu, Josef Dick and Fred J. Hickernell PDF
Math. Comp. 78 (2009), 1573-1591 Request permission


For high dimensional problems, such as approximation and integration, one cannot afford to sample on a grid because of the curse of dimensionality. An attractive alternative is to sample on a low discrepancy set, such as an integration lattice or a digital net. This article introduces a multivariate fast discrete Walsh transform for data sampled on a digital net that requires only $\mathcal {O}(N \log N)$ operations, where $N$ is the number of data points. This algorithm and its inverse are digital analogs of multivariate fast Fourier transforms.

This fast discrete Walsh transform and its inverse may be used to approximate the Walsh coefficients of a function and then construct a spline interpolant of the function. This interpolant may then be used to estimate the function’s effective dimension, an important concept in the theory of numerical multivariate integration. Numerical results for various functions are presented.

Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2000): 42C10, 41A15
  • Retrieve articles in all journals with MSC (2000): 42C10, 41A15
Additional Information
  • Kwong-Ip Liu
  • Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong, People’s Republic of China
  • Email:
  • Josef Dick
  • Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney 2052, Australia
  • Email:
  • Fred J. Hickernell
  • Affiliation: Department of Applied Mathematics, Illinois Institute of Technology, Room E1-208, 10 W. 32nd Street, Chicago, Illinois 60616
  • ORCID: 0000-0001-6677-1324
  • Email:
  • Received by editor(s): January 11, 2008
  • Received by editor(s) in revised form: July 29, 2008
  • Published electronically: January 9, 2009
  • Additional Notes: This research was supported in part by the Hong Kong Research Grants Council grant HKBU/2009/04P, the HKSAR Research Grants Council Project No. HKBU200605 and the United States National Science Foundation grant NSF-DMS-0713848.
  • © Copyright 2009 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Math. Comp. 78 (2009), 1573-1591
  • MSC (2000): Primary 42C10, 41A15
  • DOI:
  • MathSciNet review: 2501064