为什么 Matlab 的 SVD 在瘦矩阵上比在胖矩阵上更快?

计算科学 matlab svd
2021-11-25 20:18:07

我今天注意到了一些奇怪的事情。我有一个X非常瘦的矩阵(20800 x 200),双精度实数,不稀疏,我想要它的 SVD 快速。Matlab 做得相当快:

> tic; [U,S,V] = svd(X,'econ'); toc
Elapsed time is 0.280848 seconds.

但是如果我要求它的转置的 SVD,这是一个非常胖的矩阵,它要慢得多。

> Xt = X';
> tic; [UU,SS,VV] = svd(Xt,'econ'); toc
Elapsed time is 0.722308 seconds.

任何想法为什么会这样?这看起来很奇怪,因为如果我想要一个胖矩阵的 SVD,这意味着我可以通过转置来更快地做到这一点,找到这个瘦矩阵的 SVD,然后交换“U”和“V”。

我的猜测是,这是因为 Matlab 使用列主顺序,所以在瘦的情况下,“U”矩阵是大的,并且在它上面运行的任何例程都使用 1 的步幅长度,而在相反的情况下, Matlab 实现调用具有非单位步长的东西,这在内存调用方面效率较低。

但即使有充分的理由,它也引出了一个问题,为什么 Matlab 不检查脂肪矩阵而只取转置的 SVD?转置运算符的速度非常快。例如,

> tic; [VV,SS,UU] = svd(Xt','econ'); toc
Elapsed time is 0.293725 seconds.

给了我VV,UU,SS和上面一样的东西,但要快得多。

3个回答

正如我在评论中已经提到的,这是一个可能的答案,它得到了 AlexE 在进一步评论中的一些实验的支持。

MATLAB 中的 SVD 使用 LAPACK 的 DGESVD,它基于 Gene Golub 的思想。主要是在 Fortran 中的矩阵上实现,即按列存储。以这种方式处理同一列中的值在内存传输的意义上是便宜的,因为 CPU 的预取系统检测到连续的数据流,并且来自同一列的元素很可能在算法请求它们之前可供 CPU 使用。关于矩阵的 Fortran 存储方案以及算法是如何实现的,访问列中的元素比访问行中的元素更有效。此外,由于具有大量行,这些操作利用了 BLAS 后端的线程(在 MATLAB 的情况下是 MKL)。

应用于计算高瘦矩阵的 SVD 问题,许多操作利用上述技术来加速计算。如果对这样一个矩阵进行转置,则数据访问方案不再那么规则,并且昂贵的行访问的数量会增加。此外,行数太少,无法通过列中的额外并行化来加速计算。

在我看来,由于我对 Matlab 内部的了解有限,您的理解是正确的。Matlab 使用次优算法,除了“他们没有想到这一点”或“他们不在乎优化它”之外,我没有看到其他合理的原因。

(另一个我没有很好答案的相关问题是“为什么 LAPACK 的 SVD 例程不DGESVD接受TRANS参数,不像其他几个?”。)

加速瘦矩阵的 SVD 的一个常见技巧是首先对其应用 QR 分解,然后在较小的矩阵 R 中进行 SVD。这给你 A = QR = QSVD,其中 QS 是正交的,然后 QSVD 是 SVD 分解. 也许,MATLAB 在应用 SVD 之前确实检查了矩阵的形状并使用了一些类似的技巧。