Fast summation based on fast trigonometric transforms at non‐equispaced nodes
Markus Fenn, Daniel Potts · Numerical Linear Algebra with Applications · 2004
Abstract We develop a new algorithm for the fast computation of matrix–vector products with special matrices. More precisely we develop a method for the fast computation of sums f ( y j ):= ∑ α k K ( y j − x k ) at non‐equispaced nodes x k and y j ( j =1,…, M ) which requires only 𝒪( N log N + ( M + N )) arithmetic operations. Our algorithm is based on a novel approach to fast discrete trigonometric transforms at non‐equispaced nodes. Copyright © 2004 John Wiley & Sons, Ltd.