solving linear system whose symmetrized matrix is positive definite

Question

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?

Answer 1

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.

Answer 2

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$.