【算法】浅谈转置原理 — wangrx

支持下 Qiuly ~ QWQ。

转置原理是一种基于矩阵转置的方法，
用以解决二元生成函数的相关问题。

初等矩阵

（有基础的同学可以跳过）
要学会转置原理，首先要知道初等矩阵。

通过高斯消元，我们已经知道了矩阵的初等变换：

• 把两行（列）互换。
• 把某行（列）乘一非零常数 $k$
  （其实是零也行，只是不叫初等变换）。
• 把某行（列）加上另一行（列）的 $k$ 倍。

而我们又知道一个特殊的方阵——单位矩阵 $I$，它长这个样子：
$$\begin{bmatrix}
1&0&\cdots&0\newline
0&1&\cdots&0\newline
\vdots&\vdots&\vdots&\vdots\newline
0&0&\cdots&1\end{bmatrix}$$

它的性质是：任意矩阵乘上单位矩阵等于它本身。

如果作用初等变换于单位矩阵 $I$，就可得初等矩阵 $E$：

• 若作初等行变换，$E\times A$ 相当于对 $A$ 作对应的初等行变换。
• 若作初等列变换，$A\times E$ 相当于对 $A$ 作对应的初等列变换。

乘以零的情况与此相同。

因此高斯消元的过程，就是将矩阵分解为初等矩阵的过程。

算法的转置

若一个算法可以看作方阵 $A$，
输入为向量 $\vec{v}$，输出为 $A\vec{v}$，则称该算法为线性算法。
许多算法都是线性算法，例如 FFT 转化为方阵就是
$$\begin{bmatrix}
1&1&1&\cdots&1\newline
1&w^1 _ n& w^2 _ n&\cdots&w^n _ n\newline
1&w^2 _ n& w^4 _ n&\cdots&w^{2n} _ n\newline
\vdots&\vdots&\vdots&\vdots&\vdots\newline
1&w^n _ n&w^{2n} _ n&\cdots&w^{n^2} _ n
\end{bmatrix}$$

此时，输入为 $\vec{v}$，输出为 $A^T\vec{v}$ 的算法为该算法的转置算法。
$A^T$ 表示转置，其实就是将矩阵的行和列交换（$A^T _ {i,j}=A _ {j,i}$）。

转置有几个非常重要的性质（有基础的同学可以跳过），那就是：

• $(AB)^T=B^TA^T$（转置调换矩乘的顺序）
• 对于初等矩阵的转置，
  • 前两种的转置就是它本身。
  • 最后一种如果是将第 $i$ 行（列）的 $k$ 倍加到第 $j$ 行（列），
    其转置就是将第 $j$ 行（列）的 $k$ 倍加到第 $i$ 行（列）。

可以手推慢慢消化一下，这个非常重要。

线性算法的判定

然而线性算法的定义并未给我们带来什么别的东西，
这是因为算法的实际流程并未与矩阵建立起对应的关系。

自己有一个比较好的办法，
就是将输入、输出变量与运行过程中的一切辅助变量
（也就是整个内存）拼成一个向量，
也就是已知 $\begin{pmatrix}\underline{\vec{v}}\newline\underline{\vec{0}}\newline\vec{0}\end{pmatrix}$，求 $\begin{pmatrix}\underline{\vec{0}}\newline\underline{\vec{0}}\newline A\vec{v}\end{pmatrix}=\begin{bmatrix}O&O&O\newline O&O&O\newline A&O&O\end{bmatrix}\begin{pmatrix}\underline{\vec{v}}\newline \underline{\vec{0}}\newline \vec{0}\end{pmatrix}$，
（若 $A$ 为非方阵，也可通过补 $0$ 补成方阵）
这样的话。程序的各种运算与初等变换一一对应起来了。

为保证行文统一，以下均称向量中的量为变量，矩阵中的量为常量。

于是具体的，线性算法只包含以下运算：

• 交换两个变量。
• $x\leftarrow m\times x,x$ 为变量，$m$ 为常量。
  • tips: $x\gets 0$ 属于该运算。
• $x\leftarrow x+m\times y,x,y$ 为变量，$m$ 为常量。
  • tips: $x\gets y$ 为该运算与上方运算的组合，
    即 $x\leftarrow 0\times x,x\leftarrow x+y$

有了这个定义，我们便可以很方便地判定和处理线性算法了。

原算法与转置算法的转换

将矩阵分解为初等矩阵，
设 $A=E _ 1E _ 2\cdots E _ {n-1}E _ n,E _ 1,E _ 2,\cdots E _ n$ 均为初等矩阵，
则显然有 $A^T=E^T _ nE^T _ {n-1}\cdots E^T _ 2E^T _ 1$，

再由 $E _ k^T$ 性质可知，将算法转置 相当于将运算次序反过来，然后
$x\leftarrow x+my$（$x,y$ 为变量，$m$ 为常量）改写为 $y\leftarrow y+mx$ 即可。

由此我们得到将算法转置的很傻逼的机械过程。

常见算法的转置

如果上面的 “将算法转置” 还没有理解，可以看看下面的例子。

FFT 的转置

上面我们已经知道了，FFT 可写作 $n$ 阶方阵 $F$，其中 $F _ {i,j}=w _ n^{ij}$ 。
因此 $F^T=F,F^{-1} _ {i,j}=2^{-n}w _ n^{-ij}$ 。

多项式乘法（卷积）的转置

考虑多项式乘法（卷积）：
已知 $n+1$ 维向量 $\vec{a}$，$m+1$ 维向量 $\vec{b}$，求 $n+m+1$ 维向量 $\vec{c}$，
使 $c _ k=(\vec{a}\times\vec{b}) _ k=\displaystyle\sum _ {\begin{matrix}\scriptsize 0\le i\le n\newline\scriptsize 0\le k-i\le m\end{matrix}}a _ {i}b _ {k-i}\ (0\le k\le n+m)$。

可以很快地写出这个算法：

for(int k=0;k<=n+m;++k){
    c[k]=0;
    for(int i=min(0,k-m);i<=max(k,n);++i)
        c[k]+=a[i]*b[k-i];
}
for(int i=0;i<=n;++i) a[i]=0;

把 $\vec{b}$ 看作矩阵中的常量，将算法化为线性算法的标准形式：
根据 $\vec{b}$ 构造矩阵 $B$ 使得 $B\begin{pmatrix}\underline{\vec{a}}\newline\vec{0}\end{pmatrix}=\begin{pmatrix}\underline{\vec{0}}\newline\vec{c}\end{pmatrix}$。
然后写出它的转置：

for(int i=n;i>=0;--i) a[i]=0;
for(int k=n+m;k>=0;--k){
    for(int i=max(k,n);i>=min(0,k-m);--i)
        a[i]+=c[k]*b[k-i];
    c[k]=0;
}

可以发现，这个算法就是求 $\begin{pmatrix}\underline{\vec{a}’}\newline\vec{0}\end{pmatrix}=B^T\begin{pmatrix}\underline{\vec{0}}\newline\vec{c}’\end{pmatrix},\vec{c}’$ 为输入向量。
$a’ _ {i}=\displaystyle\sum _ {\begin{matrix}\scriptsize 0\le k\le n+m\newline\scriptsize 0\le k-i\le m\end{matrix}}c’ _ {k}b _ {k-i}\ (0\le i\le n)$。

考虑将 $\vec{b}$ 系数翻转，即设 $b^R _ i=b _ {m-i}$，
则 $a’ _ i=\displaystyle\sum _ {\begin{matrix}\scriptsize 0\le k\le n+m\newline\scriptsize i\le k\le m+i\end{matrix}}c’ _ {k}b^R _ {m+i-k}=(c’\times b^R) _ {m+i}\ (0\le i\le n)$
因此卷积的转置就是已知 $n+m+1$ 维向量 $\vec{c}’,m$ 维向量 $\vec{b}$，
求 $\vec{c}’\times\vec{b}^R$ 的第 $m$ 个到第 $m+n$ 个元素。

可以使用长度为 $n+m+1$ 的循环卷积，因为溢出的部分刚好不要。

根据对多项式乘法（卷积）转置的研究，我们得到了以下性质：

• 将向量分段后，某几段分向量的赋值、加法与数乘也是线性的
  （其实就是循环赋值、对应位置相加与乘上一个常数），可以当做初等变换看待。
• 转置时输入与输出的位置互换（由改写本身可证明），
  因此转置算法时，通常会在最后将输出移动到输入处。

同时要注意以下几点：

• 转置算法的时候要把运算过程（包括内存的调用）一点一点写出来。
• 注意变量与常量的差别对待（变量写在向量里，常量写在矩阵里）

转置原理

由转置的过程本身可知，原算法与转置算法的复杂度相同。

若得到了计算 $A\vec{v}$ 的优化方法，
则必然可以通过如上机械的改写得到 $A^T\vec{v}$ 的优化方法。

反过来，如果要优化 $A\vec{v}$，则可优先考虑 $A^T\vec{v}$，
然后机械改写 $A^T\vec{v}$ 的算法得到 $A\vec{v}$ 的算法。

这便是转置原理，又称特勒根原理。
（也就是说，将算法转置后再优化就是转置原理）

多项式多点求值

多项式多点求值可化为范特蒙德矩阵
$$
y _ k=\sum _ {i=0}^nf _ ix _ k^i$$
$$
\begin{bmatrix}
1&x _ 0 &x _ 0^2 &\cdots&x _ 0^n\newline
1&x _ 1 &x _ 1^2 &\cdots&x _ 1^n\newline
1&x _ 2 &x _ 2^2 &\cdots&x _ 2^n\newline
\vdots&\vdots&\vdots&\vdots&\vdots\newline
1&x _ m &x _ m^2 &\cdots&x _ m^n
\end{bmatrix}
\begin{pmatrix}
f _ 0\newline f _ 1\newline f _ 2\newline\vdots\newline f _ n
\end{pmatrix}=
\begin{pmatrix}
y _ 0\newline y _ 1\newline y _ 2\newline\vdots\newline y _ m
\end{pmatrix}
$$
首先将该矩阵补全为方阵
（$m$ 不够矩阵添 $0$，$n$ 不够矩阵与向量一起添 $0$）

考虑转置该矩阵，

$$
\begin{bmatrix}
1&1&\cdots&1\newline
x _ 0&x _ 1&\cdots&x _ m\newline
x _ 0^2&x _ 1^2&\cdots&x _ m^2\newline
\vdots&\vdots&\vdots&\vdots\newline
x _ 0^n&x _ 1^n&\cdots&x _ m^n
\end{bmatrix}
$$

发现转置算法是求 $y _ k’=\displaystyle\sum _ {i=0}^n f _ i x _ i^k$

写成生成函数，得到 $y'(x)=\displaystyle\sum _ {i=0}^n\frac{f _ i}{1-x _ ix}$。
我们一般用分治 FFT 解决这个问题。
具体地，设 $\displaystyle\sum _ {i=l}^{r}\frac{f _ i}{1-x _ ix}=\frac{f _ {l,r}(x)}{g _ {l,r}(x)}$，$l,r$ 均为多项式函数，则答案为 $\dfrac{f _ {0,n}(x)}{g _ {0,n}(x)}$
设 $l\le mid<r$，则有
$$f _ {l,r}(x)=f _ {l,mid}(x)\times g _ {mid+1,r}(x)+f _ {mid+1,r}(x)\times g _ {l,mid}(x)\newline
g _ {l,r}(x)=g _ {l,mid}(x)g _ {mid+1,r}(x)$$

化为线性算法的标准形式：

• 自下而上初始化常量（$x _ i$ 在矩阵中，被视为常量）：
  • $\vec{g} _ {l,l}=\dbinom{1}{-x _ i}$
  • $\vec{g} _ {l,r}=\vec{g} _ {l,mid}\times\vec{g} _ {mid+1,r}$
• 初始向量为 $\begin{pmatrix}\underline{\vec{f}}\newline\vec{0}\end{pmatrix},\vec{0}$ 为初始化的内存。
  各个多项式不共用内存（即第一次调用时均为 $\vec{0}$）。
• 赋值 $\vec{f} _ {l,l}\leftrightarrow(f _ i)$
• 自下而上分治（$\times$ 为多项式乘法，由上已知它是线性的）：
  • $\vec{f} _ {l,mid}\gets\vec{f} _ {l,mid}\times\vec{g} _ {mid+1,r}$
  • $\vec{f} _ {mid+1,r}\gets\vec{f} _ {mid+1,r}\times\vec{g} _ {l,mid}$
  • $\vec{f} _ {l,r}\gets\vec{f} _ {l,r}+\vec{f} _ {l,mid}$
  • $\vec{f} _ {l,r}\gets\vec{f} _ {l,r}+\vec{f} _ {mid+1,r}$
• 最后计算 $\vec{f}\leftarrow\vec{f} _ {0,n}\times(\vec{g}^{-1} _ {0,n}\bmod x^{n+1})$
• 将辅助变量清 $0$

转置该算法：

• 自下而上初始化常量 $\vec{g} _ {l,r}$
• 初始向量为 $\begin{pmatrix}\underline{\vec{f}}\newline\vec{0}\end{pmatrix},\vec{0}$ 为初始化的内存。
• 将辅助变量清 $0$
• 计算 $\vec{f} _ {0,n}’\gets \vec{f}\times^T(\vec{g}^{-1} _ {0,n}\bmod x^{n+1}),\times^T$ 为多项式乘法的转置。
• 自上而下分治：
  • $\vec{f}’ _ {mid+1,r}\gets\vec{f}’ _ {mid+1,r}+\vec{f}’ _ {l,r}$
  • $\vec{f}’ _ {l,mid}\gets\vec{f}’ _ {l,mid}+\vec{f}’ _ {l,r}$
  • $\vec{f}’ _ {mid+1,r}\gets\vec{f}’ _ {mid+1,r}\times^T\vec{g} _ {l,mid}$
  • $\vec{f}’ _ {l,mid}\gets\vec{f}’ _ {l,mid}\times^T\vec{g} _ {mid+1,r}$
• 赋值 $(f _ i)\leftrightarrow\vec{f} _ {l,l}’$

由此得到了多项式多点求值的 $\Theta(n\log^2 n)$ 快速算法。

转置原理的适用范围

具体的应用题见 「KrOI2021」Feux Follets —— Alpha1022

通常转置原理要结合分治 FFT 和矩阵食用，
因此总是得到一个 $\Theta(n\log^2 n)$ 的解法。

对于二元生成函数的相关题，
转置原理能将计算 $[x^k]$ 的问题转化为计算 $[y^k]$，从而优化递推。
因此遇到二元生成函数时，转置原理是一个不错的选择。

最后，希望更多的人能借我这篇拙劣的文章学会转置原理。QWQ