I have been reading on different techniques used to reorder sparse matrices to achieve better performance, the most popular being the Cuthill-McKee or Reverse Cuthill-McKee algorithm. Most of those techniques focus on reducing the bandwidth of the matrix, which is defined as the furthest distance of a non-zero entry from the main diagonal.
If I understand correctly, the reordering algorithm optimizations are purely computational: the goal is to come up with a storage of the matrix more adequate for caching effects. Is this true or does the reordering affect the convergence/accuracy of the iterative algorithm?
Also, why do people mostly focus on the matrix bandwidth and not for example at the average bandwidth of each matrix row? If most of the points are located next to the diagonal except for 1, the matrix bandwidth will still be high but the performance should be nearly optimal (assuming matrix size n >> 1).
METIS_NodeND
, described as "fill reducing orderings of sparse matrices using the multilevel nested dissection algorithm". I use the parallel Intel MKL library for sparse matrix-vector products (mkl_sparse_?_mv
), so you could say the bottleneck of my conjugate gradient solver is parallelized. $\endgroup$