Erik Boström: An Overview of Fast Summation Methods

Abstract:

The direct evaluation of a dense matrix–vector product Ax, where A is an N×N matrix and x has length N, requires O(N^2) operations. A classical example arises in the gravitational or electrostatic N-body problem, where pairwise interactions between N particles lead to sums of this form. For large values of N, the computational cost becomes a major challenge. Simulations of atoms, stars, or molecules can be extremely expensive; runs lasting weeks on supercomputers are not uncommon, and global annual spending on computational resources reaches billions of dollars.

Methods that accelerate sums of this type from O(N^2) to O(N^α), where 1≤α<2, are referred to as fast summation methods. These algorithms achieve their efficiency through numerical and mathematical techniques such as truncated expansions, periodicity, hierarchical recursion, reuse of intermediate computations, and specialized kernel representations. To obtain optimal performance, each approximate fast method must also be supported by a theoretical error analysis.

In this talk, I will give an overview of the main ideas and essential details of the following methods:

• FFT (Fast Fourier Transform)
• NUFFT (Nonuniform Fast Fourier Transform)
• Fast Ewald summation
• FMM (Fast Multipole Method)
• DMK (Dual-space Multilevel Kernel Splitting Framework)

Research is ongoing—recent papers on fast Ewald methods and DMK have been published by our group (Ludvig and me), the KTH group, and collaborators at the Flatiron Institute.