小学生都能看懂的《转置原理及其应用》！

· · 算法·理论

0. 前言

由于作者水平不高，所以可能会出现很多错误，求轻喷qwq。

1. 转置原理的概念

首先先明确我们所研究的对象，也即线性算法。

它支持输入一个长度为 n 的输入向量 x，然后输出一个长度为 m 的输出向量 y，且有常数矩阵 A 满足对任意合法的 x,y 都满足 y=Ax。

我们定义一个线性算法 y=Ax 的转置即为 y'=A^Tx'。

而转置原理断言可以在时空复杂度不变的情况下将一个线性算法改为其转置算法。

那么如果我们可以对一个算法的转置进行优化，那么我们只需将执行过程转置过来就可以得到原算法的优化方法。

但值得注意的的是，转置原理并不是提出了解决问题的算法，而是建立了问题相互转化的桥梁。一个问题转置之后不一定会变成更简单的问题，但可以改变我们认知问题的角度和方式。

2. 应用

0. 初等矩阵的转置

初等矩阵根据作用可分为三类

  1. 交换两行
  2. 给一行乘常数
  3. 将一行乘常数加到另一行

写成算法就是：

  1. a_i \leftrightarrow a_j
  2. a_i \leftarrow a_i \times k
  3. a_i \leftarrow a_i+a_j \times k

再写出他们的转置

  1. 第一类初等矩阵显然为对称阵，所以仍是 a_i \leftrightarrow a_j
  2. 第二类由于只在主对角线上有值，显然转置之后不变，a_i \leftarrow a_i \times k
  3. 转置之后原来在 (i,j) 上的 k 会转置到 (j,i)，因此变为 a_j \leftarrow a_j+a_i \times k

1. 多项式乘法的转置

考察多项式乘法 a \leftarrow a \times b。

考虑一个矩阵 C_{i,j}=b_{i-j}，那么相当于 a \leftarrow Ca。

那么其转置 a \leftarrow C^T a 的第 i 位就是 \sum_{i \le j} a_jb_{j-i}，也即 a 和 b 的差卷积，下文会以 \times^T 表示多项式乘法的转置。

2. 转置原理优化 FFT

正常使用的 FFT 一般是 DIF-FFT，通过奇偶分类拆解为子问题，非递归版本可简单分为两个部分：蝴蝶变换与迭代，我们分别称其为线性算法 B 和 P。

而我们知道 P \times B=F=(\omega_n^{ij})_{i,j}，那么 F=F^T，而显然 B=B^T 则 P \times B=B \times P^T

那么常规的多项式乘法的流程即为：

a \leftarrow B \times a,a \leftarrow P \times a b \leftarrow B \times b,b \leftarrow P \times b a \leftarrow a \cdot b a \leftarrow B \times a,a \leftarrow P \times a,a \leftarrow a \cdot \frac{1}{n}

考虑将 FFT 转置：

a \leftarrow P^T \times a,a \leftarrow B \times a b \leftarrow P^T \times b,b \leftarrow B \times b a \leftarrow a \cdot b a \leftarrow B \times a,a \leftarrow P \times a,a \leftarrow a \cdot \frac{1}{n}

而 B^2=I，那么我们可以在 DFT 时做 P^T 然后在 IDFT 时做 P，这样就省去了三遍蝴蝶变换，我们一般称这种技巧为 DIT-DIF。

3. 转置原理优化多项式除法

规定两个求两个长度为 n 的多项式的乘法的时间为 M(n)，而求一个多项式的逆的时间为 D(n)。

现在有多项式除法 F(x)=Q(x)G(x)+R(x)，令 n=\deg F,m=\deg G，假设 2m=n。

根据普通的多项式除法，我们计算 Q(x) 需要 M(m)+D(m) 的时间，而计算 R(x) 又需要额外的 M(m) 的时间，那么算出 R(x) 就需要花费整整 2M(m)+D(m)。

考虑直接写出 R(x)，那么 r_k=\sum_{i} f_i [x^k](x^i \bmod G(x))。将其转置，可得 r^T_k=\sum_i f_i [x^i](x^k \bmod G(x))=\sum_i [x^{n-i}] F_R(x) [x^i] (x^k \bmod G(x))=[x^n] F_R(x)(x^k \bmod G(x))。

而我们有恒等式：

[x^n]F_R(x)(x^k \bmod G(x))=[x^k] \frac{(F(x)G_R(x))\bmod x^m}{G_R(x)}

::::info[这里是证明，不想看可以直接跳] 我们发现如果 G_R(x) 是一个递推数列的特征多项式而且 F(x) 是这个数列的第 0 \sim n 项，那么这个式子描述的就是常系数齐次线性递推中的 Fiduccia 算法与 LSB-First 算法，于是考虑从线性递推角度入手。

首先考虑 k<m 时的情况，此时左式为 [x^k]F(x)。考虑右式，由于 m>k 故右式分子的前 k+1 项与 F(x)G_R(x) 相同，故左式等于右式。

我们记 A(k)=[x^n]F_R(x)(x^k \bmod G(x)),B(k)=[x^k]\frac{(F(x)G_R(x))\bmod x^m}{G_R(x)},R(k)=x^k \bmod G(x),P(x)=\frac{(F(x)G_R(x))\bmod x^m}{G_R(x)}。

考虑 x^kG(x) \bmod G(x)，显然这个东西为 0，将其展开：

x^kG(x)=\sum_{i=0}^m g_ix^{k+i} \equiv \sum_{i=0}^m g_i R(k+i) \equiv 0 \pmod{G(x)}

而我们又注意到 \deg R(k)<m，因此 \sum\limits_{i=0}^m g_i R(k+i)=0，那么乘 F_R(x) 后取 [x^n] 即得 \sum\limits_{i=0}^m g_i A(k+i)=0

下证 \sum\limits_{i=0}^m g_i B(k+i)=0。

那么 G_R(x)P(x)=(F(x)G_R(x))\bmod x^m，所以 0=[x^k]G_R(x)P(x)，写出卷积形式：

[x^k]G_R(x)P(x)=\sum_{i=0}^m g_{m-i} [x^{k-i}]S(x)=\sum_{i=0}^m g_{m-i}B(k-i)

让 k \rightarrow k+m，则 \sum_{i=0}^m g_{m-i}B(k-i)=\sum_{i=0}^m g_i B(m+i)

因此数列 A,B 的前 m 项相同，且都服从同一个递推关系，故由线性递推数列的唯一性可知对任意 k 有 A(k)=B(k)。 ::::

那么我们现在要计算 r_k^T 只需要以下步骤：

我们转置这个步骤便可得到计算 R(x) 的算法：

而差卷积可以利用自然溢出做到 \frac{1}{2} M(m)，那么我们计算 R(x) 只需要 M(m)+D(m) \sim \frac{7}{6} M(n) 的计算量，和原来 2M(m)+D(m) \sim \frac{5}{3} M(n) 的做法可谓有着天壤之别！

4. 转置原理优化多点求值

多点求值是一个典型的线性算法，设待求的点为 \{x_0,x_1 \dots x_m\}，多项式为 F(x)=\sum\limits_{i=0}^n f_ix^i，那么容易写出它的标准形式：

\left[ \begin{matrix} 1 & x_0 & \cdots & x_0^n \\ 1 & x_1 & \cdots & x_1^n \\ \vdots & \vdots & \ddots & \vdots \\ 1 & x_m & \cdots & x_m^n \\ \end{matrix} \right] \left[ \begin{matrix} f_0 \\ f_1 \\ \vdots \\ f_n \\ \end{matrix} \right]

考虑转置

\left[ \begin{matrix} 1 & 1 & \cdots & 1 \\ x_0 & x_1 & \cdots & x_m \\ \vdots & \vdots & \ddots & \vdots \\ x_0^n & x_1^n & \cdots & x_m^n \\ \end{matrix} \right] \left[ \begin{matrix} v_0 \\ v_1 \\ \vdots \\ v_n \\ \end{matrix} \right]

这个东西是简单的，就是 \sum\limits_{i=0}^n \frac{v_i}{1-xx_i}。

我们用分治去计算这个东西，令 T_{l,r}=\prod\limits_{i=l}^r (1-xx_i)，那么令 P_{l,r} 表示分子部分，设分治点为 k，那么有 P_{l,r}=P_{l,k} \times T_{k+1,r}+P_{k+1,r}\times T_{l,k}。

最后计算 P_{1,n} \times T_{1,n}^{-1} 即可。

将此过程转置即可，注意原来分治的自下而上要改为自上而下。

3. 一类特殊矩阵的快速乘向量计算方法

1. 引入

考虑一个线性算法 y=Ax，现在设矩阵系数 A_{i,j} 的二元函数为 A(x,y)=\sum_{i,j} A_{i,j} x^iy^j。

若我们可以将 A(x,y) 写作 A(x,y)=u(x)v(y)f(g(x)h(y))，且 g,h 由常数个下方提到的简单函数复合而成。那么如果 g,h 不含 \exp 和 \ln，则我们可以用 O(M(n)) 的复杂度该矩阵和逆矩阵左乘向量，否则需要 O(M(n)\log n) 的复杂度。

为保证下文提到的所有运算有意义，我们还要求 gh 的常数项为 0，u,v 常数项非 0，f 每一项非 0。

2. 右复合

对于一个 \deg F = n-1 的多项式 F 来说，F(G(x)) \bmod x^n 称为一次右复合，写作 F \circ G。

下面介绍一些简单函数的右复合。

加

F(x+k)=\sum_{i=0}^{n-1} f_i (x+k)^i \\ =\sum_{i=0}^{n-1} f_i \sum_{j=0}^i \binom{i}{j}x^jk^{i-j} \\ =\sum_{j=0}^{n-1} \frac{x^j}{j!} \sum_{i=j}^{n-1} f_ii! \cdot \frac{k^{i-j}}{(i-j)!}

差卷积即可。

乘

#### 幂 $F(x^k)$，下标变换即可，$O(n)$。 #### 逆 $F(x^{-1})=F_R(x)x^{1-n}$，设下一个右复合的为 $g$，那么下一个右复合只需计算 $F_R \circ g$ 和 $g^{1-n}$，而计算 $g^{1-n}$ 只需 $O(M(n))$。 #### 根 $F(x^{\frac{1}{k}})$。还是设下一个右复合的为 $g$，设其有唯一的一个 $h$ 使得 $g=h^k$，我们定义 $F_i(x)=\sum_{j} f_{jk+i}x^j$，那么 $F(h)=\sum\limits_{i=0}^{k-1} F_i(g) h^i$，复杂度 $O(kM(n))$，因此要求 $k$ 为常数。 #### 指 $F(e^x-1)$，这个形式是为了方便和对数互逆。 注意到减一可以扔掉，只考虑 $F(e^x)$。 $$ F(e^x)=\sum_{i=0}^{n-1} f_ie^{ix}=\sum_{i=0}^{n-1} f_i \sum_{j=0}^{n-1}\frac{i^j}{j!}x^j \\ =\sum_{j=0}^{n-1} \frac{x^j}{j!}\sum_{i=0}^{n-1} f_i i^j $$ 那么我们相当于要对每个 $i$ 算 $\sum_{j=0}^{n-1} f_j j^i$，显然可以直接分治 FFT，可以做到 $O(M(n)\log n)$。我们还发现这个东西转置以后就是经典的多点求值形式，下面会用。 #### 对 $F(\ln(1+x))$，注意到直接做是困难的。 由于对指互逆，我们只要考虑复合指数做法的逆就行了。 虽然复合指数的逆也不简单，但是我们可以将两边都转置一下，多点求值的逆就是快速插值，那么也可以做到 $O(M(n)\log n)$。 #### 计算 先考虑 $u=v=1$，那么有： $$ A_{i,j}=\sum_{k} g_i^k f_k h_j^k $$ 那么做变换 $A$ 就相当于：右复合 $g$，点乘 $f$，右复合 $h$。 那么 $u,v \neq 1$ 的情况也类似，在开头和结尾处乘 $u$ 和乘 $v$ 的转置即可。