Bandwidth minimization

[mtfishman]

Add functionality for reordering the vertices of a tensor network/graph to minimize the graph bandwidth.

It appears that a popular algorithm for this is the Cuthill-McKee algorithm. There is a discussion of Julia implementations on Julia Discourse. Some Julia implementations are:

• SymRCM.jl.
• CuthillMcKee.jl.
• NodeNumbering.jl, with a tutorial here.
• AMD.jl.

This may be relevant for finding an MPS ordering for a graph of Hamiltonian interactions or mutual information that may be beneficial for entanglement (@JoeyT1994 is this what you use for your dense-graph DMRG calculations?), or finding an MPS embedding of a more general graph if you are looking to approximate a general tensor network as an MPS (though @LinjianMa has a more specialized algorithm for that in #11 which takes into account a tensor network the resulting MPS might contract with in order to try to minimize future swapping, which would be good to split off into a separate function).

It also may be relevant for finding network layouts for tensor networks/graphs that are known to be linear or have some linear structure.

Finally, this problem appears to be related to the minimum linear arrangement (MinLA) problem, which is known to be NP-hard. See:

• https://lipn.univ-paris13.fr/Lagos2017/talks/castro.pdf
• https://www.sciencedirect.com/science/article/abs/pii/S0196677404001531
• https://d-nb.info/1002005167/34

which is a special 1D case of the more general grid arrangement problem:

• https://www.sciencedirect.com/science/article/pii/S157252861200045X

which could be relevant for visualizing hypercubic-like tensor networks and also automatically approximating tensor networks as PEPS networks (say for a generalized boundary PEPS algorithm for contracting cube-like graphs).

[JoeyT1994]

I was using the CurhillMcKee.jl package for some adjacency matrix reordering and this was working very straightforwardly so can recommend that.

I did, however, find cases where the re-ordering found by Cuthill-McKee performed worse in DMRG than just a randomly chosen one. I think the reason for this is that it uses the standard definition of bandwidth (distance of the furthest non-zero element from the diagonal) which is a bit naive when thinking about MPS ordering. For instance, the periodic boundary 1D chain adjacency matrix has the largest bandwidth possible and so Cuthill-Mckee will perform a significant re-ordering of the sites and create an adjacency matrix with lots of long-range terms (instead of just one in the periodic case). DMRG will then perform a lot worse on such an adjacency matrix even though it might have a much lower bandwidth.

Ideally we might be able to introduce a variable definition of bandwidth via some `cost-function' and then minimise over that. For instance, I think the cost-function $C(A) = \sum_{i,j} \vert A_{ij} \vert |i - j|^{\eta}$ where $\eta > 1$ is quite a popular choice for some matrix A with elements $A_{i,j}$.

[mtfishman]

Also relevant is: https://github.com/cameton/LinearOrdering.jl with the associated reference https://arxiv.org/abs/2209.02895.