数值线性代数运算的计算量

2025.07.25304 words

基础数值线性代数运算

基础数值线性代数运算及粗略计算量（ $m \ge n$ ）：

任务	主导计算量	说明
向量内积 $x^{\top}y$	$O(n)$	BLAS1
axpy $y\leftarrow y+\alpha x$	$O(n)$	BLAS1
矩阵-向量乘 $Ax$	$O(mn)$	BLAS2
矩阵-矩阵乘 $AB$	$O(mnp)$	BLAS3
三角系统求解 $Tx=b$	$O(n^2)$
LU	$O(n^3)$
Cholesky	$O(n^3)$	对称正定
econ QR	$O(mn^2)$
full QR	$O(m^2n)$
econ SVD	$O(mn^2)$
full SVD	$O(m^2 n)$
特征值分解	$O(n^3)$
最小二乘（QR 或正规方程）	$O(mn^2)$
稀疏矩阵-向量乘	$O(\mathrm{nnz}(A))$	Krylov/迭代法核心操作
稀疏带状矩阵-向量乘	$O(b n)$	$b$ 为带宽

低秩矩阵表示及常见操作

下面整理低秩矩阵表示及常见操作的粗略计算量，其中 $U\in\mathbb{R}^{m\times r}$ ， $V\in\mathbb{R}^{n\times r}$ ， $r\ll \min(m,n)$ 。

双因子表示

Copy LaTeX

任务	主导计算量	注释
矩阵-向量乘 $UV^{\top} x$	$O((m+n)r)$	对计算顺序敏感，例如 $U (V^{\top} x)$ ，下面类似
矩阵-矩阵乘 $UV^{\top} B$	$O((m+n)rp)$
恢复满矩阵	$O(mnr)$
低秩截断压缩	$O((m+n)r^2+r^3)$	两侧正交化 + 小矩阵做 SVD，下面类似

对角核心矩阵

Copy LaTeX

其中 $\Sigma \in\mathbb{R}^{r\times r}$ 为对角矩阵。

任务	主导计算量	注释
矩阵-向量乘 $U\Sigma V^{\top} x$	$O((m+n)r)$
矩阵-矩阵乘 $U\Sigma V^{\top} B$	$O((m+n)rp)$
恢复满矩阵	$O(mnr)$
低秩截断压缩	$O(1)$	直接截断即可

一般核心矩阵

Copy LaTeX

其中 $S\in\mathbb{R}^{r\times r}$ 不要求对角。

任务	主导计算量	注释
矩阵-向量乘 $USV^{\top} x$	$O((m+n)r+r^2)$
矩阵-矩阵乘 $USV^{\top} B$	$O((m+n)rp+r^2p)$
恢复满矩阵	$O(mr^2+mnr)$
低秩截断压缩	$O((m+n)r^2+r^3)$