投影分块与局部换基#

在从高位近似基向原基传递换基矩阵中，缩放边界选在前后两组 GSO 高度充分分离的位置。例如在 $M=2^{100}$ 的例子中，缩放基上第二列减去第一列的 $2$ 倍，换回原尺度时对应减去 $M$ 倍。本篇先在原尺度上计算，为了减少一次约化所处理的列数，直接选取一段连续列。若切口恰好隔开需要交换的两列，就要在后续轮次让切口两侧的列进入同一个窗口。

#QR 的对角子块表示连续列的投影格

设当前整数列基 $B=[b_1,\ldots,b_n]\in\mathbb Z^{m\times n}$ 列满秩。选取闭区间 $I=[a,b]$，块长为 $d=b-a+1$。记 $B_{:,I}=[b_a,\ldots,b_b]$。沿用格基约化与 LLL 算法的 $\pi_a$，即到前 $a-1$ 列所张成空间的正交补上的投影。局部处理的投影基及其生成的格为

每列都扣除了同一个前缀的方向。由于原基列线性无关，$Y$ 仍有 $d$ 个线性无关的列。投影以后的向量一般不在原格中，它们保留了选取局部换基所需的长度和夹角 [1, p. 6]。

对当前基作正对角的薄 QR 分解 $B=QR$。$Q=[q_1,\ldots,q_n]$ 的列正交归一，$R$ 是 $n\times n$ 上三角矩阵。用 $q_a,\ldots,q_b$ 作局部正交坐标，有

这是因为 $b_j=\sum_{i=1}^{j}q_iR_{ij}$。对 $a\le j\le b$，投影去掉 $i<a$ 的项，留下的系数正好构成 $R$ 的第 $a$ 到 $b$ 行、同一范围的列。于是对任意 $z\in\mathbb R^d$，$\|Yz\|_2=\|Tz\|_2$。沿用上一篇的高度记号 $g_i=h_{i\mid i-1}(B)=R_{ii}$，投影块的 GSO 高度依次为 $g_a,\ldots,g_b$，局部格体积为它们的乘积。块内的 GSO 系数也能直接沿用全局记号。对 $a\le j<i\le b$，$b_j^*$ 已经垂直于前缀，所以 $\langle\pi_a(b_i),b_j^*\rangle=\langle b_i,b_j^*\rangle$。两边除以 $g_j^2$ 得到同一个 $\mu_{i,j}$。

下文用一个三维基 $B$ 的第 2、3 列做例子。

第一列沿 $y$ 轴，$\pi_2$ 因此扣除 $y$ 分量。以 $x,z$ 轴作局部坐标，第二、三列分别成为 $(4,0)^T$ 和 $(3,1)^T$。这个例子的 $Q$ 依次取 $y,x,z$ 轴的单位向量，故

若直接截取原矩阵 $B$ 的第 2、3 行和第 2、3 列，会得到 $\bigl(\begin{smallmatrix}1&9\\0&1\end{smallmatrix}\bigr)$。它仍包含 $y$ 坐标，却漏掉了两列的 $x$ 坐标，不能用来判断这个投影块的约化条件。

#块内的整数列操作可以一起作用于原基

先在 $T$ 上用 $\delta=3/4$ 做二维 LLL。记两列为 $y_1=(4,0)^T$、$y_2=(3,1)^T$。

1. 投影系数为 $3/4$。尺寸约化把第二列改成 $y_2-y_1=(-1,1)^T$。
2. 新第二列的平方长度为 $2$，小于 $(3/4)\cdot16=12$，交换两列。在原基中，对应的列是 $b_2=(4,1,0)^T$ 和 $b_3-b_2=(-1,8,1)^T$，平方长度分别为 $17$ 和 $66$。直接比较全长会错过这次交换，投影比较才使用相对于同一前缀的高度。
3. 交换后，$(4,0)^T$ 沿 $(-1,1)^T$ 的投影系数为 $-2$。将它加上后者的两倍，得到 $(2,2)^T$。现在两列正交，且按长度从短到长排列。

最终局部第一列是 $-y_1+y_2$，第二列是 $-y_1+2y_2$。把它们在旧基下的系数按列排列，就得到如下累计换基矩阵 $V$。

对任意块 $I$，只要局部子程序返回 $V\in\mathrm{GL}_d(\mathbb Z)$，就可以把它嵌入全维矩阵，并在完整的整数列上一次执行换基。

这里 $I_j$ 是 $j$ 阶单位矩阵，阶数为零的块省略。$\widehat V$ 仍是整数幺模矩阵，故 $B'$ 生成原格。前 $a-1$ 列保持原样，投影 $\pi_a$ 也保持原样。由投影的线性性，$\pi_a(B'_{:,I})=\pi_a(B_{:,I}V)=YV$。若已记录 $B=B_{\rm in}U$，则同步更新 $U\leftarrow U\widehat V$。

三维例子中，把上述 $V$ 施于含有完整坐标的第二列和第三列，得到

原基第 2、3 列的 $y$ 坐标 $(1,9)$ 也被更新为 $(1,9)V=(8,17)$。仅替换投影块会漏掉这一行。局部两列在 $x,z$ 平面内已正交，但新第二列沿第一列的 GSO 系数为 $8/2=4$。若目标是全局标准 LLL，仍需相对于前缀做尺寸约化。

#局部换基会改变 QR 的交叉块

$TV$ 已经完成局部换基，对角线下方可能出现非零项。将 $TV$ 重新分解为 $O T'$，其中 $O$ 正交、$T'$ 上三角且对角为正。令 $\widehat O=\operatorname{diag}(I_{a-1},O,I_{n-b})$。更新后全局基的 QR 分解为

此时 $R'_{I,I}=T'$。块上方的系数变为 $R_{1:a-1,I}V$，块右方的系数变为 $O^T R_{I,b+1:n}$，相应范围为空时省略。块外的对角元 $R_{ii}=g_i$ 都保持原值，交叉块里的系数则要按新基更新。

如果还在局部投影块内部使用上一篇的高位截断和列缩放，先在块内按原尺度恢复 $V=SWS^{-1}$，验证它的整数性和局部约化质量，再嵌入 $\widehat V$。下面的势函数比较都在原始尺度进行。

#局部势函数与全局势函数按相同比例变化

沿用前面的 LLL 势函数。记 $D_0(B)=1$，$D_j(B)$ 为前 $j$ 列组成的 Gram 矩阵的行列式，$\Phi(B)=\prod_{j=1}^{n}D_j(B)$。对投影基 $Y$ 独立使用这个定义，记它的前 $t$ 列的 Gram 行列式为 $D_t^I(Y)$，局部势函数为 $\Phi_I(Y)=\prod_{t=1}^d D_t^I(Y)$ [2, sec. 3.1]。

先看当前基中以第 $a-1+t$ 列结束的前缀。它的体积平方等于从开头到该列的全部 GSO 高度平方之积。将乘积在第 $a-1$ 列处分开，就有

换基后对 $B'$ 和 $YV$ 也有同一等式。对 $j<a$，前缀完全没有改动。对 $j\ge b$，前缀包含整个 $V$，经历的是幺模换基，体积也保持原值。局部的末项 $D_d^I$ 同理保持不变。把前后势函数相除，变化的因子恰好来自块内的前缀。

因此同一次块内换基造成的对数势变化，在局部和全局完全相等。若后续用 $\ell_i=\log_2 g_i$ 表示 GSO 高度轮廓，则 $\tfrac12\log_2\Phi(B)=\sum_{i=1}^n(n-i+1)\ell_i$，局部与全局的这一对数势也等量变化。

在三维例子中，局部两列的平方 GSO 高度从 $(16,1)$ 变为 $(2,8)$，体积平方都是 $16$。全局多出的第一列高度平方为 $4$。用这几项即可复算两个势函数的值。

from fractions import Fraction
from math import prod

def potential(squared_heights):
    rank = len(squared_heights)
    return prod(s ** (rank - i) for i, s in enumerate(squared_heights))

local = potential([16, 1]), potential([2, 8])
whole = potential([4, 16, 1]), potential([4, 2, 8])
print(local, whole)  # (256, 32) (16384, 2048)
assert Fraction(local[1], local[0]) == Fraction(whole[1], whole[0]) == Fraction(1, 8)

局部势从 $256$ 降到 $32$，全局势从 $16384$ 降到 $2048$，两者都降至原值的 $1/8$，因而两边的 $\tfrac12\log_2\Phi$ 都减少 $3/2$。这个比例也恰好等于交换时的平方高度比 $2/16$，另外两次尺寸约化都保持势函数。

#错位窗口把上一轮的边界纳入局部检查

取正交整数基 $B=\operatorname{diag}(1,4,1,4)$，固定 $\delta=3/4$。第一轮分成 $[1,2]$ 和 $[3,4]$ 两块。每块的两列都正交，高度均为 $(1,4)$，各自通过 LLL 检查。但全局第 2、3 列隔着切口，它们违反 Lovász 条件，因为 $(3/4)\cdot4^2=12>1^2$。这个例子的全部尺寸系数都为零，缺失的恰是一次跨界比较。

把第二轮的边界移动一列。仍用从 1 开始、两端都计入的区间，两轮窗口可写成

两端的单列无需局部约化。中间块 $[2,3]$ 将高度 $(4,1)$ 的两列交换，整个基的 GSO 高度顺序变成 $(1,1,4,4)$。本例四列始终正交，此时全局 LLL 条件成立。

一般输入中，修复一个边界也可能改变相邻窗口的高度或投影系数。覆盖过每个边界，只说明它曾被处理过。若目标是标准 LLL，停止时应对同一组最终基检查全部尺寸系数和所有相邻 Lovász 条件。局部势的恒等式能把已完成的进展记到全局，要估计总轮数，还需要证明每轮能取得多大进展。

#批量应用局部变换可以减少全维整数更新

块内多次尺寸约化与交换都可以先累计在 $d\times d$ 的 $V$ 中，然后用一次矩阵乘法更新 $m\times d$ 的原基列。用普通稠密矩阵乘法，这次更新约需 $O(md^2)$ 次标量运算。完整成本还包括提取和维护 QR、更新累计整数矩阵、操作数的位长，以及实际轮数。

同一轮内互不相交的块可以在同一份当前 $R$ 上分别求 $V$。它们的嵌入作用在不同列上，可以合并为块对角矩阵。相互重叠的两块则共享列。第一块更新后，第二块应读取新的投影几何。把先前算出的整数幺模矩阵作用于当前基，仍会保持原格，但它在旧块上达到的约化质量需要在新块上重新验证。

Neumaier 和 Stehlé 的递归算法使用重叠约一半的投影块，按从后向前的顺序逐轮处理，并另行分析整轮的收敛。BLASter 采用另一种调度，同一轮计算不相交的局部段，相邻轮改变起始偏移，使上一轮的切口进入下一轮的局部问题 [3, secs. 3, 4.1; 4, sec. 3.1]。

投影格、BKZ 与局部 SVP使用同样的投影几何，其中 BKZ 的理想局部调用返回投影格的最短非零向量及其整数系数，后续再将它提升、插入原基。本篇的局部任务是约化整个投影基并返回 $V$。三维例子还留下了块间系数 $4$。下一单元的递归 Seysen 约化将从这些上三角交叉系数入手，研究怎样在保持 GSO 高度的同时整理基及其逆所反映的偏斜。

#参考文献