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

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

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

《 Computational excursions in analysis and number theory 》

演算法（ Lenstra–Lenstra–Lovasz algorithm ）

演算法（ HJLS algorithm ）

演算法（ PSLQ algorithm ）

計算半平面交內部格點數目（ Barvinok's algorithm ）

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

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