有哪些十分精巧的數值演算法？

01-07

例如大神級別的卡馬克平方根倒數速算演算法，以及還可以推廣至平方根演算法。
FFT也算是吧，大幅減少運算量。
除此以外，還有哪些十分精巧（如快速或者精確）的數值演算法？（出現在一本普通的數值分析教材里的演算法不算，因為通常這些演算法還能夠進一步優化）

FFT解泊松類方程

共軛梯度，krylov子空間類

qr迭代+雙重隱式位移加速

反冪法

multigrid

自適應有限元

小波快速分解重建

bb演算法

我在想一下來回答

判斷是否是平方數

1+3

1+3+5

1+3+5+7

....

計算矩陣特徵值的一個大類演算法。

Projection Methods。

特別Krylov子空間演算法。

這一類裡面有著名的conjugate gradient

MINRES，GMRES。

現在可能GMRES更popular吧。

還有冪法（power methods）。

也是算特徵值的。

只要兩到三步迭代就可以有一個大致的特徵值估計。缺點是只能估計絕對值最大的特徵值。冪法的變形有很多。

至於multigrid。我就是做multigrid的。

這個算是一大類，叫multilevel。

本身的idea也是非常精妙的，歷史不久，60年代前蘇聯數學家提出來的。

我說的這些都是數學上的演算法。我想還有很多很巧妙的別的領域的演算法。不了解就不多說了。

多項式求根的快速QR法

多項式的根等價於友矩陣的特徵值。直接對多項式的友矩陣用QR迭代的話每一步複雜度至少為O(n^2)，而快速QR利用了友矩陣的特殊結構(酉矩陣的秩1修正)，把運算量直接削到了O(n)。可惜前面的係數太大沒什麼用(

矩陣計算六講2.3節有詳細論述。