用于LUD增量计算的优势输入流

### 用于LUD增量计算的优势输入流 #### 1. 优势输入流的定义 在矩阵计算场景中，合作数据服务器存储的矩阵 $A$ 的元素会以矩阵元素序列的形式发送到计算服务器，在计算服务器上增量计算矩阵 $A_d$。设 $A_m$ 为计算服务器已接收的 $m$ 个数据项的集合，$P_{A_m}$ 为这 $m$ 个数据元素的布局，它由一系列二元组 $((R_0, C_0), (R_1, C_1) \cdots (R_{n - 1}, C_{n - 1}))$ 表示。其中，$R_i$ 是 $S_{R_i} = \{a_{ii}, a_{i i + 1} \cdots a_{i n - 1}\}$ 的子集（$0 \leq i \leq n - 1$），$C_i$ 是 $S_{C_i} = \{a_{i + 1 i}, a_{i + 2 i} \cdots a_{n - 1 i}\}$ 的子集（$0 \leq i \leq n - 2$），$C_{n - 1}$ 为空集。 例如，对于一个 $5 \times 5$ 的矩阵 $A$ 的 $P_{A_{10}}$，$R_0 = \{a_{00}, a_{02}, a_{04}\}$，$R_2 = \{a_{23}, a_{24}\}$，$C_0 = \{a_{10}, a_{20}, a_{40}\}$，$C_1 = \{a_{41}\}$，$C_3 = \{a_{43}\}$，其他集合 $R_1$、$R_3$、$R_4$ 和 $C_2$ 为空集。若 $a_{ij} \in R_i$ 或 $a_{ij} \in C_j$，则表示 $a_{ij}$ 已被计算服务器接收。 二元组 $(R_i, C_i)$ 的状态定义如下： - 当 $|R_i| = n - i$ 且 $|C_i| = n - i - 1$ 时，为满状态； - 当 $|R_i| = |C_i| = 0$ 时，为空状态； - 其他情况为增长状态。若 $0 \leq |R_i| - |C_i| \leq 1$ 且 $a_{ii} \in R_i$，则 $(R_i, C_i)$ 为对称增长状态。 若 $(R_0, C_0), (R_1, C_1) \cdots (R_{k - 1}, C_{k - 1})$ 为满状态，$(R_k, C_k)$ 为增长或空状态，且 $(R_{k + 1}, C_{k + 1}) \cdots (R_{n - 1}, C_{n - 1})$ 均为空状态，则 $P_{A_m}$ 为紧凑布局。若 $(R_k, C_k)$ 为对称增长或空状态，则 $P_{A_m}$ 为对称紧凑布局。 用 $\Im(P_{A_m}, op)$ 表示基于 $A_m$ 中数据元素可执行操作 $op$ 的数量。若 $\Im(P_{A_m}, op) \geq \Im(P_{A'_m}, op)$（$P_{A'_m}$ 为任意其他 $m$ 个数据项集合的布局），则 $P_{A_m}$ 对于操作 $op$ 是最优的。若 $A_m \subset A_{m + 1}$ 且 $\Im(P_{A_m}, op) \geq \Im(P_{A'_m}, op)$（$1 \leq m < n^2$），则 $P_{A_1}P_{A_2} \cdots P_{A_{n^2}}$ 是操作 $op$ 的优势布局序列。基于此，定义 $d_0d_1d_2 \cdots d_{n^2 - 1}$ 为优势输入流，其中 $d_0d_1d_2 \cdots d_i \in A_{i + 1}$（$0 \leq i < n^2$）。 #### 2. 相关引理和定理 - **引理 1**：设 $P_{A_m}$ 为对称紧凑布局，$P_{A'_m}$ 为紧凑布局，则 $\Im(P_{A_m}, mul/div) \geq \Im(P_{A'_m}, mul/div)$。 - **证明**：设 $(R'_k, C'_k)$ 是紧凑布局 $P_{A'_m}$ 中索引 $k$ 最小的增长或空二元组，假设 $|R'_k| + |C'_k| = b < 2(n - k) - 1$。使用 $R'_k$ 和 $C'_k$ 中元素可执行的乘除操作数量为 $|R'_k|(b - |R'_k|)$ 或 0（若 $a_{kk} \notin R'_k$ 则为 0）。当 $b$ 为偶数且 $a_{kk} \in R'_k$ 时，$|R'_k|(b - |R'_k|)$ 的最大值为 $\frac{b^2}{4}$（当 $|R'_k| = |C'_k| = \frac{b}{2}$ 时）；当 $b$ 为奇数且 $a_{kk} \in R_k$ 时，最大值为 $\frac{b^2 - 1}{4}$（当 $|R'_k| = \frac{b + 1}{2}$ 且 $|C'_k| = \frac{b - 1}{2}$ 时）。在这两种情况下，对称紧凑布局都满足使 $|R'_k|(b - |R'_k|)$ 最大化的要求。 - **引理 2**：设 $P_{A_m}$ 和 $P_{A'_m}$ 为对称紧凑布局，则 $\Im(P_{A_m}, mul/div) = \Im(P_{A'_m}, mul/div)$。 - **证明**：$P_{A_m}$ 和 $P_{A'_m}$ 为对称紧凑布局，假设 $(R_i, C_i)$ 和 $(R'_i, C'_i)$ 在 $0 \leq i < k$ 时为满状态，$(R'_k, C'_k)$ 和 $(R_k, C_k)$ 对称增长。则有 $|R_i| = |R'_i|$ 且 $|C_i| = |C'_i|$（$0 \leq i \leq k$），这意味着 $\sum_{i = 0}^{k} |R_i| \cdot |C_i| = \sum_{i = 0}^{k} |R'_i| \cdot |C'_i|$，即 $\Im(P_{A_m}, mul/div) = \Im(P_{A'_m}, mul/div)$。 - **定理 1**：设 $P_{A_m}$ 为对称紧凑布局，则 $\Im(P_{A_m}, mul/div) \geq \Im(P_{A^*_m}, mul/div)$，其中 $P_{A^*_m}$ 为任意非对称紧凑布局。 - **证明**：设 $(R^*_k, C^*_k)$ 是 $P_{A^*_m}$ 中索引 $k$ 最小的增长或空二元组，假设 $|R^*_k| + |C^*_k| = b$ 且 $\sum_{i = k + 1}^{n - 1}(|R^*_i| + |C^*_i|) = b'$。 - 若 $b + b' \leq 2(n - k) - 1$，则移除 $k < i < n$ 时 $(R^*_i, C^*_i)$ 中的元素，并将 $b'$ 个元素对称添加到 $(R^*_k, C^*_k)$ 中，得到的新布局 $P_{A'_m}$ 为对称紧凑布局。根据相关公式和引理 2，显然有 $\Im(P_{A_m}, mul/div) = \Im(P_{A'_m}, mul/div) \geq \Im(P_{A^*_m}, mul/div)$。 - 若 $b + b' > 2(n - k) - 1$，则从索引最大的二元组开始，删除 $(R^*_i, C^*_i)$ 中 $2(n - k) - 1 - b$ 个元素，并将这些元素