Are there any specialized methods available for solving structurally symmetric sparse linear systems?

Question

When solving $Ax=b$, prior knowledge about $A$'s structure can help in designing an efficient solver which exploits this information (e.g conjugate gradient method is to be used when $A$ is symmetric and is preferable to GMRES when we know $A$ is so )

For the set of non-linear equations I am working with, I am using the Newton-Raphson method for its solution. The Jacobian ($A$) of NR for every iteration, turns out to be sparse and also symmetric in its sparsity pattern for my problem (but not necessarily in its value).

So $a_{ij} \neq 0 \Leftrightarrow a_{ji} \neq 0$

Is there a class of methods (iterative or direct) which can solve this class of problems efficiently?

If yes, then web-links to any implementations would also be very useful.

Answer 1

This is called "structurally symmetric". It simplifies graph traversal, such as occurs when setting up aggregates in algebraic multigrid, but doesn't offer much structure to improve convergence rates. Note that all common PDE discretizations have this property so this is still a huge class of matrices including many instances for which no truly good iterative solver is known.

Answer 2

The sparsity sparsity structure helps only in avoiding repeating the fill reducing reordering heuristic and symbolic factorization step for each iteration. Two points to take note of are:

1. These are graph processing (read pointer jumping or List Processing) intensive which results in low cash hit ratio, and not that easily parallelizable.

2. Memory requirements tend to be far lower in the reordering phase. There are ways to reduce the memory footprint during the symbolic factoring phase.

In essence, sometimes it is best to run these two phases sequentially or on a small number of cores (4 or 8) in an SMP mode.