the fast multipole method
Suppose you must compute the gravitational pull that N stars exert on each other, or the electrostatic force among N charges. Done naively, every one of the N bodies interacts with every other, which is N^2 pairwise computations — a hundred billion for just a hundred thousand bodies, and hopeless for the millions in a galaxy simulation. The fast multipole method is a divide-and-conquer breakthrough that computes all those interactions to a chosen accuracy in only O(N) or O(N log N) work, and it stands beside the FFT as one of the top algorithms of the last century.
The key idea exploits distance. The detailed positions of a faraway cluster of bodies barely matter to you — from far enough away, a whole galaxy of stars pulls almost exactly like a single point mass at its centre, plus small corrections. The FMM makes this precise with a MULTIPOLE EXPANSION: it summarizes the combined influence of a distant group of sources by a compact series (the leading term is the total mass or charge, the next terms capture its spread and shape). It organizes space into a hierarchy of cells (a tree), computes one multipole summary per cell, and lets distant cells interact through these cheap summaries rather than body-by-body; only genuinely nearby bodies are handled by direct pairwise sums. Translating and combining these expansions up and down the tree, with a controllable truncation error, is what collapses the N^2 cost to nearly linear.
Unlike the FFT, the FMM is an APPROXIMATION with a tunable accuracy — keep more terms in the multipole expansion for more digits, at more cost — and that is the honest trade. It shines for long-range interactions that fall off smoothly with distance: gravitation and electrostatics in N-body and molecular simulations, and the dense linear systems from boundary-integral equations in acoustics and electromagnetics. It does not help with short-range-only forces (where direct summation is already cheap), and its tree bookkeeping carries a real implementation complexity and constant-factor overhead, so the linear scaling wins decisively only once N is large. Mention it alongside wavelets as another of the 'fast transform' ideas that made previously impossible computations routine.
Simulate a million-body galaxy. Direct force summation is 10^6 squared = 10^12 pair interactions per step — days of computing. The FMM groups distant stars into multipole summaries and computes the same forces, to several accurate digits, in about 10^6 to 10^7 operations per step, turning an intractable problem into a routine one.
Summarize distant groups by a multipole expansion — N^2 collapses to nearly O(N).
Unlike the FFT, the FMM is approximate: accuracy is a dial you set by the number of expansion terms, traded against cost. Its tree overhead and large constant factor mean it only beats direct summation once N is genuinely large.