直接方法

在本节中，我们将简要讨论计算稠密矩阵的奇异值和奇异向量的方法。 这些方法有时被称为变换方法。 其中一些或全部方法已在LAPACK、ScaLAPACK以及MATLAB的svd命令中实现。^[1]

虽然可以将第4.2节中的变换方法应用于其中一个厄米矩阵A^* A、AA^*或H(A)，但实际使用的方法是专门为SVD设计的，因此更高效和准确。

最常见的变换方法分三个阶段计算瘦SVD，如下所示。 （它们可以很容易地修改以计算完整的SVD，或者仅计算选定的奇异值和/或奇异向量，但为了简单起见，我们只介绍瘦SVD。）

1. 找到一个n阶酉矩阵V_1和一个m行n列、列正交的矩阵U_1，使得 U_1^*A V_1 = B是一个n阶双对角矩阵，即仅在主对角线和第一上对角线上非零。
2. 计算B的SVD： B = U_2 \Sigma V_2^*。
3. 乘以U = U_1 U_2和V = V_1 V_2，得到瘦SVD A = U \Sigma V^*。

第一阶段，即双对角化阶段，通过LAPACK例程xGEBRD和ScaLAPACK例程PxGEBRD使用一系列\min (m-1,n)个左酉Householder反射和n-2个右酉Householder反射实现，成本为4n^2(m-\frac{1}{3}n)次浮点运算。 如果只需要奇异值，第二阶段的成本仅为O(n^2)，远低于第一阶段的成本，第三阶段则省略。 如果需要所有左和右奇异向量，成本则强烈依赖于所选算法，如下所述。

第二阶段的算法类似于第4.2节中讨论的对称三对角特征问题的算法，下面概述了一些差异。

目前，最快的串行或共享内存并行稠密SVD例程是LAPACK的xGESDD，但更快的正在开发中。 最快的分布式内存并行稠密SVD例程是ScaLAPACK的PxGESVD，同样，更好的也在开发中。

QR算法：

该算法找到所有奇异值，并可选地找到所有左和/或右奇异向量。 仅奇异值的成本为O(n^2)，奇异向量的成本为O(n^3)。 它可以实现，使得所有奇异值几乎都计算出正确的有效数字，即使是极小的奇异值（只要不发生下溢）[123]。 QR用于在LAPACK的计算例程xBDSQR中计算奇异向量，该例程被驱动例程xGESVD用于计算稠密矩阵的SVD，但已被下面描述的更快方法取代。 xBDSQR也被ScaLAPACK驱动例程PxGESVD使用。

DQDS算法：

该算法仅在O(n^2)时间内找到双对角矩阵的奇异值，但比QR更准确和更高效[168,355,360]。 它是计算奇异值的首选串行算法，在LAPACK中实现为xLASQ1，并被所有LAPACK驱动例程使用。

分治法：

这是目前LAPACK中用于找到大于约25乘25的双对角矩阵的所有奇异值和向量的最快方法[208,12]。 它将矩阵分成两半，计算每一半的SVD，并通过求解一个特殊的有理方程将解粘合在一起。对于一个大的双对角矩阵，这会递归重复，直到部分小于25，这时调用QR算法。^[2]它可能比DQDS或QR稍不准确，因为最小奇异值的误差可能达到机器ε乘以\sigma_1，但这几乎总是足够好。

分治法由LAPACK计算例程xBDSDC实现，该例程被LAPACK驱动例程xGESDD用于计算稠密矩阵的SVD。 xGESDD是目前LAPACK中稠密矩阵SVD的首选算法。

二分法和逆迭代：

二分法和逆迭代可用于仅找到感兴趣的奇异值和向量。 当前算法每个奇异三元组的工作时间为O(n)，除非奇异值在一个k个相邻奇异值的簇中，在这种情况下，如果使用正交化以尝试保证正交奇异向量，成本可能上升到O(nk^2)。如果许多奇异值紧密聚集，这可能高达O(n^3)。 尽管如此，有时仍可能无法保证正交性[129]。 LAPACK、ScaLAPACK或MATLAB目前不包含基于二分法和逆迭代的SVD例程。

最近在[168,128,358,356]中的进展承诺了一种算法，该算法每个奇异三元组的工作时间为O(n)，同时保证正交性，但尚未完成。完成后，LAPACK和ScaLAPACK都将提供这种算法，它应该是所有情况下的最快算法。

如果A是带状的，第一阶段可以通过LAPACK计算例程xGBBRD更便宜地执行，但没有可用的LAPACK驱动例程。

最后，我们提到用于SVD的雅可比方法[114,198]。 这种变换方法反复将A右乘以基本正交矩阵（雅可比旋转），直到A收敛到U \Sigma；雅可比旋转的乘积是V。雅可比比上述任何变换方法都慢（它可以做到运行时间大约是QR的两倍[136]），但有一个有用的特性，即对于某些A，它可以比上述任何方法更准确地提供极小的奇异值及其奇异向量，前提是它得到了适当的实现[118,115]。

1. 已经宣布，基于LAPACK的数值库将成为MATLAB下一个主要版本的一部分；请参阅《MATLAB、Simulink和工具箱用户通讯，2000年冬季版》，网址为http://www.mathworks.com/company/newsletter/clevescorner/winter2000.cleve.shtml。
2. 这段代码对浮点运算的假设非常温和。它能在具备保护位（guard digit）的加减法机器上运行，也能在没有保护位的二进制机器上工作，例如Cray X-MP、Cray Y-MP、Cray C-90或Cray-2等机型。理论上，它可能在不具备保护位的十六进制或十进制机器上失效，但我们目前尚未发现此类情况。