The DOI matches its Crossref record.
Fast Fourier Transforms for Nonequispaced Data, II
Open accessAbstract
A group of algorithms generalizing the fast Fourier transform to the case of noninteger frequencies and nonequispaced nodes on the interval [-π, π] is presented. The schemes of this paper are based on a combination of the classical fast Fourier transform with a version of the fast multipole method, and generalize both the forward and backward FFTs. Each of the algorithms requires O(N · logN + N · log(l/ϵ)) arithmetic operations, where ϵ is the precision of computations and N is the number of nodes; the CPU time requirement of the method is independent of the distribution of the nodes. The efficiency of the scheme is illustrated by several numerical examples. The approach of this paper is compared to the approach taken by Dutt et al. ("Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation," Tech. Rep. 977, Department of Computer Science, Yale University, 1993) to the same set of problems. It turns out that the scheme of Dutt et al. is preferable for the forward problem, while the method introduced here is considerably more efficient for the inverse one.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Fast Discrete Curvelet Transforms
Candès, E., Demanet, L., Donoho, D., & Ying, L. (2006) · Multiscale Modeling & Simulation · doi:10.1137/05064182x · Cited by 2,573
Nonuniform fast fourier transforms using min-max interpolation
Fessler, J. A., & Sutton, B. P. (2003) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2002.807005 · Cited by 1,337
Fast Direct Methods for Gaussian Processes
Ambikasaran, S., Foreman-Mackey, D., Greengard, L., Hogg, D. W., & O'Neil, M. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2448083 · Cited by 669
Using NFFT 3---A Software Library for Various Nonequispaced Fast Fourier Transforms
Keiner, J., Kunis, S., & Potts, D. (2009) · ACM Transactions on Mathematical Software · doi:10.1145/1555386.1555388 · Cited by 367
Metadata
- Authors
- Dutt, A., & Rokhlin, V.
- Venue
- Applied and Computational Harmonic Analysis
- Publisher
- Elsevier BV
- Published
- 1995-01
- Volume
- 2
- Issue
- 1
- Pages
- 85-100
- ISSN
- 1063-5203 (ISSN-L)
- OpenAlex
- W1998152471
- Cited by
- 193
- References
- 0
- FWCI
- 5.31
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.