对于低维格, one can solve SVP efficiently as Euclid's algorithm.
高维格,
exact algorithm
provably find a SV, but EXPENSIVE
- intuitively, these algorithms perform exhausive search of all extremely short vectors, whose number 关于维度指数 in worst case
- best deterministic algorithm: Kannan's enumeration, with super-exp complexity(最坏情形), let n = dim, n^(n/2e + O(n)).
- best randomized algorithm: sieve of Ajtai, Kumar, and Sivakumar(AKS) 2^(O(n)), require exp space
approximation algorithm
len(appr SV)<=f(dim)λ1
LLL: 可视为Hermite's 不等式的算法版本
blockwise algorithm of Gama and Nguyen: Mordell's 不等式的算法版本
in high dim(say, higher than 150), only appr algorithms are practical.
对于高维格, 只有近似算法在实践上有意义.
但是这两种类型的算法是互补的:
- 所有精确算法, 首先应用近似算法(至少LLL)作为一个预处理的过程.
- 所有近似算法, 在低维度的情形调用多次精确算法作为subroutine
精确算法的分析: 数ball里的格点数目
background
Gram矩阵
input: b1,...,bm of R^n
output: a matrix of R[m][m], entry(i,j) inner product (bi,bj)
Gram行列式
△(b1,...,bm)=det(Gram(b1,...,bm))
basic properties:
- 行列式值总是非负的, 等于0 iff 向量是线性相关的
- 幺模变换of b1,...,bm不改变行列式的值
- geometric interpretation: 向量线性无关, 则行列式开根号得到基本平行多面体的体积
vn: n维单位球的体积
定义: R^n的子集说是离散的, 如果这个子集里面没有limit point, 以子集D里的任一点x为球心, 存在某半径r, 使得在这个球里的子集里的点只有球心一点.
Z^n是离散的
Qn和Rn不是
{1/n:n为正整数}是离散的
{0}U{1/n:n为正整数}不是
离散集的子集是离散的
