Open boschmitt opened 3 years ago
This change does not work for the general coupling constraint graph. (It works for a line though.)
The trick I used to compute both sides of the diagonal at the same time, allowed me to not have to worry about removing vertices from the coupling graph.
On the other hand, the papers that describe similar techniques need to update the coupling graph after processing each column. Indeed, they need to remove the vertex corresponding to the column it just processed. (This is to ensure that the processing of subsequent columns don't screw up previous ones---which can happen if a subsequent stainer tree uses the vertex of a previous column as a stainer node.) The problem with this behaviour is that after each column is processed, we will have a new, more constrained, coupling graph which need to be analysed to find shortest paths between vertices. (Potentially an expensive price to pay, especially when using this technique for resynthesis.)
Description
When doing gaussian elimination, I was using a trick to solve both the upper and lower triangle of the matrix at the same time. (I picked the trick up on the staq codebase.) It turns out this was not a good idea because it lead to subpar results.
Previously this produced a circuit of size
100
and depth80
.Not it produces a circuit of size
64
and depth54
.Furthermore, when synthesizing circuits to compute all possible permutations on a path of 8 vertices. It used to find that this algorithm was only better than a swap-based method in 1271 out of 40319 permutations (roughly 3.15%). Now it finds better results for 5028 (12.47%).
It also "solves" the examples in #157