lattice
lattice 🚧
lattice basis reduction 🚧
closest vector problem 🚧
integer relation 🚧
lattice counting 🚧

lattice 🚧

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 🚧

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 🚧

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 🚧

integer relation

《 Computational excursions in analysis and number theory 》

演算法( Lenstra–Lenstra–Lovasz algorithm )

演算法( HJLS algorithm )

演算法( PSLQ algorithm )

lattice counting 🚧

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

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

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