支持下 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

分类: 文章

1 条评论

Qiuly · 2021年11月9日 6:52 下午

orz qwq

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code