7
$\begingroup$

Are there iterative methods for the solution of nonsymmetric linear systems $Ax=b$ that can take (theoretical or practical) advantage from knowing that $A+A^T$ is positive definite? These matrices are always nonsingular, but does this help the solution process, at least for some methods?

$\endgroup$
6
  • 2
    $\begingroup$ I think, for such matrices, BiCGStab is guaranteed to converge. But I cannot find a reference. I think also the convergence bounds of IDR(s) can be further improved under that assumption. There was a talk on it at ENUMATH 2015, iirc. $\endgroup$ Apr 11 at 23:04
  • $\begingroup$ @AbdullahAliSivas: What is IDR(s)? $\endgroup$ Apr 12 at 13:00
  • $\begingroup$ IDR is the shorthand for Induced Dimension Reduction, and it is a short-recurrence Krylov subspace method developed by Peter Sonneveld, and then improved by Martin B. van Gijzen and Peter Sonneveld. (s) is the dimensionality of the induced subspaces. BiCGStab methods and IDR(s) are methods are mildly related, they are both developed out of a desire to avoid an MtV operation, which may be why they benefit from the fact that A+A^T is positive definite. $\endgroup$ Apr 12 at 15:24
  • 2
    $\begingroup$ Links to IDR: epubs.siam.org/doi/abs/10.1137/070685804 and dl.acm.org/doi/10.1145/2049662.2049667 $\endgroup$ Apr 13 at 23:42
  • $\begingroup$ I think this is a fun question because it shows that if you have structure (however obscure, as in the current case), you could think of exploiting it for more efficient algorithms. $\endgroup$ Apr 13 at 23:44
4
$\begingroup$

This is a response/answer to the discussion in the comments to the question.

I have been looking for the sources too, and I couldn't find them either. I am wondering if I am misremembering. Let me maybe discuss it in my own words.

First of all, we know that a complex matrix $A$ is positive definite, e.g. $$Re[x^{\ast}Ax]>0 \qquad \forall x\in\mathbb{C}^n,$$ if and only if its Hermitian part $(A+A^H)/2$ is positive definite. Since we have the PDness of the Hermitian part, we know that the matrix itself is PD too. We know that GMRES is guaranteed to find the exact solution for non-singular matrices $A\in \mathbb{C}^{n\times}$ in $n$ iterations, PD matrices are non-singular, hence, GMRES is going to converge.

(I am sure you already know the next part, but I will repeat it to make it more future-proof.)

However, the predicting convergence of GMRES to a tolerance is still not straightforward. The most common way is to check the eigenvalues of a matrix (can be found in papers published in the last decade), even though Greenbaum et al. showed that the eigenvalues of a matrix is not a good predictor of convergence for GMRES in their work "Any Nonincreasing Convergence Curve is Possible for GMRES" in 1996. Hence, alternative analysis techniques were proposed (and should be used), namely, pseudospectrum and field-of-values (numerical range). The field-of-values (FOV) of a matrix $A$ is defined as the set $FOV(A) = \{z^{\ast}Az : z\in \mathbb{C}^n, \|z\|=1 \}$. Furthermore, we know that GMRES convergence can be predicted (asymptotically) if the FOV does not contain the origin (see the reference at the end of the answer).

Now, what I remember (from the citations neither of us could find) is that both BiCGStab($\ell$) and IDR(s) can be written in terms of another Krylov subspace method followed by GMRES($m$) for small $m$, say $0<m\leq \ell$ (or, respectively, s). The argument, then, is that at every second half iteration of BiCGStab (where GMRES($\ell$) is applied) it is "guaranteed" (take it with a hint of salt, probably faulty memory) there will be some reduction in residual. Therefore, we expect BiCGStab($\ell$) convergence curves to be monotonically decreasing. Hence, eventually BiCGStab($\ell$) is going to converge (though it may require more than $n$ iterations). The argument for IDR(s) was similar as far as I remember.

Comprehensive review with some new results for GMRES: J. Liesen and P. Tichý, The Field of Values Bounds on Ideal GMRES, arXiv:1211.5969, 2018.

$\endgroup$
0
$\begingroup$

What about trying various forms of the Woodbury matrix identity?

https://en.wikipedia.org/wiki/Woodbury_matrix_identity

Depending on how prominent the symmetric and antisymmetric components are, you could consider the anti-symmetric portion a small-ish perturbation of the original matrix.

$$A^{-1}=(A_s-A_a)^{-1}=\sum_{k=0}^{\infty}(A_s^{-1}A_a)^kA_s^{-1}$$ where $A_s=\frac{1}{2}(A^T+A)$ and $A_a=\frac{1}{2}(A^T-A)$. Perhaps you only need a few terms of the sum to be close enough.

$$A^{-1}\approx A_s^{-1} + A_s^{-1}A_aA_s^{-1}$$

There are also some interesting properties of anti-symmetric matrices that are evident if you compute powers of $A_a^k$.

$\endgroup$
1
  • 1
    $\begingroup$ This is just iterative refinement, using the Cholesky factor of the symmetric part in place of an exact factorization. It performs very poorly unless $A$ is nearly symmetric. $\endgroup$ Apr 27 at 12:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.