Semiring induced valuation algebras: Exact and approximate local computation algorithms

Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra.There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.

Dimension theory and nonstable K1 of quadratic modules

Employing Bak’s dimension theory, we investigate the nonstable quadratic K-group K1,2n(A, ) = G2n(A, )/E2n(A, ), n 3, where G2n(A, ) denotes the general quadratic group of rank n over a form ring (A, ) and E2n(A, ) its elementary subgroup. Considering form rings as a category with dimension in the sense of Bak, we obtain a dimension filtration G2n(A, ) G2n0(A, ) G2n1(A, ) E2n(A, ) of the general quadratic group G2n(A, ) such that G2n(A, )/G2n0(A, ) is Abelian, G2n0(A, ) G2n1(A, ) is a descending central series, and G2nd(A)(A, ) = E2n(A, ) whenever d(A) = (Bass–Serre dimension of A) is finite. In particular K1,2n(A, ) is solvable when d(A) <.

Algorithmic computation of knot polynomials of secondary structure elements of proteins

The classification of protein structures is an important and still outstanding problem. The purpose of this paper is threefold. First, we utilize a relation between the Tutte and homfly polynomial to show that the Alexander-Conway polynomial can be algorithmically computed for a given planar graph. Second, as special cases of planar graphs, we use polymer graphs of protein structures. More precisely, we use three building blocks of the three-dimensional protein structure-alpha-helix, antiparallel beta-sheet, and parallel beta-sheet-and calculate, for their corresponding polymer graphs, the Tutte polynomials analytically by providing recurrence equations for all three secondary structure elements. Third, we present numerical results comparing the results from our analytical calculations with the numerical results of our algorithm-not only to test consistency, but also to demonstrate that all assigned polynomials are unique labels of the secondary structure elements. This paves the way for an automatic classification of protein structures.

Comparing the implementation of two-dimensional numerical quadrature on GPU, FPGA and ClearSpeed systems to study electron scattering by atoms

The use of accelerators, with compute architectures different and distinct from the CPU, has become a new research frontier in high-performance computing over the past ?ve years. This paper is a case study on how the instruction-level parallelism offered by three accelerator technologies, FPGA, GPU and ClearSpeed, can be exploited in atomic physics. The algorithm studied is the evaluation of two electron integrals, using direct numerical quadrature, a task that arises in the study of intermediate energy electron scattering by hydrogen atoms. The results of our ‘productivity’ study show that while each accelerator is viable, there are considerable differences in the implementation strategies that must be followed on each.

Models of open populations with space-limited recruitment: extension of theory and application to the barnacle Chthamalus montagui.

1. Barnacles are a good model organism for the study of open populations with space-limited recruitment. These models are applicable to other species with open supply of new individuals and resource limitation. The inclusion of space in models leads to reductions in recruitment with increasing density, and thus predictions of population size and stability are possible. 2. Despite the potential generality of a demographic theory for open space-limited populations, the models currently have a narrow empirical base. In this study, a model for an open population with space-limited recruitment was extended to include size-specific survival and promotions to any size class. The assumptions of this model were tested using data from a pan-European study of the barnacle Chthamalus montagui Southward. Two models were constructed: a 6-month model and a periodic annual model. Predicted equilibria and their stabilities were compared between shores. 3. Tests of model assumptions supported the extension of the theory to include promotions to any size class. Mortality was found to be size-specific and density independent. Studied populations were open, with recruitment proportional to free space. 4. The 6-month model showed a significant interaction between time and location for equilibrium free space. This may have been due to contrasts in the timing of structuring processes (i.e. creating and filling space) between Mediterranean and Atlantic systems. Integration of the 6-month models into a periodic annual model removed the differences in equilibrium-free space between locations. 5. Model predictions show a remarkable similarity between shores at a European scale. Populations were persistent and all solutions were stable. This reflects the apparent absence of density-dependent mortality and a high adult survivorship in C. montagui. As populations are intrinsically stable, observations of fluctuations in density are directly attributable to variations in the environmental forcing of recruitment or mortality