Matlab 的 svds 函数的缩放/性能（Lanczos 双对角化）

计算科学 matlab svd
2021-12-24 07:25:29

我有一个简单的 Matlab 脚本，旨在计算k矩阵的奇异值A. A是一个随机密集方阵，大小为5000×5000，其中 100 个奇异值被限制为 0（尽管最后一个细节似乎对我的问题无关紧要）。

我在 Matlab 中通过[Uk, Sk, Vk] = svds(A, k);. 根据文档，svds使用 Lanczos bidiagonalization 来计算这些值。我查看了函数定义 ( edit svds) 并没有看到任何相关的分支，例如，根据不同的条件在后台使用不同的算法。但是，当我增加k，我得到非常好奇的缩放/性能：

作为奇异值 k 数量的函数的 svds 缩放

文档提到

增加 k 有时可以提高性能，尤其是当矩阵具有重复的奇异值时。

但我将此解释为意味着性能会有所提高k，而不是大幅减少总运行时间。

这是 Lanczos 双对角化的已知行为（我不太熟悉的算法）吗？或者有没有人猜测为什么会有这样的表现svds？

编辑：这是我的脚本的最小版本，因此其他人可以尝试重现：

results = [];
A = rand(5000, 5000);
[U, S, V] = svd(A);
dS = diag(S);
dS(4900:5000) = 0;
A = U*diag(dS)*V;
b = rand(5000, 1);
for k = 100 : 100 : 4500
    tic
        [Uk, Sk, Vk] = svds(A,k);
        Ahat = Vk*diag(1./diag(Sk))*Uk';
        test = Ahat * b;
    time_k = toc
    results = [results; k time_k];
end
plot(results(:,1), results(:,2))
1个回答

我能够通过代码段重现您的初始结果。svd但是，通过在您的通话中添加更多选项：

[Uk, Sk, Vk] = svds(A,k,'largest','display',true);

我们看到算法确实变成了密集算法（@ThijsSteel）。

对于 300 个奇异值：

=== Singular value decomposition A*v = sigma*u, A'*u = sigma*v ===

Computing 300 largest singular values of 5000-by-5000 matrix A.

Parameters:
  Maximum number of iterations: 100
  Tolerance: 1e-10
  Subspace Dimension: 900

Find largest singular values for A*v = sigma*u, A'*u = sigma * v.

--- Start of Lanczos bidiagonalization method ---
Iteration   1: 144 of 300 singular values converged. Smallest non-converged residual 1.4e-09 (tolerance 1.0e-10).
Iteration   2: 300 of 300 singular values converged.
---
To check if singular value multiplicities were missed, restart the method, looking for k+1 singular values.
---
Iteration   3: 301 of 301 singular values converged.
---
No additional multiple singular values found. Successful return.
---

time_k =

   55.5512

对于 2300 个奇异值：

=== Singular value decomposition A*v = sigma*u, A'*u = sigma*v ===

Computing 2300 largest singular values of 5000-by-5000 matrix A.

Parameters:
  Maximum number of iterations: 100
  Tolerance: 1e-10
  Subspace Dimension: 6900

Compute SVDS by calling SVD, because the subspace dimension is equal to the minimum matrix size.

time_k =

   45.7203
其它你可能感兴趣的问题
上一篇使用连续过度松弛技术计算泊松方程的误差，Python 下一篇如何在反应扩散计算中使用拉普拉斯算子避免方形？