I'm interested in the following problem: given $M$, a $p \times p $ symmetric sparse matrix (the number of non-zero elements in each row is at most $s \ll p$), find a matrix $B = PMP^T$ where $P$ is a permutation matrix such that $B$ is banded.

The algorithm that solves this problem is Cuthill-McKee. What I am struggling to find though is: are there guarantees on the bandwidth of the matrix $B$? That is, can we say that after running the Cuthill-McKee algorithm we can be sure to obtain a matrix $B$ with bandwidth $b$ ? If so, what is $b$ as a function of $s$?



Your Answer

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