6.1 Some Practicalities

For large-scale problems, the iterative regularization methods can be favorable alternatives to the direct methods for the following reasons.

• The matrix A is never altered, but only "touched" via the matrix-vector products with A and A ^T, while matrix factorizations and in particular orthogonal factorizations such as the QR factorization and the SVD destroy any sparsity or structure of A. Hence, iterative methods are suited whenever one can take advantage of the sparsity or structure of A in the matrix-vector multiplications. Recall that a matrix-vector multiplication with A or A ^T requires m n flops if A is sparse and n is the average number of nonzeros per row, and 15 p log ₂ p flops if A has Hankel or Toeplitz structure and p is the smallest power of 2 satisfying p = 2 ^t ? 2 max( m, n) ? 1; cf. [351, 4.2.4]. See also [171, 6.2]. Sparse matrix-vector products are discussed in [36, 7.1.2].

• The "atomic operations" of the iterative methods are the matrix-vector products with A and A ^T plus saxpy operations (i.e., y ? ax + y), vector 2-norms, and possibly backsolves. These operations are fairly simple to parallelize, and it is known how to overlap the computations with communication on message-passing parallel computers [83], [328].

• Iterative methods are the only methods of choice for problems where the matrix-vector products