快速泊松求解器（fast Poisson solver）
/ PWAH-sawn /
泊松方程——找一個位勢 u，使其曲率（拉普拉斯算子作用）等於給定的源，寫成 u 的拉普拉斯等於 f——是全科學中最常被求解的方程之一：它支配靜電、重力、穩態熱、流體模擬中的壓力步驟，以及影像編輯。在 N 乘 N 的格上離散化後，它變成一個有數百萬未知數的龐大線性系統。快速泊松求解器利用該系統的特殊結構，用 FFT 以近乎最優的時間求解它。
洞見在於：規則格上的標準五點拉普拉斯是一個卷積算子，而 FFT 把卷積對角化。用平實步驟說：取右端 f 的 FFT 以進入頻率空間；在那裡，原本是糾纏稀疏矩陣的微分算子，變成單純的乘法——每個傅立葉模態只是被一個依其頻率而定的已知數縮放（對離散拉普拉斯，大約是一些 (2 - 2*cos) 項之和）。所以你把轉換後的源「除以」那個數，便還原出解的每個傅立葉係數，每個模態一次獨立的除法；然後反 FFT 回到物理空間。整個求解每維花 O(N log N)——對一個觸及每個格點的方法而言，幾乎是可能的最便宜。使用正弦或餘弦轉換的變體則處理狄利克雷或諾依曼邊界條件，而非週期性的。
快速泊松求解器是大規模模擬的基石：不可壓縮流體程式每個時間步都呼叫一次以強制無散度速度，許多影像與幾何演算法也倚賴它。誠實的適用範圍很重要。純 FFT 求解器之所以快，正是因為它假設矩形（或週期）區域上的「簡單、規則」格與常係數；不規則幾何、變係數或不尋常的邊界會破壞那乾淨的對角化，此時你退回多重網格法或預條件 Krylov 求解器，它們以相當的 O(N) 成本處理一般問題，但機制更多。然而在適用之處，FFT 泊松求解器難以匹敵。
在 1024 乘 1024 的週期格上解 u 的拉普拉斯等於 f——超過一百萬個未知數。直接稠密求解完全不可能（約 10^18 次運算）。FFT 法以三趟轉換加上一百萬次純量除法完成，約 10^8 次運算——快到足以在流體模擬的每一步內運行。
FFT 把拉普拉斯對角化——解泊松方程變成每個傅立葉模態一次除法。
FFT 泊松求解器需要規則格、常係數與簡單邊界；不規則幾何或變係數會破壞對角化，此時多重網格法或預條件 Krylov 法以相當的成本接手。