Qun Wang

"Reducibility and Flows on Feynman Diagrams"

Abstract:

A Feynman diagram of order n is a rooted mixed graph on 2n vertices consisting of a perfect matching of undirected edges (called V-lines) and a permutation formed by directed edges (call G-lines). A Feynman diagram is irreducible if and only if it is connected and can't be disconnected into two disjoint components by removing two G-lines. Three algorithms to test the reducibility of Feynman diagrams were implemented and tested. The three algorithms implemented are called "quadratic", "pseudolinear" and "randomized". Conservative flows are constructed in order to test for reducibility in all three algorithms. For a Feynman diagram with order n, the quadratic algorithms takes expected time O(n^2). The pseudolinear algorithm effectively takes expected time O(n) for the order up to 63, but the expected time is O(n^2) for arbitrarily higher orders. The randomized algorithm takes expected time O(n log n) for diagrams of any order, but is effectively linear for n <= 215. Testing was done on Feynman diagrams of various orders. Timing results are reported and analyzed. For order less than 23, the quadratic and pseudolinear algorithms run faster than the randomized algorithm because of the overhead of checking true cut-pairs for the latter approach. And for larger n, the randomized algorithm becomes much faster than the other two approaches. The pseudolinear algorithm runs faster than the quadratic algorithm due to its smaller constant factor, even for higher order diagrams.