What Operations Can One Afford to Perform?

The cheapest matrix operation is multiplication, by $A^* A$, $AA^*$, or $H(A)$. Note that $y=A^*Ax$ is computed as $y=A^*(Ax)$, i.e., as one multiplication by $A$ and then one by $A^*$. There are two reasons not to form $A^* A$ itself: First, $A^* A$ can be much denser than $A$ and so more expensive to multiply by. Indeed, $A^* A$ can be dense even when $A$ has only one nonzero row. Second, it can cost as much to form $A^* A$ as $n/4$ products $A^*(Ax)$, which is often more than enough to compute the desired singular triplets.

Similar comments apply to $AA^*$, except that since $AA^*$ is $m$-by-$m$, and $m \geq n$, $AA^*$ can be (arbitrarily) larger than $A^* A$. Also, storage and manipulation of $n$ vectors can be (arbitrarily) cheaper than $m$ vectors. So in general it is better to use $A^* A$ instead of $AA^*$, and recover the left singular vectors $u_i$ from the eigenvectors $v_i$ of $A^* A$ (right singular vectors of $A$) by $u_i = Av_i / \sigma_i$. (But see the comments on shift-and-invert below for a case when $AA^*$ is much better than $A^* A$.)

One multiplication by $H(A)$ costs the same as one multiplication by either $A^* A$ or $AA^*$.

Now consider shift-and-invert, which requires computing an $LU$ or $LDL^*$ factorization of either $A^*A - \sigma I$, $AA^* - \sigma I$, or $H(A) - \sigma I$. Here $\sigma$ is a shift, or approximate eigenvalue of the matrix from which it is being subtracted. The cost of these factorizations depends strongly on the sparsity structure of the matrix. Depending on the dimensions and sparsity structure of $A$, it may be much cheaper to factorize one of $A^*A - \sigma I$, $AA^* - \sigma I$, or $H(A) - \sigma I$ instead of the others. Here are some examples:

1. If $A$ is nonzero in the first column and along the main diagonal, then $A^* A$ and $H(A)$ are nearly as sparse as $A$ but $AA^*$ is dense. So forming and factoring $A^*A - \sigma I$ costs time $O(m+n)$ and space $O(n)$, but $AA^* - \sigma I$ costs time $O(m^3)$ and space $O(m^2)$, both vastly more. Forming and factoring $H(A) - \sigma I$ also costs time and space $O(m+n)$, but the constants are larger than for $A^*A - \sigma I$.

2. If $m \approx n$, and $A$ is nonzero in the first row and along the main diagonal, then $AA^*$ and $H(A)$ are nearly as sparse as $A$ but $A^* A$ is dense. So $AA^* - \sigma I$ costs $O(n)$ time and space to form and factor, but $A^*A - \sigma I$ costs time $O(n^3)$ and space $O(n^2)$, both vastly more. Forming and factoring $H(A) - \sigma I$ also costs time and space $O(n)$, but the constants are larger than for $AA^* - \sigma I$.

3. If $m \approx n$, and $A$ is nonzero in the first row, first column and along the main diagonal, then $H(A)$ is nearly as sparse as $A$ but both $AA^*$ and $A^* A$ are dense. So forming and factoring $H(A) - \sigma I$ costs time and space $O(n)$, but either $AA^* - \sigma I$ or $A^*A - \sigma I$ costs $O(n^3)$ time and $O(n^2)$, both vastly more.

The above examples are chosen to represent extremes, where the behavior of $A^* A$, $AA^*$, and $H(A)$ are all as different as possible. It also assumes that the matrices being factored are well ordered; i.e., the rows and columns are ordered to minimize fill and operations during factorization. For the above examples, symmetric minimum-degree ordering was used. In general, it is possible to compute the ordering and estimate the work and space required to factor $AA^* - \sigma I$, $A^*A - \sigma I$, and $H(A) - \sigma I$ by a symbolic factorization much more cheaply than actually performing the factorizations themselves. See §10.3 for details.