Feynman graph generation and calculations in the Hopf algebra of Feynman graphs

Two programs for the computation of perturbative expansions of quantum field theory amplitudes are provided. feyngen can be used to generate Feynman graphs for Yang–Mills, QED and φ^k${\phi }^k$ theories. Using dedicated graph theoretic tools feyngen can generate graphs of comparatively high loop orders. feyncop implements the Hopf algebra of those Feynman graphs which incorporates the renormalization procedure necessary to calculate finite results in perturbation theory of the underlying quantum field theory. feyngen is validated by comparison to explicit calculations of zero dimensional quantum field theories and feyncop is validated using a combinatorial identity on the Hopf algebra of graphs.     

The implementation of the renormalized complex MSSM in FeynArts and FormCalc

We describe the implementation of the renormalized complex MSSM (cMSSM) in the diagram generator FeynArts and the calculational tool FormCalc. This extension allows to perform UV-finite one-loop calculations of cMSSM processes almost fully automatically. The Feynman rules for the cMSSM with counterterms are available as a new model file for FeynArts. Also included are default definitions of the renormalization constants; this fixes the renormalization scheme. Beyond that all model parameters are generic, e.g. we do not impose any relations to restrict the number of input parameters. The model file has been tested extensively for several non-trivial decays and scattering reactions. Our renormalization scheme has been shown to give stable results over large parts of the cMSSM parameter space.     

Symbolic expansion of transcendental functions

Higher transcendental function occur frequently in the calculation of Feynman integrals in quantum field theory. Their expansion in a small parameter is a non-trivial task. We report on a computer program which allows the systematic expansion of certain classes of functions. The algorithms are based on the Hopf algebra of nested sums. The program is written in C++ and uses the GiNaC library.     

Clifford and Graßmann Hopf algebras via the BIGEBRA package for Maple

Hopf algebraic structures will replace groups and group representations as the leading paradigm in forthcoming times. K-theory, co-homology, entanglement, statistics, representation categories, quantized or twisted structures as well as more geometric topics of invariant theory, e.g., the Graßmann-Cayley bracket algebra, are all covered by the Hopf algebraic framework. The new branch of experimental mathematics allows one to easily enter these fields through direct calculations using symbolic manipulation and computer algebra system (CAS). We discuss problems which were solved when building the BIGEBRA package for Maple and CLIFFORD to handle tensor products, Graßmann and Clifford algebras, coalgebras and Hopf algebras. Recent results showing the usefulness of CAS for investigating new and involved mathematics provide us with examples. An outlook on further developments is given.     

Simplicial powers of graphs

In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer k≥1, a graph G=(V_G,E_G) is the k-simplicial power of a graph H=(V_H,E_H) (H a root graph of G) if V_G is the set of all simplicial vertices of H, and for all distinct vertices x and y in V_G, xyE_G if and only if the distance in H between x and y is at most k. This concept generalizes k-leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. Recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For k≤5, k-leaf powers can be recognized in linear time, and for k≤4, structural characterizations are known. For k≥6, the recognition and characterization problems of k-leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs.     

Divide and Congruence Applied to η-Bisimulation

We present congruence formats for η- and rooted η-bisimulation equivalence. These formats are derived using a method for decomposing modal formulas in process algebra. To decide whether a process algebra term satisfies a modal formula, one can check whether its subterms satisfy formulas that are obtained by decomposing the original formula. The decomposition uses the structural operational semantics that underlies the process algebra.     

Bonsai: A compact representation of trees

This paper shows how trees can be stored in a very compact form, called ‘Bonsai’, using hash tables. A method is described that is suitable for large trees that grow monotonically within a predefined maximum size limit. Using it, pointers in any tree can be represented within 6 + [log₂n] bits per node where n is the maximum number of children a node can have. We first describe a general way of storing trees in hash tables, and then introduce the idea of compact hashing which underlies the Bonsai structure. These two techniques are combined to give a compact representation of trees, and a practical methodology is set out to permit the design of these structures. The new representation is compared with two conventional tree implementations in terms of the storage required per node. Examples of programs that must store large trees within a strict maximum size include those that operate on trie structures derived from natural language text. We describe how the Bonsai technique has been applied to the trees that arise in text compression and adaptive prediction, and include a discussion of the design parameters that work well in practice.     

Simpson's rule of discretized Feynman path integration

We suggest a Simpson's rule for discretized Feynman path integral approximation of density matrix element. For a class of bounded below potential functions, we rigorously establish the error boundO(1/N ²) for itsN-step discretized representation. As a model, we use harmonic oscillator to compare the Simpson's rule with the conventional trapezoidal rule.     

The H∞ control problem using static output feedback

In this paper we shall consider the H_∞ control problem using static output feedback. The approach uses some recent results from linear algebra. The main result shows that the H_∞ control problem is solvable by a static output feedback controller if and only if there exists a positive definite matrix satisfying two certain quadratic matrix inequalities. A parametrization of all static output feedback H_∞ controllers is given.     

LanHEP—a package for the automatic generation of Feynman rules in field theory. Version 3.0

The LanHEP program version 3.0 for Feynman rules generation from the Lagrangian is described. It reads the Lagrangian written in a compact form, close to the one used in publications. It means that Lagrangian terms can be written with summation over indices of broken symmetries and using special symbols for complicated expressions, such as covariant derivative and strength tensor for gauge fields. Supersymmetric theories can be described using the superpotential formalism and the 2-component fermion notation. The output is Feynman rules in terms of physical fields and independent parameters in the form of CompHEP model files, which allows one to start calculations of processes in the new physical model. Alternatively, Feynman rules can be generated in FeynArts format or as LaTeX table. One-loop counterterms can be generated in FeynArts format.

Program summary

Program title: LanHEPCatalogue identifier: ADZV_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AECH_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 83 041No. of bytes in distributed program, including test data, etc.: 1 090 931Distribution format: tar.gzProgramming language: CComputer: PCOperating system: LinuxRAM: 2 MB (SM), 12 MB (MSSM), 120 MB (MSSM with counterterms)Classification: 4.4Nature of problem: Deriving Feynman rules from the LagrangianSolution method: The program reads the Lagrangian written in a compact form, close to the one used in publications. It means that Lagrangian terms can be written with summation over indices of broken symmetries and using special symbols for complicated expressions, such as covariant derivative and strength tensor for gauge fields. Tools for checking the correctness of the model, and for simplifying the output expressions are provided. The output is Feynman rules in terms of physical fields and independent parameters in the form of CompHEP model files, which allows one to start calculations of processes in the new physical model. Alternatively, Feynman rules can be generated in FeynArts format or as a LaTeX table.Running time: 1 sec (SM), 8 sec (MSSM), 8 min (MSSM with counterterms)     

<Emphasis Type="Italic">H</Emphasis> <Subscript>2</Subscript>-optimization of sampled-data systems with a linear periodic plant. I. Parametric transfer matrix and its properties

This paper suggests a solution procedure of the H₂-optimization problem for a sampled-data system with a periodic continuous plant and a sampled-data element whose sampling period coincides with the period of the plant. The procedure employs the concept of the parametric transfer matrix and the Wiener–Hopf method based on factorization and separation of rational matrices.     

Decomposition and stability of linear systems with multiplicative noise

This paper concerns a representation of solutions and the stability of linear systems with multiplicative white noise, which is described by a vector Ito stochastic differential equation. The solution can be represented as a finite product of exponential matrices if Lie algebra generated by system matrices is solvable. If Lie algebra is not solvable, it is shown by the decomposition principle of Lie algebra that the problem of solving an equation can be reduced to the problem of solving a set of equations, whose corresponding Lie algebra is simple. Noting the structure of the sample solution, we present a technique of obtaining asymptotic stability conditions of sample solutions w.p.1, in the pth-order moment and in the pth-mean moment. The necessary and/or sufficient conditions of stability in some stochastic sense are obtained under certain conditions.     

Discrete time convolution control systems

In this paper, we study a general class of linear time invariant discrete time distributed systems. We consider both single-input-single-output (SISO) and multi-input-multi-output (MIMO) systems, and study design procedures. We develop a commutative algebra of transfer function, b(p₀), for a general class of SISO discrete time convolution systems, which covers sampled distributed systems and, of course, lumped systems as a special case. Each element of b(p₀) is formulated as a ratio of two elements in an algebra l₁?(p₀) of causal p₀-stable transfer functions. We demonstrate that l₁?(p₀) indeed a euclidean ring, give necessary and sufficient conditions for coprimeness between elements in l₁?(p₀) and characterize poles and zeros for elements in b(p₀). In contrast to the algebra l₁ the algebra b(p₀) includes both stable and unstable systems; furthermore since p₀<1 this formulation allows us to study the dominant poles inside the unit disc of the complex plane. We study next MIMO systems whose transfer functions are matrices with elements in b(p₀). We establish the matrix fraction representation theory and use it to develop : the dynamic interpretation of poles and transmission zeros, the feedback interconnection of such MIMO systems, and the problem of controller design to achieve stabilization (analogous to arbitrary closed-loop eigenvalue assignment), asymptotic tracking and disturbance rejection ; finally, for the case of stable square plants, we show how to achieve complete decoupling with detailed pole assignment and finite settling time, subject to, of course, the limitations imposed by the plant transmission zeros outside the open unit disc.     

Labeling schemes for weighted dynamic trees

A Distance labeling scheme is a type of localized network representation in which short labels are assigned to the vertices, allowing one to infer the distance between any two vertices directly from their labels, without using any additional information sources. As most applications for network representations in general, and distance labeling schemes in particular, concern large and dynamically changing networks, it is of interest to focus on distributed dynamic labeling schemes. The paper considers dynamic weighted trees where the vertices of the trees are fixed but the (positive integral) weights of the edges may change. The two models considered are the edge-dynamic model, where from time to time some edge changes its weight by a fixed quanta, and the increasing-dynamic model in which edge weights can only grow. The paper presents distributed approximate distance labeling schemes for the two dynamic models, which are efficient in terms of the required label size and communication complexity involved in updating the labels following the weight changes.     

A robust model for finding optimal evolutionary trees

Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species, and seeks to find an edge-weighted treeT in which the distanced _ij ^T in the tree between the leaves ofT corresponding to the speciesi andj exactly equals the observed distance,d _ij . When such a tree exists, this is expressed in the biological literature by saying that the distance function or matrix isadditive, and trees can be constructed from additive distance matrices in0(n ²) time. Real distance data is hardly ever additive, and we therefore need ways of modeling the problem of finding the best-fit tree as an optimization problem.In this paper we present several natural and realistic ways of modeling the inaccuracies in the distance data. In one model we assume that we have upper and lower bounds for the distances between pairs of species and try to find an additive distance matrix between these bounds. In a second model we are given a partial matrix and asked to find if we can fill in the unspecified entries in order to make the entire matrix additive. For both of these models we also consider a more restrictive problem of finding a matrix that fits a tree which is not only additive but alsoultrametric. Ultrametric matrices correspond to trees which can be rooted so that the distance from the root to any leaf is the same. Ultrametric matrices are desirable in biology since the edge weights then indicate evolutionary time. We give polynomial-time algorithms for some of the problems while showing others to be NP-complete. We also consider various ways of fitting a given distance matrix (or a pair of upper- and lower-bound matrices) to a tree in order to minimize various criteria of error in the fit. For most criteria this optimization problem turns out to be NP-hard, while we do get polynomial-time algorithms for some.Supported by DIMACS under NSF Contract STC-88-09648.Supported by NSF Grant CCR-9108969.This work was begun while this author was visiting DIMACS in July and August 1992, and was supported in part by the U.S. Department of Energy under Contract DE-AC04-76DP00789.     

A comment on ‘ self-tuning pole/zero assignment regulators’

The generalized H ₂ optimal control problem for a linear time-invariant system is one in which the conventional H ₂ norm is replaced by an operator norm. The closed-loop system is described in terms of a mapping between the space of time-domain input disturbances in L ₂ and the space of time-domain regulated outputs in L _∞. A minimum of this norm is then sought over all stabilizing controllers. It is shown that optimal controllers for such problems have the structure of a Kalman filter with estimated state feedback, where the feedback gains are obtained from the solution to a weighted LQR problem. A computational algorithm is presented to determine the weights in this LQR problem, and examples are given which demonstrate various problems which may arise in obtaining the optimal weights. In particular, it is shown that the generalized H ₂ problem may involve the solution to a singular LQR problem.     

Additive weights under the Balanced Probability Model

We compute the average behaviour of additive weights over the family ? _t (n) of unlabelled rooted planart-ary trees withn nodes under the so-calledBalanced Probability Model, introduced by R. Casas, J. Díaz and C. Martínez. The generating function related to a particular additive weight with polynomial weight functions always satisfies an ordinary inhomogeneous differential equation, which can be solved explicitly by thevariation of constant — method. These coefficients are estimated using singularity analysis. The so-calledoccupancy, a parameter which is analyzed in the paper of Casaset al., turns out to be additive, hence, the methods presented here are applicable to it.     

Symbolic evaluation of dimensionally regularized Feynman diagrams

A modification of the symbolic and algebraic manipulation program REDUCE is reported which allows the treatment of vector and gamma algebra in an arbitrary number of dimensions. The number of dimensions serves as a cut-off for divergences in the Feynman diagrams one has to evaluate in a theory like quantum gravity.     

Random feature weights for decision tree ensemble construction

This paper proposes a method for constructing ensembles of decision trees, random feature weights (RFW). The method is similar to Random Forest, they are methods that introduce randomness in the construction method of the decision trees. In Random Forest only a random subset of attributes are considered for each node, but RFW considers all of them. The source of randomness is a weight associated with each attribute. All the nodes in a tree use the same set of random weights but different from the set of weights in other trees. So, the importance given to the attributes will be different in each tree and that will differentiate their construction. The method is compared to Bagging, Random Forest, Random-Subspaces, AdaBoost and MultiBoost, obtaining favourable results for the proposed method, especially when using noisy data sets. RFW can be combined with these methods. Generally, the combination of RFW with other method produces better results than the combined methods. Kappa-error diagrams and Kappa-error movement diagrams are used to analyse the relationship between the accuracies of the base classifiers and their diversity.