The convergence behavior depends to a great deal on the
distribution of the spectrum of .
Two matrices with precisely the same sparsity
pattern could exhibit completely different convergence characteristics
for a given choice of
and
. Therefore, it would be misleading to
draw any conclusions based solely on operation counts per iteration.
Nevertheless, it can be useful to have a notion of the major costs
of an iteration to guide initial choices.
In the following, we assume that the cost of a matrix-vector
product is
. For a sparse matrix,
one could think of
as twice the average number of nonzero entries
per row of
. For a dense matrix
, and
for a fast Fourier transform (FFT) matrix
. See §10.2.
For a fixed value of
and
,
the cost (in floating point operations) for one iteration of IRLM is
If the matrix-vector product is cheap (i.e.,
is quite small),
the cost of implicit restart is significant and alternatives
should be considered. One of these might be to use a polynomial
spectral transformation. This would involve operating with a suitably
constricted polynomial function of
in place of
.
An example would be a Chebyshev polynomial designed to damp the unwanted
portion of the spectrum. The action
would,
of course, be applied as a succession of matrix-vector products
involving
.