8
$\begingroup$

Pretty much the question. Given a general sparse, non-symmetric (both numerically and structurally) matrix, how important is the sparsity pattern (i.e. row/column permutation of matrix/vector) for iterative solvers? I can see it becomes important for direct solvers (LU) or preconditioners (ILU) by directly affecting the number of fill-ins.

For iterative solvers, however, it seems that the most important part is the MatVec operation which does not seem to care about the actual matrix pattern. Is there some component that could be depended on the pattern that I'm not considering here?

How about in parallel? I suspect the pattern could become important in the way the matrix and vectors are distributed and thus determines the communication volume/overhead but would like to see other thoughts and inputs.

I'm asking this both in general and also regarding PETSc's KSP solvers.

$\endgroup$
  • 1
    $\begingroup$ There should only be a problem in parallel if you have a very large number of nonzeros in a row or column. An arrowhead matrix is a nice example of such a case (a diagonal matrix plus a dense last row and column). $\endgroup$ – Jack Poulson Jun 5 '12 at 19:37
  • $\begingroup$ Is "sparsity pattern" the correct word here? afaik, you ask about the ordering of the matrix entries, while the term "sparsity pattern" refers to, say, diagonal, tridiagonal, block-diagonal, etc. $\endgroup$ – shuhalo Jun 6 '12 at 4:35
  • $\begingroup$ @Martin Note that a property like "tridiagonal" is still dependent on the ordering. Think of a 1D problem in random ordering, for example. $\endgroup$ – Jed Brown Jun 6 '12 at 11:17
6
$\begingroup$

Ordering is only significant in load balance/communication and suitability for preconditioning. The Krylov method does not care about the order or even whether the matrix entries are stored.

In practice, a bad ordering may require much more communication than otherwise necessary when multiplying by a matrix. See the section of the PETSc User's Manual on "Natural ordering" versus "PETSc ordering" for an example. Additionally, an ordering corresponding to a bad parallel partition might make domain decomposition preconditioners less effective. Note that it is the partition that matters here, though a partition induces an (equivalence class of) orderings.

$\endgroup$

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.