弗萊瓦爾德斯演算法（Freivalds' algorithm）
/ FRY-valdz /
假設有人遞給你三個 n×n 矩陣 A、B、C，宣稱 A 乘 B 等於 C。重新計算 A 乘 B 來檢查，用 Strassen 約需 n^2.8、樸素法需 n^3——幾乎和自己做乘法一樣貴。弗萊瓦爾德斯演算法以便宜得多的方式驗證這個宣稱，只花 O(n^2) 時間，作法是根本不重算乘積，而是用一個隨機向量去抽查它。
精確地說：挑一個 n 維隨機向量 r，每個分量獨立均勻地取 0 或 1。計算 Br，再算 A(Br)，並另外算 Cr——三者都是矩陣乘向量、花 O(n^2)。比較 A(Br) 與 Cr。若 A 乘 B 真的等於 C，則 ABr 永遠等於 Cr，所以測試總是說「相等」——沒有假警報。若 A 乘 B 不等於 C，令 D = AB - C，這是一個非零矩陣；測試只在 Dr = 0 時錯說「相等」。關鍵的機率事實是：對任何固定的非零矩陣 D，一個均勻隨機的 0/1 向量 r 滿足 Dr = 0 的機率至多為二分之一。（理由：取 D 中含非零元的一列；無論 r 的其他座標是什麼，該非零元所在座標的兩個取值中，恰好一個使那列的內積為零。）所以每次執行至少以二分之一的機率抓到差異。
弗萊瓦爾德斯演算法之所以重要，是因為它是「驗證比計算容易」與「指紋法」最乾淨的例子：與其直接比較龐大物件，你比較便宜的隨機摘要，並相信不同物件鮮少摘要成相同。獨立跑 k 次；由於它是單邊的（它從不錯誤拒絕），任何一次「不相等」就是定論，而 k 次之後仍錯誤接受一個錯誤乘積的機率至多為 (1/2)^k。誠實的提醒：它是帶單邊錯誤的蒙地卡羅——它可能放過一個錯誤乘積，只是很少——而且只有每次執行使用全新獨立隨機性時，錯誤才會減半。
宣稱：2×2 單位矩陣乘上以 (2,3) 與 (4,5) 為兩列的矩陣，等於以 (2,3) 與 (4,6) 為兩列的矩陣 C——右下角應為 5，故宣稱是錯的。取 r = (0,1)：真正乘積乘 r 為 (3,5)，而 C 乘 r 為 (3,6)。兩者不同，測試正確地拒絕。取 r = (1,0) 時兩者都給 (2,4)，測試就會通過——這正是你要用全新隨機 r 重複的原因。
用隨機 r 檢查 ABr = Cr，在 O(n^2) 內驗證 A 乘 B = C——單邊錯誤，靠重複縮小錯誤。
錯誤是單邊的：正確乘積永遠通過，但錯誤乘積每次以至多二分之一的機率通過。獨立重複把它壓到 (1/2)^k，但永遠到不了零——弗萊瓦爾德斯是驗證，不是確定性的證明。