MuST: the multilevel sinc transform. A fast multilevel algorithm (MuST) for evaluating an n-sample sinc interpolant at mn points is presented. For uniform grids, its complexity is 25mnlog(1/δ) flops for the sinc kernel and 75mnlog(1/δ) for the sincd kernel, where δ is the target evaluation accuracy. MuST is faster than fast Fourier transform- and fast multiple method-based evaluations for large n and/or for large δ. It is also applicable to nonuniform grids and to other kernels. Numerical experiments demonstrating the algorithm’s practicality are presented.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element