“随机算法”最近在部分 svd 中非常流行。可以在此处下载仅标头实现：http ://code.google.com/p/redsvd/

可以在此处找到对当前方法的评论：http: //arxiv.org/abs/0909.4061

对于完整的 svds，我不确定你是否能比 Householder 做得更好。

我在这里读到，研究正朝着一种保证正交性的逆迭代方法前进$\mathcal{O}(N)$复杂。我有兴趣了解这方面或其他方面的进展。

（因为没有时间写细节，所以想发表一些评论，但评论框变得相当大。）

我相信这将是 Dhillon 和 Parlett 的MRRR（多个相对稳健的表示）算法。这植根于费尔南多以前的工作，而这反过来又受到吉姆威尔金森在他关于特征值问题的不朽著作中提出的一个问题的启发。用于获得奇异向量的“逆迭代”部分植根于Fernando 的“扭曲分解”概念，该概念利用分解矩阵成$\mathbf L\mathbf D\mathbf L^\top$和$\mathbf U\mathbf D\mathbf U^\top$分解。

另一方面，算法的“奇异值”部分来自（移位的）微商差（dqd(s)）算法，它是Fernando、Parlett、Demmel 和 Kahan先前工作的结晶（灵感来自来自 Heinz Rutishauser）。

您可能知道 SVD 方法通常先进行双对角分解，然后再从双对角矩阵获得奇异值。不幸的是，我对前端双对角分解的当前最佳方法不太了解；最后我检查了一下，通常的方法是从带有列旋转的 QR 分解开始，然后对三角因子适当地应用正交变换，最终获得双对角分解。

我知道我对细节很吝啬；一旦我可以访问我的图书馆，我将尝试进一步充实这个答案......

有 PROPACK 和 nu-TRLan 库。

http://soi.stanford.edu/~rmunk/PROPACK/

http://crd-legacy.lbl.gov/~kewu/trlan/