什么操作是可以承受的？

最经济的矩阵操作是乘法，通过$A^* A$、$AA^*$或$H(A)$进行。注意，$y=A^*Ax$的计算方式是$y=A^*(Ax)$，即先进行一次$A$的乘法，然后进行一次$A^*$的乘法。不直接形成$A^* A$有两个原因：首先，$A^* A$可能比$A$稠密得多，因此乘法成本更高。实际上，即使$A$只有一行非零元素，$A^* A$也可能非常稠密。其次，形成$A^* A$的成本相当于计算$n/4$次$A^*(Ax)$，这通常已经足够计算所需的奇异三元组。

类似的情况也适用于$AA^*$，只是由于$AA^*$是$m$乘$m$的矩阵，而$m \geq n$，$AA^*$可能（任意）比$A^* A$大。此外，存储和操作$n$个向量的成本可能（任意）比$m$个向量低。因此，通常使用$A^* A$而不是$AA^*$更好，并通过$u_i = Av_i / \sigma_i$从$A^* A$的特征向量$v_i$（即$A$的右奇异向量）恢复左奇异向量$u_i$。（但请参阅下面的移位-反转注释，了解$AA^*$比$A^* A$更好的情况。）

进行一次$H(A)$的乘法成本与进行一次$A^* A$或$AA^*$的乘法相同。

现在考虑移位-反转，这需要计算以下矩阵之一的$LU$或$LDL^*$分解： $A^*A - \sigma I$、 $AA^* - \sigma I$或 $H(A) - \sigma I$。 这里$\sigma$是一个移位，或从其减去的矩阵的近似特征值。这些分解的成本强烈依赖于矩阵的稀疏结构。根据$A$的维度和稀疏结构，对以下矩阵之一进行分解可能比其他矩阵便宜得多： $A^*A - \sigma I$、 $AA^* - \sigma I$或 $H(A) - \sigma I$。以下是一些例子：

1. 如果$A$在第一列和主对角线上非零，那么$A^* A$和$H(A)$与$A$几乎一样稀疏，但$AA^*$是稠密的。因此，形成和分解$A^*A - \sigma I$的时间和空间成本分别为$O(m+n)$和$O(n)$，而$AA^* - \sigma I$的时间和空间成本分别为$O(m^3)$和$O(m^2)$，两者都高得多。形成和分解$H(A) - \sigma I$的时间和空间成本也是$O(m+n)$，但常数因子比$A^*A - \sigma I$大。

2. 如果$m \approx n$，且$A$在第一行和主对角线上非零，那么$AA^*$和$H(A)$与$A$几乎一样稀疏，但$A^* A$是稠密的。因此，形成和分解$AA^* - \sigma I$的时间和空间成本分别为$O(n)$，而$A^*A - \sigma I$的时间和空间成本分别为$O(n^3)$和$O(n^2)$，两者都高得多。形成和分解$H(A) - \sigma I$的时间和空间成本也是$O(n)$，但常数因子比$AA^* - \sigma I$大。

3. 如果$m \approx n$，且$A$在第一行、第一列和主对角线上非零，那么$H(A)$与$A$几乎一样稀疏，但$AA^*$和$A^* A$都是稠密的。因此，形成和分解$H(A) - \sigma I$的时间和空间成本分别为$O(n)$，而$AA^* - \sigma I$或$A^*A - \sigma I$的时间和空间成本分别为$O(n^3)$和$O(n^2)$，两者都高得多。

上述例子是为了展示极端情况，其中$A^* A$、$AA^*$和$H(A)$的行为尽可能不同。这也假设正在分解的矩阵是良序的；即，行和列的顺序是为了在分解过程中最小化填充和操作。对于上述例子，使用了对称最小度排序。通常，可以通过符号分解以比实际执行分解本身低得多的成本计算排序并估计形成和分解$AA^* - \sigma I$、$A^*A - \sigma I$和$H(A) - \sigma I$所需的工作和空间。详情请参见第10.3节。