39、线性系统求解与线性变换代数

线性系统求解与线性变换代数

1. 稀疏线性系统求解

1.1 问题描述

设 (V) 是有限域 (F) 上的有限维向量空间，维数为 (\ell>0)，(\tau:V\rightarrow V) 是 (F -) 线性映射。我们的目标是求解形如 (\tau(\gamma)=\delta) 的方程，即给定 (\tau) 和 (\delta\in V)，找到满足该方程的 (\gamma\in V)。

1.2 算法性质

我们开发的算法具有以下性质：
- 概率性算法。
- 期望在 (F) 中进行 (O(\ell^2)) 次运算。
- 期望对 (\tau) 进行 (O(\ell)) 次求值。
- 需要 (O(\ell)) 个 (F) 中元素的存储空间。

1.3 与高斯消元法的比较

当表示 (\tau) 的矩阵是稀疏的，具有 (\ell^{1 + o(1)}) 个非零元素时：
|算法|运算次数|存储空间|
| ---- | ---- | ---- |
|本文算法| (\ell^{2+o(1)}) 次 (F) 中的运算| (\ell^{1+o(1)}) 个 (F) 中元素的空间|
|高斯消元法| (\Omega(\ell^3)) 次 (F) 中的运算| (\Omega(\ell^2)) 个 (F) 中元素的空间|

由此可见，当矩阵稀疏时，本文算法比高斯消元法更高效。而且，只要 (\tau) 可以用 (o(\ell^2)) 次 (F) 中的运算求值和/或用 (o(\ell^2)) 个 (F) 中元素的空间表示，本文算法在时间和/