转置原理学习笔记

本文主要是介绍转置原理学习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文参考 wangrx 浅谈转置原理 和 Vocalise 的博客。

1.矩阵的初等变换

也是高斯消元的基础。

1.1 定义

对矩阵施以下三种变换，称为矩阵的初等变换 ：

• 交换矩阵的两行（列）
• 以一个非零数 \(k\) 乘矩阵的某一行（列）
• 把矩阵的某一行（列）的 \(l\) 倍加于另一行（列）

对单位矩阵 \(I\) 施以一次初等变换得到的矩阵，称为初等矩阵。

1.2 一些定理

设 \(A_{m\times n}=(a_{ij})_{m\times n}\)

• 定理 1 ：对 \(A\) 的行施以一次初等变换，等同于用同种 \(m\) 阶初等矩阵左乘 \(A\)。对 \(A\) 的列施以一次初等变换，等同于用同种 \(n\) 阶初等矩阵右乘 \(A\)。

​ Proof：将 \(A\) 和 \(I\) 矩阵分块即可。

容易验证，初等矩阵都是可逆的，且它们的逆仍是初等矩阵。

\(I(ij)^{-1}=I(ij),I(i(k))^{-1}=I(i(\dfrac{1}{k})),I(ij(l))^{-1}=I(ij(-l))\)

• 定理 2 ：\(n\) 阶矩阵 \(A\) 可逆的充要条件是它可以写成一些初等矩阵的乘积。

因此，\(A\) 可以表示成若干个初等矩阵的乘积。

2.算法的转置

2.1 定义

将一个算法看做方阵 \(A\)，输入向量为 \(\vec v\)，输出向量为 \(A \vec v\)，则称该算法为线性算法。

许多算法都是线性算法，例如 FFT 的单位根矩阵。

2.2 转置的定义和性质

当输入为 \(\vec v\)，输出为 \(A^T\vec v\) 的算法称为该算法的转置算法。

转置的几个性质：

• \((AB)^T=B^TA^T\)

• 对于初等矩阵的转置： 前两种的转置是它本身。最后一种如果是将第 \(i\) 行（列）的 \(k\) 倍加到第 \(j\) 行，

  则其转置为将第 \(j\) 行（列）的 \(k\) 倍加到第 \(i\) 行（列）。

2.3 线性算法的判定

但算法的实际流程并未与矩阵建立起对应的方式。我们需要找到一种途径来刻画这个过程。

将输入，输出变量和运行过程中的一切辅助变量（也就是整个内存）拼成一个向量。

也就是已知 \(\begin{bmatrix} \vec v \\ \vec 0 \\ \vec 0 \end{bmatrix}\)， 求 \(\begin{bmatrix} \vec 0 \\ \vec 0 \\ A \vec v\end{bmatrix} = \begin{bmatrix} O \ \ \ O \ \ \ O \\ O \ \ \ O \ \ \ O \\ A \ \ \ O \ \ \ O\end{bmatrix}\begin{bmatrix}\vec v \\ \vec 0 \\ \vec 0\end{bmatrix}\).

若 \(A\) 不是方阵，也可以通过补 \(0\) 补成方阵。

称向量中的量为变量，矩阵中的量为常量。

具体的，线性算法只包含一下运算：

• 交换两个变量。
• \(x \leftarrow m \times x\)，\(x\) 为变量， \(m\) 为常量。
• \(x \leftarrow x+ m \times y，\)\(x, y\) 为变量，\(m\) 为常量。

2.4 原算法与转置算法的转换

将矩阵分解为初等矩阵，设 \(A = E_1E_2 \cdots E_{n}\)，则有 \(A^T = E_n^TE_{n-1}^T \cdots E_1^T\)。

由转置的性质可知，将算法转置相当于将运算顺序反过来，再讲 \(x \leftarrow x +my\)，改写成 \(y \leftarrow y + mx\) 即可。

3.常见算法的转置

推荐阅读：127： 浅谈转置原理

3.1 前缀和

前缀和问题 ：\(b_i = \sum\limits_{j \leq i}a_i\)，转置为后缀和问题 \(a_i=\sum\limits_{i \leq j}b_j\) 。

for(int i = 1; i <= n; ++i) a[i] += a[i - 1];

首先将执行顺序倒序，变成 ：

for(int i = n; i >= 1; --i) \\ do something..

然后将 \(a_i \leftarrow a_i +a_{i - 1}\) 转置为 \(a_{i-1} \leftarrow a_{i-1}+a_i\)。

for(int i = n; i >= 1; --i) a[i - 1] += a[i]; 

3.2 DFT

\(n\) 阶 DFT 形如 ：$$

3.3 多项式乘法

3.4 多项式多点求值

3.5 More...

这篇关于转置原理学习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！