A fast procedure for the construction of quadrature formulas for bandlimited functions

We introduce an efficient scheme for the construction of quadrature rules for bandlimited functions. While the scheme is predominantly based on well-known facts about prolate spheroidal wave functions of order zero, it has the asymptotic CPU time estimate O(n log n) to construct an n-point quadrature rule. Moreover, the size of the n log n term in the CPU time estimate is small, so for all practical purposes the CPU time cost is proportional to n. The performance of the algorithm is illustrated by several numerical examples. & COPY; 2023 Elsevier Inc. All rights reserved.

Automated summary

We present an efficient scheme for constructing quadrature rules for bandlimited functions using prolate spheroidal wave functions of order zero. The scheme has an asymptotic CPU time estimate of O(n log n) to generate an n-point quadrature rule. Additionally, the CPU time cost is proportional to n for practical purposes due to the small size of the n log n term in the estimate. The algorithm's performance is demonstrated with numerical examples.