从高位近似基向原基传递换基矩阵#

在浮点 LLL 的精度与正确性中，原基 $B$ 精确保留，工作精度 $w$ 决定投影和取整算得多准。当 $B$ 的整数条目有几千位时，可以先用各列的高位选出整数列操作，再把这些操作施于完整的 $B$。输入保留的位数 $p$ 和工作精度 $w$ 可以分别选择。若各列的尺度仍相差很大，还可以通过分块缩放减小计算中的整数。

#近似基上选出的换基矩阵可以用于原基

设原基 $B=[b_1,\ldots,b_n]\in\mathbb Z^{m\times n}$ 列满秩。保留各列的高位，得到矩阵 $\widetilde B=[\tilde b_1,\ldots,\tilde b_n]$。若 $\widetilde B$ 仍列满秩，就称它为近似基。近似基生成的格 $\widetilde B\mathbb Z^n$ 可以与原格 $B\mathbb Z^n$ 不同。

在近似基上选出整数换基矩阵 $U\in\mathrm{GL}_n(\mathbb Z)$。近似基的换基结果为 $\widetilde C=\widetilde B U$，原基的换基结果为 $C=BU$。由于 $U\mathbb Z^n=\mathbb Z^n$，$C$ 一定生成原格。还要判断 $\widetilde C$ 满足的约化条件能在多大程度上传给 $C$。

取下面的二维原基 $B$。它的条目均非负，将每个条目向下截到 $32$ 的倍数，相当于舍去最低 5 个二进制位，得到近似基 $\widetilde B$。

$$B=\begin{pmatrix}32&97\\0&33\end{pmatrix},\qquad \widetilde B=\begin{pmatrix}32&96\\0&32\end{pmatrix} =32\begin{pmatrix}1&3\\0&1\end{pmatrix}.$$

把 $\widetilde B$ 整体除以 $32$，尺寸约化系数和 Lovász 检查中的高度比都不变，因此可以在小整数矩阵 $\widetilde B/32$ 上选择列操作。将第二列减去第一列的三倍，得到

$$U=\begin{pmatrix}1&-3\\0&1\end{pmatrix},\qquad \widetilde C=\widetilde B U=\begin{pmatrix}32&0\\0&32\end{pmatrix},\qquad C=BU=\begin{pmatrix}32&1\\0&33\end{pmatrix}.$$

前面的列操作是在近似基上选出的。现在用完整的原基验算结果。$\widetilde C$ 和 $C$ 的行列式分别为 $1024$ 和 $1056$，截去的低位体现在 $C$ 的第二列 $(1,33)^T$ 中。在 $C$ 上算得 $\mu_{2,1}=1/32$，满足尺寸约化条件。取 $\delta=3/4$，Lovász 条件为 $\tfrac34\cdot 32^2\le 1^2+33^2$，即 $768\le 1090$。

#逐列截断可能丢失短方向

换基矩阵 $U$ 的第二列 $x=(-3,1)^T$ 记录了刚才的列操作。同一组系数在原基上给出 $Bx=(1,33)^T$，在近似基上给出 $\widetilde Bx=(0,32)^T$。截断保留了第一列，第二列从 $(97,33)^T$ 变成 $(96,32)^T$。逐列用截断值减去原值，得到截断误差矩阵

$$E:=\widetilde B-B=\begin{pmatrix}0&-1\\0&-1\end{pmatrix}.$$

对任意系数向量 $x$，都有 $\widetilde Bx-Bx=Ex$。在刚才的方向上，$Ex=(-1,-1)^T$，相对误差为 $\|Ex\|_2/\|Bx\|_2=\sqrt{2}/\sqrt{1090}\approx 4.3\%$。

再看上一篇近乎平行的两列 $b_1=(N,1)^T$ 和 $b_2=(N+1,1)^T$，取 $N=2^k$。若只将 $N+1$ 舍成 $N$，第二列的相对误差随 $N$ 增大而趋于零。此时取 $x=(-1,1)^T$ 做两列之差，原来有 $Bx=(1,0)^T$，误差却恰好是 $Ex=(-1,0)^T=-Bx$。这个方向上的相对误差为 $1$，原来的短向量被截成了零。截断所得的矩阵 $\widetilde B$ 两列重合，秩从 $2$ 降为 $1$。

这两个例子都用整数系数，计算投影高度还会用到实系数。为了比较同一组系数在两组基上产生的向量，定义所有方向上的最大相对误差

$$\varepsilon=\sup_{x\in\mathbb R^n,\ x\ne0} \frac{\|Ex\|_2}{\|Bx\|_2}.$$

$B$ 列满秩，保证了分母非零。若 $\varepsilon<1$，由三角不等式，对每个实系数向量 $x$ 都有

$$(1-\varepsilon)\|Bx\|_2 \le\|\widetilde Bx\|_2 \le(1+\varepsilon)\|Bx\|_2.$$

当 $x\ne0$ 时，下界为正，所以 $\widetilde B$ 仍列满秩。换基后令 $x=Uy$，就能用同一个 $\varepsilon$ 比较 $\|\widetilde C y\|_2$ 和 $\|C y\|_2$。若只估计绝对误差 $\|EU\|_2\le\|E\|_2\|U\|_2$，所得上界还取决于 $\|U\|_2$。

实际截断通常先控制每列的误差。记 $E=[e_1,\ldots,e_n]$，$\xi=\max_i\|e_i\|_2/\|b_i\|_2$。要从 $\xi$ 估计 $\varepsilon$，需要知道 $B$ 在不同方向上能把长度放大或缩小多少。当 $x$ 遍历单位球面时，$\|Bx\|_2$ 的最大值和最小值分别称为 $B$ 的最大奇异值和最小奇异值，即

$$\sigma_{\max}(B)=\max_{\|x\|_2=1}\|Bx\|_2,\qquad \sigma_{\min}(B)=\min_{\|x\|_2=1}\|Bx\|_2.$$

对任意 $x$ 都有 $\sigma_{\min}(B)\|x\|_2\le\|Bx\|_2\le\sigma_{\max}(B)\|x\|_2$。由于 $B$ 列满秩，$\sigma_{\min}(B)>0$，左侧给出了相对误差分母的下界。每列 $b_i$ 都是一个单位坐标向量的像，因此 $\|B\|_F\le\sqrt n\,\sigma_{\max}(B)$。再用 $\|E\|_2\le\|E\|_F\le\xi\|B\|_F$ 估计误差，得到

$$\varepsilon\le\sqrt n\,\xi\,\kappa_2(B),\qquad \kappa_2(B)=\frac{\sigma_{\max}(B)}{\sigma_{\min}(B)}.$$

$\kappa_2(B)$ 是 $B$ 的二范数条件数。对矩阵，$\|\cdot\|_2$ 表示谱范数，$\|\cdot\|_F$ 表示各条目平方和的平方根。若截断能保证 $\xi\le 2^{-p}$，要达到目标 $\varepsilon\le\varepsilon_0$（$0<\varepsilon_0<1$），取 $p\ge\lceil\log_2(\sqrt n\,\kappa_2(B)/\varepsilon_0)\rceil$ 就足够。在保留位数相同时，近乎平行的列比接近正交且尺度相当的列更容易丢失短方向。

#截断误差影响约化条件的传递

#长度失真给出 Lovász 参数的下界

LLL 比较两列去掉共同前缀后的高度。记 $c_j$ 为 $C=BU$ 的第 $j$ 列。第 $i$ 列去掉前 $r$ 列后的高度，等于 $c_i$ 到前 $r$ 列所张成空间的距离，即

$$h_{i\mid r}(C)=\min_{a\in\mathbb R^r} \left\|c_i-\sum_{j=1}^{r}a_jc_j\right\|_2,\qquad 0\le r<i.$$

$r=0$ 时，$h_{i\mid r}$ 是列长。$r=i-1$ 时，它就是 Gram–Schmidt 正交化后的高度（GSO 高度）$g_i$。对每组固定的系数 $a$，上式中的向量都等于 $C$ 乘以一个实系数向量。在 $C$ 和 $\widetilde C$ 上取相同的 $a$，应用上一节的长度界，再分别取最小值，得到

$$(1-\varepsilon)h_{i\mid r}(C) \le h_{i\mid r}(\widetilde C) \le(1+\varepsilon)h_{i\mid r}(C).$$

设 $\widetilde C$ 在第 $k$ 处通过参数为 $\widetilde\delta$ 的 Lovász 检查。取共同前缀 $r=k-2$。用上式给 $C$ 的第 $k$ 列高度取下界，给第 $k-1$ 列高度取上界，得到平方高度比的下界

$$\frac{h_{k\mid r}(C)^2}{h_{k-1\mid r}(C)^2} \ge \left(\frac{1-\varepsilon}{1+\varepsilon}\right)^2 \frac{h_{k\mid r}(\widetilde C)^2}{h_{k-1\mid r}(\widetilde C)^2} \ge \widetilde\delta\left(\frac{1-\varepsilon}{1+\varepsilon}\right)^2 .$$

在前面的二维例子中，$B$ 可逆，令 $y=Bx$ 可得 $\varepsilon=\|EB^{-1}\|_2=\sqrt{2}/33$。$\widetilde C$ 的平方高度比恰为 $1$。由上式，$C$ 的平方高度比至少为 $((33-\sqrt2)/(33+\sqrt2))^2\approx0.84238>3/4$，足以通过 $\delta=3/4$ 的 Lovász 检查。用 $C$ 的两列直接计算，实际比值为 $1090/1024$。

#尺寸条件的传递需要预留余量

尺寸约化还要检查投影系数 $\mu_{i,j}$。取正整数 $M$，令原基和近似基的第一列都等于 $(2M,0)^T$，第二列分别为 $b_2=(M+1,2M)^T$ 和 $\tilde b_2=(M,2M)^T$。取 $U=I$ 时，近似基的投影系数恰为 $1/2$，满足 $|\mu_{2,1}|\le 1/2$。原基的系数为 $1/2+1/(2M)$，超过同一阈值。两组基都满秩，而且相对扰动可随 $M$ 增大而任意小。

Saruchi 等人给尺寸条件和 Lovász 条件都预留了余量。对待检基 $X$ 作正对角 QR 分解 $X=Q_XR_X$。参数组 $\Xi=(\delta,\eta,\theta)$ 使用尺寸界 $|(R_X)_{ij}|\le\eta(R_X)_{ii}+\theta(R_X)_{jj}$（$i<j$）和通常的 Lovász 条件。定理 1 对 $\widetilde C$ 使用较强的参数 $(\delta,\eta,\theta)$，对 $C$ 使用较弱的参数 $(\delta_{\rm w},\eta_{\rm w},\theta_{\rm w})$，其中 $\delta_{\rm w}<\delta$、$\eta_{\rm w}>\eta$、$\theta_{\rm w}>\theta$。输入需要保留的位数取决于原基 $B$ 的正对角 QR 因子 $R$。令

$$\operatorname{cond}(R)=\bigl\|\,|R|\,|R^{-1}|\,\bigr\|_2,$$

其中绝对值逐项取，两矩阵之间是矩阵乘法。对固定的两组合法参数，论文给出的逐列误差充分条件形如 $\xi\le 1/(c_0 m^8\beta^n\operatorname{cond}(R)^2)$，$c_0,\beta$ 由参数决定，$m$ 是环境维数，$n$ 是格的秩。满足此界时，只要 $\widetilde C$ 满足较强的约化条件，$C$ 就满足较弱的约化条件。固定维数和参数，若 $\xi\le 2^{-p}$，$\operatorname{cond}(R)$ 每增大一倍，这个充分条件要求多保留 2 位。

论文的合法参数要求 $1/2<\eta<1$、$0<\theta\le1$、$\eta^2<\delta<1$。若目标是经典的 $|\mu_{i,j}|\le1/2$，仍须在 $C$ 上按此阈值检查。前面的 $\kappa_2(B)$ 用于估计长度失真，论文的 $\operatorname{cond}(R)$ 用于传递完整的约化条件 [1, secs. 2.2, 4]。

#分块缩放可以减小参与约化的整数

高位截断控制每列保留多少有效位。即使两列的有效位都很少，二进制指数也可能相差很远，把它们相加减时仍会出现长整数。例如，$1$ 和 $2^{100}$ 都只有一位有效数字，$2^{100}-1$ 却需要 $100$ 位。如果后一块的最小 GSO 高度远大于前一块的最大 GSO 高度，就可以适当缩小后块，在较小的整数上寻找换基操作 [1, sec. 5]。

先只考虑缩放。取正对角矩阵 $S=\operatorname{diag}(s_1,\ldots,s_n)$，将原基的第 $i$ 列乘以 $s_i$，所得的 $BS$ 称为缩放基。取 $M=2^{100}$，在下例中把第二列乘以 $2/M$，得到

$$B=\begin{pmatrix}1&M\\0&M\end{pmatrix},\qquad S=\operatorname{diag}(1,2/M),\qquad BS=\begin{pmatrix}1&2\\0&2\end{pmatrix}.$$

在 $BS$ 上，第二列减去第一列的 2 倍，得到 $(0,2)^T$。恢复第二列的原尺度后得到 $(0,M)^T$，这正是原基上第二列减去第一列的 $M$ 倍。LLL 在缩放后的当前基上判断是否交换，本例比较的是 $\delta\cdot 1^2\le 2^2$。原尺度下对应的 Lovász 条件是 $\delta\cdot 1^2\le M^2$。

#撤销缩放后需要检验整数性

缩放基下的系数 $x$ 对应原基下的系数 $Sx$，因为 $(BS)x=B(Sx)$。设 $W\in\mathrm{GL}_n(\mathbb Z)$ 是在缩放基上选出的换基矩阵。撤销缩放后，原坐标下的变换矩阵 $V$ 满足

$$(BS)WS^{-1}=BV,\qquad V=SWS^{-1},\qquad V_{ij}=(s_i/s_j)W_{ij}.$$

上例中 $W_{12}=-2$，换回原坐标后 $V_{12}=(M/2)(-2)=-M$。由于 $\det V=\det W=\pm1$，$V$ 能否用作原格的换基矩阵，取决于它的条目是否都是整数。

考虑另一组 $B=\begin{pmatrix}2&1\\0&2\end{pmatrix}$ 和 $S=\operatorname{diag}(1,2)$。缩放基 $BS$ 的第二列是 $(2,4)^T$，它在第一列 $(2,0)^T$ 上的投影系数为 $1$。将第二列减去第一列，得到

$$W=\begin{pmatrix}1&-1\\0&1\end{pmatrix},\qquad V=SWS^{-1}=\begin{pmatrix}1&-1/2\\0&1\end{pmatrix}.$$

这里 $\det V=1$，但 $BV=\operatorname{diag}(2,2)$ 的第二列 $(0,2)^T$ 在原基下的坐标是 $(-1/2,1)^T$，已经离开原格。

#投影高度的间隔决定分块边界

设 $g_i$ 是第 $i$ 列的 GSO 高度。只在后段最低高度 $\min_{j>k}g_j$ 远大于前段最高高度 $\max_{i\le k}g_i$ 时，才在第 $k$ 列后分块。缩小后块时仍要留出足够的间隔。标准 LLL 的尺寸约化保持 GSO 高度。块内的相邻两列若因 Lovász 条件失败而交换，它们的新高度都在原来的两个高度之间。因此两侧的高度仍然分开，边界处不会触发交换。后块的列仍可以减去前块列的整数倍，所以累计换基矩阵 $W$ 按这些块是上三角的 [1, sec. 5.1]。

每块使用同一个缩放系数。取 $S=\operatorname{diag}(2^{e_1}I,\ldots,2^{e_\ell}I)$，其中 $e_1\ge\cdots\ge e_\ell$ 均为整数。记 $W_{ab}$ 和 $V_{ab}$ 为第 $(a,b)$ 块。当 $a\le b$ 时，$V_{ab}=2^{e_a-e_b}W_{ab}$，指数差非负。当 $a>b$ 时，$W_{ab}=V_{ab}=0$。因此 $V$ 的每个块都是整数矩阵，又有 $\det V=\pm1$，它就是原格的换基矩阵。

若后段反而出现更短的投影高度，这个位置就要保留交换的可能。正数缩放也保留列间的夹角。上文近乎平行的两列一旦被截成同一列，再缩放仍然共线。要保住短向量 $(1,0)^T$，需要从原基保留足够的高位。

#缩放基上的 Lovász 条件可以传回原尺度

整数性保证 $BV$ 生成原格。要判断约化质量，还要看撤销缩放后的投影高度。由 $BV=((BS)W)S^{-1}$，第 $i$ 列恢复原尺度时，它相对于给定前缀的高度乘以 $1/s_i$，因为前缀张成的空间保持不变。第 $k$ 处 Lovász 检查的平方高度比因此乘以 $(s_{k-1}/s_k)^2$。这个因子在同一块内为 $1$，跨块时至少为 $1$，所以已经通过的 Lovász 条件仍成立。对尺寸条件，论文在缩放基上把参数 $\theta$ 收紧为 $\theta/2$，用这部分余量保证原尺度下能达到目标参数。论文将缩放基写作 $BD^{-1}$，对应本文的 $S=D^{-1}$ [1, sec. 5.1]。

若先截断再缩放，LLL 的输入是 $\widetilde B S$。记 $W_t$ 为前 $t$ 步列操作的乘积，尺寸约化和 Lovász 检查都在当前基 $(\widetilde B S)W_t$ 上进行。设最终的换基矩阵为 $W$，令 $V=SWS^{-1}$。撤销缩放得到 $\widetilde B V=(\widetilde B S)W S^{-1}$，再把 $V$ 用于完整的原基，得到 $BV$。前文的截断误差界和预留的参数余量给出 $BV$ 可保证的约化条件 [1, secs. 4–5]。

若连续近似两次，先将两轮的变换写回同一套系数坐标，再合并误差。设两轮的相对长度误差上界分别为 $\varepsilon_1$ 和 $\varepsilon_2$，且都小于 $1$，总长度倍率就介于 $(1-\varepsilon_1)(1-\varepsilon_2)$ 和 $(1+\varepsilon_1)(1+\varepsilon_2)$ 之间。

本节按投影高度选择缩放边界。下一单元为了控制计算规模，将选取一段连续的列，投影掉前面各列张成的空间，在所得的投影块内做约化。若切口恰好隔开两列需要交换的向量，重叠分块可以让它们在下一轮进入同一块。随后要把块内的换基用于整组基，并比较局部和全局势函数的下降量。

#参考文献