Suppose I have a sparse $M \times N$ matrix $A$ and I define the "width" of each row $i$ to be:

$$w_i \equiv r(A_i) - l(A_i),$$ where $r(A_i)$ is the index of the rightmost nonzero element of row $i$ of $A$, and $l(A_i)$ is the index of the leftmost nonzero element of row $i$ of $A$.

I want to find a permutation of the columns of $A$ such that $W = \frac{1}{M} \sum_{i = 1}^M w_i$ is minimized. I know there are algorithms that deal with the bandwidth, but that deals with both the rows and columns of $A$. Is there any work on dealing with just the width (sometimes called the profile)?

  • $\begingroup$ This doesn't answer directly your question, because it doesn't aim at minimizing the width as you define it, but it seems related to the notion of graph compression and precisely node reindexing for graph compression. In this paper: arxiv.org/pdf/1602.08820.pdf the authors optimize a related quantity. Maybe that may help. $\endgroup$
    – Alt-Tab
    May 13, 2023 at 9:04


Your Answer

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