快速多極法（fast multipole method）

假設你必須計算 N 顆恆星彼此施加的重力拉扯，或 N 個電荷之間的靜電力。樸素地做，N 個物體中的每一個都與其他每一個交互作用，即 N^2 次成對計算——僅十萬個物體就是一千億次，對星系模擬中的數百萬個更是無望。快速多極法是一項分治的突破，它以選定的精度計算所有那些交互作用，只需 O(N) 或 O(N log N) 的工作，與 FFT 並列為上個世紀的頂尖演算法之一。

關鍵想法利用距離。一個遙遠物體群的詳細位置對你幾乎無關緊要——從夠遠處看，一整個星系的恆星拉扯起來幾乎就像其中心的一個點質量，外加小修正。FMM 用「多極展開」把這點精確化：它用一個緊湊的級數（領頭項是總質量或電荷，後續項捕捉其分布與形狀）來總結一個遙遠源群的合併影響。它把空間組織成階層的格子（一棵樹），每個格子算一個多極摘要，讓遙遠的格子透過這些便宜的摘要交互作用、而非逐體；只有真正鄰近的物體才用直接的成對求和處理。在樹上下平移與組合這些展開，並帶有可控的截斷誤差，正是把 N^2 成本塌縮到近乎線性的關鍵。

與 FFT 不同，FMM 是一種精度可調的「近似」——在多極展開中保留更多項以得到更多位數，代價更高——這就是誠實的取捨。它在隨距離平滑衰減的長程交互作用上大放異彩：N 體與分子模擬中的重力與靜電，以及聲學與電磁學中邊界積分方程所得的稠密線性系統。它對僅短程的力沒有幫助（那裡直接求和本就便宜），而它的樹狀記帳帶有實質的實作複雜度與常數因子開銷，所以線性的擴展只有在 N 夠大時才決定性地獲勝。把它與小波並提——同屬讓先前不可能的計算變成例行公事的「快速轉換」想法。