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.

Improve this question
$\endgroup$
3
  • 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, 2012 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, 2012 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, 2012 at 11:17

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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