Remove double loop in J

[davidweichiang]

It can be changed into a single loop (thanks @darcey).

[ccshan]

Can I get more explanation?

[davidweichiang]

Currently J uses a double loop to compute $\prod_{i \in [n] \setminus {k}} weight(e_i)$ where $weight(e_i)$ is the sum-product of $e_i$'s label if nonterminal, or the weight of its factor if terminal. So it runs in O(|E|^2) time. But it can be reduced to O(|E|) time as follows:

• Number the edges $e_1, ..., e_n$
• For k = 0 to n, compute $\prod_{i=1,...,k} weight(e_i)$ in constant time
• For k = n downto 0, compute $\prod_{i=k,...,n} weight(e_i)$ in constant time
• For k = 1 to n, compute $\prod_{i \in [n] \setminus {k}} weight(e_i)$ in constant time

[davidweichiang]

Unfortunately this isn't the easiest fix, because the outer loop is in J (and J_log) but the inner loop is in sum_product_edges.

[ccshan]

Thanks, this helps. So to compute $\prod_{i=1,...,k} weight(e_i)$ for example, do you mean a loop like this instead of what sum_product_edges currently does?

• Initialize $A_0$ to the scalar-1 tensor
• For k=1 to n, compute $Ak = \prod{i=1,...,k} weight(ei)$ by einsum of $A{k-1}$ and $weight(e_k)$, keeping all nodes that appear in any $e_i$ where $i>k$ (as well as the original rule.rhs.ext)

Is the size of these intermediate tensors (affected by the edge numbering) a concern then?

[davidweichiang]

Right. I guess the ordering does matter, which is something we haven't thought about at all yet. People who work on tensor networks have thought about this a lot.