转置原理

一、转置原理

若对于一个 \(n\times m\) 的矩阵 \(M\)，存在一个线性算法能够对于给定的 \(m\) 维列向量 \(a\)，求出 \(b = Ma\)，则一定存在一个线性算法能够在同时间复杂度内，对于一个给定的 \(n\) 维列向量 \(b\) 求出 \(a = M^T b\)。

若第一个算法的过程为 \(b = A_k A_{k-1}\cdots A_2 A_1 a\)，那么第二个算法的过程只需要 \(a ={A_1}^T {A_2}^T \cdots{A_{k-1}}^T {A_k}^T b\) 即可。

二、一些算法的转置

2.1 多项式多点求值

给定一个 \(n\) 次多项式 \(f(x)\) 以及 \(m\) 个点值 \(a_1, a_2, \ldots, a_m\)，对于 \(i \in [1,m]\)，求出 \(f(a_i)\)。

设 \(\displaystyle f(x)=\sum_{i=0}^n b_ix^i\)。

令向量 \(\displaystyle a=\begin{bmatrix}b_0\\b_1\\\vdots\\b_{n-1}\\b_n\end{bmatrix}\)，矩阵 \(\displaystyle M=\begin{bmatrix}1 & a_1 & \cdots & {a_1}^n \\ 1 & a_2 & \cdots & {a_2}^n \\ \vdots & \vdots & \ddots & \vdots\\ 1 & a_{m-1} & \cdots & {a_{m-1}}^n \\ 1 & a_m & \cdots & {a_m}^n \end{bmatrix}\)，则原问题相当于求出 \(b = Ma\)。

考虑其转置算法，对于一个给定的 \(m\) 维向量 \(\displaystyle b=\begin{bmatrix}c_1\\c_2\\\vdots\\c_{m-1}\\c_m\end{bmatrix}\)，有矩阵 \(\displaystyle M^T = \begin{bmatrix}1 & 1 & \cdots & 1 \\ a_1 & a_2 & \cdots & a_m \\ \vdots & \vdots & \ddots & \vdots\\ {a_1}^{n-1} & {a_2}^{n-1} & \cdots & {a_m}^{n-1} \\ {a_1}^n & {a_2}^n & \cdots & {a_m}^n\end{bmatrix}\)，即求 \(a = M^T b\)。

那么转置算法相当于 \(\forall i \in [0,n]\)，求 \(\displaystyle [x^i]\sum_{j=1}^m \frac{c_j}{1-a_jx}\)，这可以利用分治 NTT 在 \(\Theta(n \log^2 n)\) 的时间复杂度内求出。