2
$\begingroup$

Suppose we want to find $x$ such that:

$$x=b+Ax$$

where $A$ is a large sparse square matrix with eigenvalues in the unit circle.

There are two representations of the solution:

1) $$x=(I-A)^{-1}b,$$

2) $$x=\sum_{k=0}^\infty{A^k b}.$$

Since we cannot practically store powers of the matrix $A$ (due to memory limits: indeed in practice, we just have a function that computes $Ax$ given $x$), using the representation 2) means evaluating the recurrence:

$$x_t=b+A x_{t-1}.$$

However, since $A$ may have eigenvalues close to $1$ in magnitude, this will converge slowly.

Is there a multivariate series acceleration method which would handle such recursions? (E.g. a multivariate version of the Aitken "delta-squared" process/Steffensen's method.)

Alternatively, is there a technique for solving 1) directly that is guaranteed to have good performance? Do our assumptions on $A$ imply anything about the performance of GMRES / CGS / BICGSTAB(L) / QMR etc.?

Note: This question: "Is there a faster method to compute the geometric series of a matrix?" is similar but seems to be interested in finite sums of small dense matrices, rather than infinite sums of large sparse matrices.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Yes, what you describe as the "matrix geometric series" can be understood as a modified Richardson iteration with unit step-size (if $A$ is also symmetric, then this boils down to gradient descent), and the problem of optimally accelerating the convergence of this sequence is solved by GMRES in the Euclidean norm. $\endgroup$ – Richard Zhang Apr 10 '18 at 18:55
  • $\begingroup$ Thanks. GMRES without restarts is prohibitively expensive in terms of memory though. (These are really huge matrices.) And GMRES with restarts does not seem particularly reliable in practice. $\endgroup$ – cfp Apr 10 '18 at 19:31
  • 1
    $\begingroup$ There is a theorem (due to Faber and Manteuffel) that states that for nonsymmetric matrices, there cannot exist a Krylov subspace algorithm that is simultaneously optimal (in the sense of GMRES) as well as limited memory (in the sense of CG). In practice, GMRES(k) is locally but not globally optimal. QMR / TFQMR are "quasi-optimal" in a heuristic sense. BiCGSTAB(k) is in some ways like GMRES(k), but also attempts at global optimization in a heuristic sense. $\endgroup$ – Richard Zhang Apr 10 '18 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.