托馬斯演算法

許多問題給你的矩陣幾乎全是零，只有主對角線與緊鄰的兩條對角線上有非零——三對角矩陣。每當每個未知數只與它的緊鄰耦合時（如一維熱傳方程或三次樣條），就會出現這種形狀。托馬斯演算法正是針對這種結構、快得驚人的高斯消去法特化版。

它就是忽略所有結構性零的消去。往前掃描時，每一列的消去只觸及對角線下方那一個元素，所以整個前向消去是一個短迴圈，原地更新對角線與右端；接著一次回代掃描由下而上還原各未知數。由於每列只有常數量的算術，整個求解花 O(n) 次浮點運算與 O(n) 儲存——線性，而非稠密求解的 O(n^3) 與 O(n^2)。對一個百萬未知數的三對角系統，這就是瞬間完成與不可能之間的差別。

托馬斯演算法是利用稀疏性的典範案例：當矩陣有已知的纖細結構時，你把消去量身配合它，成本就劇烈崩降。它推廣到帶狀矩陣（寬幾條對角線），對帶寬 b 成本為 O(n b^2)。兩個誠實的注意點：和純高斯消去法一樣它不做樞紐選擇，所以一般情況下可能不穩定——但對常見的對角佔優或對稱正定三對角矩陣，它可證明穩定，而這正是實務中大多數的情況；若在沒有這些保證下某個樞紐變零或極小，你就必須退回到有樞紐選擇的求解器。