| Safe Haskell | None |
|---|---|
| Language | GHC2024 |
Proarrow.Tools.ContractionOrder
Description
The order to contract a network of factors in, such as a tensor network or the states of an open hypergraph: which two to contract first, then which two of the factors and results, and so on. Contracting two factors makes a factor on the nodes of both that something else still needs, so its size depends on the order, and a bad order can make the intermediate results far larger than the network itself.
planContraction makes two plans and takes the one whose contractions are smaller together:
numpy's greedy order, and an elimination order of the nodes from the min-fill heuristic for tree
decompositions, as in Peterseim and Lopuhaä-Zwakenberg, /Fixed-Parameter Tractable Inference for
Discrete Probabilistic Programs, via String Diagram Algebraisation/ (LICS 2026).
Documentation
A plan to contract factors: one of them, by its place in the list, or the contraction of the results of two plans.
planContraction :: Ord n => (Set n -> Double) -> (n -> Bool) -> Set n -> [Set n] -> [Plan] Source Github #
Plans to contract the given factors, each given by its nodes, until no two of the results share a node that may be contracted: a plan for each result. A result keeps the nodes that the given set needs or that factors outside it touch, and its size is the size of those nodes. Of numpy's greedy order, which contracts the pair that shares such a node and whose result grows least, its size less those of the two parts, and of the min-fill elimination order of those nodes, which contracts the parts on each node in turn, the pair that grows least first, the plan whose contractions are smaller together is taken.
>>>planContraction (fromIntegral . length) (const True) mempty [Set.fromList "ab", Set.fromList "bc", Set.fromList "cd"][Contract (Contract (Factor 0) (Factor 1)) (Factor 2)]
minFillOrder :: (Ord a, Ord w) => ([a] -> w) -> [[a]] -> [a] -> [a] Source Github #
An order to eliminate the given vertices of a graph in, by the min-fill heuristic for tree decompositions. The graph has an edge between any two vertices of a common clique. Eliminating a vertex joins its neighbours, so the next vertex is the one whose neighbours lack the fewest edges among themselves, and of those the one whose neighbours weigh least together. A star is eliminated from its leaves:
>>>minFillOrder length [[0, 1], [0, 2], [0, 3 :: Int]] [0, 1, 2, 3][1,2,0,3]