Looking for fast computation method of $Ax=b$ ($A$ is sparse matrix)

Question

I am looking for fast method to solve linear equation $$Ax=b$$

In which A is sparse matrix. Could you suggest to me some current method for this task. Thank in advance

Answer 1

For nonsymmetric sparse $A$, the Conjugate Gradient Squared method (CGS) is a good approach (P. Sonneveld, SIAM J. Sci. Statist. Comput., 10 (1989), pp. 36-52). It is closely related to the older Bi-Conjugate Gradient method (BiCG) but avoids multiplications by the transpose matrix $A^T$.

Per Daniel Shapero's SciComp.SE post, there is no guarantee of convergence with such methods. Generally speaking when both CGS and BiCG converge, CGS does so about twice as fast (for roughly the same amount of computation).

In particular there is no guarantee, even with exact arithmetic, that the sizes of residuals will decrease monotonically as with conjugate gradients for symmetric positive definite matrices. The Bi-Conjugate Gradient Stabilized method (BiCGStab) was proposed by H. A. van der Vorst (1992) to "stabilize" the residual sizes by adding a GMRES step after every BiCG step. This provides smoother convergence behavior, but at the expense of substantially greater computation.

A generalized Conjugate Gradient Squared method proposed by Fokkema, Sleijpen, and Van der Vorst (1996) also aims at regularizing the behavior of residuals but with less extra computation. More recent developments along ideas by Sonneveld are reviewed in IDR: A new generation of Krylov subspace methods? by Rendel, Rizvanolli and Zemke (2011).

As Daniel Shapero remarks, "coming up with a good preconditioner for your specific matrix is probably more important than using the optimal outer-level iterative solver." Since your matrix $A$ has no predictable pattern, being the result of randomly sampled entries, I don't have a suggestion for how to go about that, but perhaps you do. Daniel also provided a link to a good survey How fast are nonsymmetric matrix iterations? by Nachtigal, Reddy, and Trefethen (1992).

The Matlab implementation might be a good way to experiment with CGS and preconditioning strategies.

---

The OP's Comments above about "the Wiedemann method" (perhaps equating it with Krylov subspace iterative methods) are puzzling. Douglas Wiedemann (1986) proposed Solving Sparse Linear Systems over Finite Fields, which might suggest the matrix $A$ has entries drawn from a finite field. However the Question does not state this, even indirectly through its tags. In answering above I've assumed that the matrix $A$ samples from a field of characteristic zero (hence necessarily an infinite field). [Note: I now see that the OP has a previous, yet unanswered Question on Wiedemann for solving sparse linear equation which links to the same paper on solving over finite fields.]