多重網格法（multigrid method）

每一個離散化的橢圓型偏微分方程——有限元素或有限差分的拉普拉斯算子——都留給你一個巨大的稀疏線性方程組要解，常達數百萬未知量。古典的迭代求解器如高斯-賽德爾有個惱人的缺陷：它們幾趟掃描就壓垮誤差中的高頻、鋸齒部分，但誤差中平滑、大尺度的部分卻幾乎不動，於是收斂爬行到近乎停滯。多重網格是優雅的解藥，也是少數能以正比於未知量數目的時間求解此類系統的演算法之一——最佳複雜度，你所能盼望的最好。

關鍵洞見是「在細網格上平滑」在「粗網格上看起來粗糙」。細網格平滑器碰不到的平滑誤差，一旦你在間距加倍的網格上觀看，就變成高頻、因而容易消滅。於是多重網格在一層層網格上對付誤差。V 循環如此進行：在細網格上施加幾趟平滑掃描（在那裡消滅高頻誤差），算出剩餘的殘差，把它「限制」到較粗的網格上（平均到較少的點上），在那裡求解較小的問題以得到平滑誤差——遞迴地，越來越粗，直到網格小到可直接求解——再把那個修正「延拓」（內插）回上層，加到細網格解上，最後再做幾趟平滑掃描以清理內插誤差。誤差的每一個頻段，都在最容易移除它的網格上被處理。

報酬戲劇性十足：一個調校良好的多重網格求解器，收斂到固定精度所需的循環數「不」隨網格加密而增長，給出 O(N) 的總工作量——而單網格迭代法隨 N 增長需要越來越多次迭代，直接稀疏求解的擴展性更差。它是橢圓型問題的黃金標準求解器，也是許多大型模擬的內核引擎。提醒是真實的：古典（幾何）多重網格需要一層層巢狀網格，對良好的橢圓算子效果最佳；對非結構化網格、跳變係數或非橢圓型問題，它可能退化，這正是代數多重網格（AMG，僅從矩陣本身建立粗層、無需網格）與「以多重網格作前處理子」被發展出來的原因。