Lattice(Under Construction!)

Lattice

給定一組向量,作為座標軸,嘗試畫出座標格線。整數倍位置,稱作「晶格」。

N個向量必須產生N維空間!向量不得共點、共線、共面、……,以免空間萎縮。

大家習慣令向量數值是整數,增進討論意義。

http://cseweb.ucsd.edu/classes/wi12/cse206A-a/
http://cseweb.ucsd.edu/classes/wi10/cse206a/
http://people.csail.mit.edu/vinodv/CS294/

Lattice Basis Reduction(Under Construction!)

Lattice Basis Reduction

https://en.wikipedia.org/wiki/Lattice_reduction

正交化。找到一組晶格向量,盡量互相垂直。

演算法(Lagrange's Algorithm)

兩個向量的演算法。教科書以此作為引言。

長向量投影到短向量。短向量乘上(四捨五入的)伸縮倍率,得到(偏移的)投影向量。長向量減去(偏移的)投影向量,變得(更加的)垂直。

不斷相互投影,直到投影之後長度大小關係不變。

可以視作輾轉相除法。

while (true)
{
    if (‖b₁‖ > ‖b₂‖) swap(b₁, b₂);  // b₂ is longer
    s = dot(b₁, b₂) / ‖b₁‖²;
    s = round(s);
    b₂ = b₂ - (s * b₁);             // b₂ project to b₁
    if (‖b₁‖ ≤ ‖b₂‖) break;         // b₂ is still longer
}

演算法(Hermite's Algorithm)

https://cs.uwaterloo.ca/~cbright/reports/latticealgs.pdf

演算法(Lenstra–Lenstra–Lovasz Algorithm)

https://math.pro/db/thread-1876-1-1.html

https://zhuanlan.zhihu.com/p/336840687

Closest Vector Problem(Under Construction!)

Shortest Vector Problem

https://en.wikipedia.org/wiki/Lattice_problem

找到長度最短的晶格向量。NP-hard。

利用Lattice Basis Reduction快速找到近似解。

Closest Vector Problem

針對一個非晶格向量,找到距離最近的晶格向量。NP-hard。

利用Shortest Vector Problem快速找到近似解。

Integer Relation(Under Construction)

Integer Relation

《Computational excursions in analysis and number theory》

演算法(Lenstra–Lenstra–Lovasz Algorithm)

演算法(HJLS Algorithm)

演算法(PSLQ Algorithm)

Lattice Counting(Under Construction)

計算半平面交內部格點數目(Barvinok's Algorithm)

整數一次不等式組的解數量。

https://en.wikipedia.org/wiki/Minkowski's_theorem