Theoretical Computer Science
reference-request graph-algorithms matrices sparse-matrix
Updated Fri, 27 May 2022 01:25:29 GMT

Reducing the bandwidth of non-symmetric matrix


Is there an efficient algorithm to reduce the bandwidth of a directed graph's adjacency matrix? Something like the reverse Cuthill-McKee, but for non-symmetric matrices.

Solution

The following article discusses various approaches to reducing the bandwidth of unsymmetric matrices.

J.K. Reid, J. A. Scott: Reducing the total bandwidth of a sparse unsymmetric matrix, SIAM Journal on Matrix Analysis and Applications 28(3):805–821.

The technical report version of the article is available here:

J. K. Reid and J. A. Scott, Reducing the total bandwidth of a sparse unsymmetric matrix, Technical Report RAL-TR-2005-001, STFC Rutherford Appleton Laboratory. http://www.numerical.rl.ac.uk/reports/rsRAL2005001.pdf

Comments (2)

  • +1 – Whoops, thanks for the edit! And for the answer, that seems to be exactly what I'm looking for :) — May 26, 2014 at 10:42  
  • +0 – You're welcome! I'm glad that you found the answer useful. — Jun 08, 2014 at 11:57  

External Links

External links referenced by this document:

References