什么操作是可以承受的？

最经济的矩阵操作是乘法，通过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节。