Next: Which Singular Values and Up: Iterative Algorithms   J. Previous: Iterative Algorithms   J.   Contents   Index

## What Operations Can One Afford to Perform?

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

Similar comments apply to , except that since is -by-, and , can be (arbitrarily) larger than . Also, storage and manipulation of vectors can be (arbitrarily) cheaper than vectors. So in general it is better to use instead of , and recover the left singular vectors from the eigenvectors of (right singular vectors of ) by . (But see the comments on shift-and-invert below for a case when is much better than .)

One multiplication by costs the same as one multiplication by either or .

Now consider shift-and-invert, which requires computing an or factorization of either , , or . Here 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 , it may be much cheaper to factorize one of , , or instead of the others. Here are some examples:

1. If is nonzero in the first column and along the main diagonal, then and are nearly as sparse as but is dense. So forming and factoring costs time and space , but costs time and space , both vastly more. Forming and factoring also costs time and space , but the constants are larger than for .

2. If , and is nonzero in the first row and along the main diagonal, then and are nearly as sparse as but is dense. So costs time and space to form and factor, but costs time and space , both vastly more. Forming and factoring also costs time and space , but the constants are larger than for .

3. If , and is nonzero in the first row, first column and along the main diagonal, then is nearly as sparse as but both and are dense. So forming and factoring costs time and space , but either or costs time and , both vastly more.

The above examples are chosen to represent extremes, where the behavior of , , and 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 , , and by a symbolic factorization much more cheaply than actually performing the factorizations themselves. See §10.3 for details.

Next: Which Singular Values and Up: Iterative Algorithms   J. Previous: Iterative Algorithms   J.   Contents   Index
Susan Blackford 2000-11-20