Uniform solutions to SAT and Subset Sum by spiking neural P systems

We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this respect: Subset Sum{\tt Subset}\,{\tt Sum} and SAT.{\tt SAT}. For both of them we provide uniform constructions of standard spiking neural P systems (i.e., not using extended rules or parallel use of rules) which solve these problems in a constant number of steps, working in a non-deterministic way. This improves known results of this type where the construction was non-uniform, and/or was using various ingredients added to the initial definition of spiking neural P systems (the SN P systems as defined initially are called here “standard”). However, in the Subset Sum{\tt Subset}\,{\tt Sum} case, a price to pay for this improvement is that the solution is obtained either in a time which depends on the value of the numbers involved in the problem, or by using a system whose size depends on the same values, or again by using complicated regular expressions. A uniform solution to 3-SAT{\tt SAT} is also provided, that works in constant time.     

Optimizing server placement in distributed systems in the presence of competition

Although the problem of data server placement in parallel and distributed systems has been studied extensively, most of the existing work assumes there is no competition between servers. Hence, their goal is to minimize read, update and storage cost. In this paper, we study the server placement problem in which a new server has to compete with existing servers for user requests. Therefore, in addition to minimizing cost, we also need to maximize the benefit of building a new server.Our major results include three parts. First, for tree-structured systems, we propose an O(|V|³k) time dynamic programming algorithm to find the optimal placement of k extra servers that maximizes the benefit in a tree with |V| nodes. We also propose an O(|V|³) time dynamic programming algorithm to find the optimal placement of extra servers that maximizes the benefit, without any constraint on the number of extra servers. Second, for general connected graphs, we prove that the server placement problems are NP-complete, and present three greedy heuristic algorithms, called Greedy Add, Greedy Remove and Greedy Add-Remove, to solve them. Third, we show that if the number of requests a server can handle (i.e., server capacity) is bounded, the server placement problem is NP-complete even for tree networks. We then derive a variation of the same set of greedy heuristic algorithms, with consideration of server capacity constraint, to solve the problem.Our experiment results demonstrate that the greedy algorithms achieve good results, when compared with the upper bounds found by a linear programming algorithm. Greedy Add performs best in the unconstrained model, yielding a benefit within 12% difference from the theoretical upper bound in average. For the constrained model, Greedy Remove performs best for smaller network sizes, while Greedy Add-Remove performs best for larger network sizes. On average, the heuristic algorithms yield a benefit within 13% difference from the theoretical upper bound in the constrained model.     

A PARALLEL DIVIDE AND CONQUER ALGORITHM FOR NON SYMMETRIC TRIDIAGONAL TOEPLITZ SYSTEMS USING CONJUGATE GRADIENT

Abstract

In this paper, we consider the application of the conjugate gradient method specifically to solve non symmetric systems which are large, tridiagonal and Toeplitz. Under the condition that the system is diagonally dominant, one can pre-multiply the system by the transpose of the coefficient matrix and take advantage of the structure of the new coefficient matrix to perturb and factor it. This allows us to divide the task of solution containing pairs of tridiagonal, symmetric and Toeplitz systems and to solve the pairs of systems using a parallel implementaton of congujate gradient. Final corrections, to account for the perturbations, provide a numerical approximation to the solution.     

DIRHB—A relativistic self-consistent mean-field framework for atomic nuclei

The DIRHB package consists of three Fortran computer codes for the calculation of the ground-state properties of even–even atomic nuclei using the framework of relativistic self-consistent mean-field models. Each code corresponds to a particular choice of spatial symmetry: the DIRHBS, DIRHBZ and DIRHBT codes are used to calculate nuclei with spherical symmetry, axially symmetric quadrupole deformation, and triaxial quadrupole shapes, respectively. Reflection symmetry is assumed in all three cases. The latest relativistic nuclear energy density functionals are implemented in the codes, thus enabling efficient and accurate calculations over the entire nuclide chart.     

Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.     

Open-Source Model Checking

We present GMC², a software model checker for GCC, the open-source compiler from the Free Software Foundation (FSF). GMC², which is part of the GMC static-analysis and model-checking tool suite for GCC under development at SUNY Stony Brook, can be seen as an extension of Monte Carlo model checking to the setting of concurrent, procedural programming languages. Monte Carlo model checking is a newly developed technique that utilizes the theory of geometric random variables, statistical hypothesis testing, and random sampling of lassos in Büchi automata to realize a one- sided error, randomized algorithm for LTL model checking. To handle the function call/return mechanisms inherent in procedural languages such as C/C++, the version of Monte Carlo model checking implemented in GMC² is optimized for pushdown-automaton models. Our experimental results demonstrate that this approach yields an efficient and scalable software model checker for GCC.     

An analysis of separable least squares data driven local coordinates for maximum likelihood estimation of linear systems

In this paper we study a novel parametrization for state-space systems, namely separable least squares data driven local coordinates (slsDDLC). The parametrization by slsDDLC has recently been successfully applied to maximum likelihood estimation of linear dynamic systems. In a simulation study, the use of slsDDLC has led to numerical advantages in comparison to the use of more conventional parametrizations, including data driven local coordinates (DDLC). However, an analysis of properties of slsDDLC, which are relevant to identification, has not been performed up to now. In this paper, we provide insights into the geometry and topology of the slsDDLC construction and show a number of results which are important for actual identification, in particular for maximum likelihood estimation. We also prove that the separable least squares methodology is indeed guaranteed to be applicable to maximum likelihood estimation of linear dynamic systems in typical situations.     

The tauola-photos-F environment for the TAUOLA and PHOTOS packages, release II

We present the system for maintaining the versions of two packages: the TAUOLA of τ-lepton decay and PHOTOS for radiative corrections in decays. The following features can be chosen in an automatic or semi-automatic way: (1) format of the common block HEPEVT; (2) version of the physics input (for TAUOLA): as published, as initialized by the CLEO collaboration, as initialized by the ALEPH collaboration (it is suggested to use this version only with the help of the collaboration advice), new optional parametrization of matrix elements in 4π decay channels; (3) type of application: stand-alone, universal interface based on the information stored in the HEPEVT common block including longitudinal spin effects in the elementary Z/γ^∗→τ⁺τ⁻ process, extended version of the standard universal interface including full spin effects in the H/A→τ⁺τ⁻ decay, interface for KKMC Monte Carlo, (4) random number generators; (5) compiler options. The last section of the paper contains documentation of the programs updates introduced over the last two years.

Program summary

Title of program:tauola-photos-F, release IICatalogue identifier:ADXO_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXO_v1_0Programs obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputer: PC running GNU/Linux operating systemProgramming languages and tools used:CPP: standard C-language preprocessor, GNU Make builder tool, also FORTRAN compilerNo. of lines in distributed program, including test data, etc.: 194 118No. of bytes in distributed program, including test data, etc.:2 481 234Distribution format: tar.gzCatalogue identifier:ADXO_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXO_v2_0No. of lines in distributed program, including test data, etc.:308 235No. of bytes in distributed program, including test data, etc.:2 988 363Distribution format:tar.gzDoes the new version supersede the previous version:YesNature of the physical problem: The code of Monte Carlo generators often has to be tuned to the needs of large HEP Collaborations and experiments. Usually, these modifications do not introduce important changes in the algorithm, but rather modify the initialization and form of the hadronic current in τ decays. The format of the event record (HEPEVT common block) used to exchange information between building blocks of Monte Carlo systems often needs modification. Thus, there is a need to maintain various, slightly modified versions of the same code. The package presented here allows the production of ready-to-compile versions of TAUOLA [S. Jadach, Z. Wa?s, R. Decker, J.H. Kühn, Comput. Phys. Comm. 76 (1993) 361; A.E. Bondar, et al., Comput. Phys. Comm. 146 (2002) 139] and PHOTOS [E. Barberio, Z. Wa?s, Comput. Phys. Comm. 79 (1994) 291] Monte Carlo generators with appropriate demonstration programs. The new algorithm, universal interface of TAUOLA to work with the HEPEVT common block, is also documented here. Finally, minor technical improvements of TAUOLA and PHOTOS are also listed.Method of solution: The standard UNIX tool: the C-language preprocessor is used to produce a ready-to-distribute version of TAUOLA and PHOTOS code. The final FORTRAN code is produced from the library of ‘pre-code’ that is included in the package.Reasons for new version: The functionality of the version of TAUOLA and PHOTOS changed over the last two years. The changes, and their reasons, are documented in Section 9, and our new papers cited in this section.Additional comments: The updated version includes new features described in Section 9 of the paper. PHOTOS and TAUOLA were first submitted to the library as separate programs. Summary details of these previous programs are obtainable from the CPC Program Library.Typical running time: Depends on the speed of the computer used and the demonstration program chosen. Typically a few seconds.     

From Varieties of Algebras to Covarieties of Coalgebras

Varieties of F-algebras with respect to an endofunctor F on an arbitrary cocomplete category C are defined as equational classes admitting free algebras. They are shown to correspond precisely to the monadic categories over C. Under suitable assumptions satisfied in particular by any endofunctor on Set and Set^op the Birkhoff Variety Theorem holds. By dualization, covarieties over complete categories C are introduced, which then correspond to the comonadic categories over C, and allow for a characterization in dual terms of the Birkhoff Variety Theorem. Moreover, the well known conditions of accessibilitly and boundedness for Set-functors F, sufficient for the existence of cofree F-coalgebras, are shown to be equivalent.     

MRx as a performative and theatrical stage

Abstract

This article provides one component of a new interdisciplinary, humanities-based framework for MR^x design and criticism along with Engberg and Bolter's article, “MR^x and the Aesthetics of Locative Writing and JafariNaimi's article, “MR^x as a Participatory Platform. As defined in the introductory article for this series, MR^x experiences are conceptualised as site-specific; hybrid; and aesthetic, performative and/or social. This article develops a performance studies and theatre history perspective on MR^x. By outlining historical examples relevant to contemporary MR^x practice, a set of best practices are derived. These strategies are conceptualised as central questions, which are then applied in the analysis of four examples of recent MR^x works, along with suggestions for how these strategies may be used during the design process.     

RNGSSELIB: Program library for random number generation, SSE2 realization

The library RNGSSELIB for random number generators (RNGs) based upon the SSE2 command set is presented. The library contains realization of a number of modern and most reliable generators. Usage of SSE2 command set allows to substantially improve performance of the generators. Three new RNG realizations are also constructed. We present detailed analysis of the speed depending on compiler usage and associated optimization level, as well as results of extensive statistical testing for all generators using available test packages. Fast SSE implementations produce exactly the same output sequence as the original algorithms.

Program summary

Program title: RNGSSELIBCatalogue identifier: AEIT_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEIT_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.: 4177No. of bytes in distributed program, including test data, etc.: 21 228Distribution format: tar.gzProgramming language: C.Computer: PC.Operating system: UNIX, Windows.RAM: 1 MbytesClassification: 4.13.Nature of problem: Any calculation requiring uniform pseudorandom number generator, in particular, Monte Carlo calculations.Solution method: The library contains realization of a number of modern and reliable generators: mt19937, mrg32k3a and lfsr113. Also new realizations for the method based on parallel evolution of an ensemble of dynamical systems are constructed: GM19, GM31 and GM61. The library contains both usual realizations and realizations based on SSE command set. Usage of SSE commands allows the performance of all generators to be substantially improved.Restrictions: For SSE realizations of the generators, Intel or AMD CPU supporting SSE2 command set is required. In order to use the realization lfsr113sse, CPU must support SSE4 command set.Running time: Running time is of the order of 20 sec for generating 10⁹ pseudorandom numbers with a PC based on Intel Core i7-940 CPU. Running time is analysed in detail in Section 5 of the paper.     

Novosibirsk hadronic currents for τ→4π channels of τ decay library TAUOLA

The new parameterization of form factors developed for 4π channels of the τ lepton decay and based on Novosibirsk data on e⁺e⁻→4π has been coded in a form suitable for the TAUOLA Monte Carlo package. Comparison with results from TAUOLA using another parameterization, i.e. the CLEO version of 1998 is also included.     

TaylUR 3, a multivariate arbitrary-order automatic differentiation package for Fortran 95

This new version of TaylUR is based on a completely new core, which now is able to compute the numerical values of all of a complex-valued function's partial derivatives up to an arbitrary order, including mixed partial derivatives.

New version program summary

Program title: TaylURCatalogue identifier: ADXR_v3_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXR_v3_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GPLv2No. of lines in distributed program, including test data, etc.: 6750No. of bytes in distributed program, including test data, etc.: 19 162Distribution format: tar.gzProgramming language: Fortran 95Computer: Any computer with a conforming Fortran 95 compilerOperating system: Any system with a conforming Fortran 95 compilerClassification: 4.12, 4.14Catalogue identifier of previous version: ADXR_v2_0Journal reference of previous version: Comput. Phys. Comm. 176 (2007) 710Does the new version supersede the previous version?: YesNature of problem: Problems that require potentially high orders of partial derivatives with respect to several variables or derivatives of complex-valued functions, such as e.g. momentum or mass expansions of Feynman diagrams in perturbative QFT, and which previous versions of this TaylUR [1,2] cannot handle due to their lack of support for mixed partial derivatives.Solution method: Arithmetic operators and Fortran intrinsics are overloaded to act correctly on objects of a defined type taylor, which encodes a function along with its first few partial derivatives with respect to the user-defined independent variables. Derivatives of products and composite functions are computed using multivariate forms [3] of Leibniz's rule where ν=(ν₁,…,νd), , , Dνf=^∂|ν|f/(ν₁^∂x₁?νd^∂xd), and μ<ν iff either |μ|<|ν| or |μ|=|ν|,μ₁=ν₁,…,μk=νk,μk+1<νk+1 for some k∈{0,…,d−1}, and of Fàa di Bruno's formula where the sum is over , . An indexed storage system is used to store the higher-order derivative tensors in a one-dimensional array. The relevant indices (k₁,…,ks;λ₁,…,λs) and the weights occurring in the sums in Leibniz's and Fàa di Bruno's formula are precomputed at startup and stored in static arrays for later use.Reasons for new version: The earlier version lacked support for mixed partial derivatives, but a number of projects of interest required them.Summary of revisions: The internal representation of a taylor object has changed to a one-dimensional array which contains the partial derivatives in ascending order, and in lexicographic order of the corresponding multiindex within the same order. The necessary mappings between multiindices and indices into the taylor objects' internal array are computed at startup. To support the change to a genuinely multivariate taylor type, the DERIVATIVE function is now implemented via an interface that accepts both the older format derivative(f,mu,n) and also a new format derivative(f,mu(:))=Dμf that allows access to mixed partial derivatives. Another related extension to the functionality of the module is the HESSIAN function that returns the Hessian matrix of second derivatives of its argument. Since the calculation of all mixed partial derivatives can be very costly, and in many cases only some subset is actually needed, a masking facility has been added. Calling the subroutine DEACTIVATE_DERIVATIVE with a multiindex as an argument will deactivate the calculation of the partial derivative belonging to that multiindex, and of all partial derivatives it can feed into. Similarly, calling the subroutine ACTIVATE_DERIVATIVE will activate the calculation of the partial derivative belonging to its argument, and of all partial derivatives that can feed into it. Moreover, it is possible to turn off the computation of mixed derivatives altogether by setting Diagonal_taylors to .TRUE.. It should be noted that any change of Diagonal_taylors or Taylor_order invalidates all existing taylor objects. To aid the better integration of TaylUR into the HPSrc library [4], routines SET_DERIVATIVE and SET_ALL_DERIVATIVES are provided as a means of manually constructing a taylor object with given derivatives.Restrictions: Memory and CPU time constraints may restrict the number of variables and Taylor expansion order that can be achieved. Loss of numerical accuracy due to cancellation may become an issue at very high orders.Unusual features: These are the same as in previous versions, but are enumerated again here for clarity. The complex conjugation operation assumes all independent variables to be real. The functions REAL and AIMAG do not convert to real type, but return a result of type taylor (with the real/imaginary part of each derivative taken) instead. The user-defined functions VALUE, REALVALUE and IMAGVALUE, which return the value of a taylor object as a complex number, and the real and imaginary part of this value, respectively, as a real number are also provided. Fortran 95 intrinsics that are defined only for arguments of real type (ACOS, AINT, ANINT, ASIN, ATAN, ATAN2, CEILING, DIM, FLOOR, INT, LOG10, MAX, MAXLOC, MAXVAL, MIN, MINLOC, MINVAL, MOD, MODULO, NINT, SIGN) will silently take the real part of taylor-valued arguments unless the module variable Real_args_warn is set to .TRUE., in which case they will return a quiet NaN value (if supported by the compiler) when called with a taylor argument whose imaginary part exceeds the module variable Real_args_tol. In those cases where the derivative of a function becomes undefined at certain points (as for ABS, AINT, ANINT, MAX, MIN, MOD, and MODULO), while the value is well defined, the derivative fields will be filled with quiet NaN values (if supported by the compiler).Additional comments: This version of TaylUR is released under the second version of the GNU General Public License (GPLv2). Therefore anyone is free to use or modify the code for their own calculations. As part of the licensing, it is requested that any publications including results from the use of TaylUR or any modification derived from it cite Refs. [1,2] as well as this paper. Finally, users are also requested to communicate to the author details of such publications, as well as of any bugs found or of required or useful modifications made or desired by them.Running time: The running time of TaylUR operations grows rapidly with both the number of variables and the Taylor expansion order. Judicious use of the masking facility to drop unneeded higher derivatives can lead to significant accelerations, as can activation of the Diagonal_taylors variable whenever mixed partial derivatives are not needed.Acknowledgments: The author thanks Alistair Hart for helpful comments and suggestions. This work is supported by the Deutsche Forschungsgemeinschaft in the SFB/TR 09.References:

[1]

G.M. von Hippel, TaylUR, an arbitrary-order diagonal automatic differentiation package for Fortran 95, Comput. Phys. Comm. 174 (2006) 569.

[2]

G.M. von Hippel, New version announcement for TaylUR, an arbitrary-order diagonal automatic differentiation package for Fortran 95, Comput. Phys. Comm. 176 (2007) 710.

[3]

G.M. Constantine, T.H. Savits, A multivariate Faa di Bruno formula with applications, Trans. Amer. Math. Soc. 348 (2) (1996) 503.

[4]

A. Hart, G.M. von Hippel, R.R. Horgan, E.H. Müller, Automated generation of lattice QCD Feynman rules, Comput. Phys. Comm. 180 (2009) 2698, doi:10.1016/j.cpc.2009.04.021, arXiv:0904.0375.

     

An analysis of the parametrization by data driven local coordinates for multivariable linear systems

In this paper, we study a novel parametrization for state-space systems, namely data driven local coordinates (DDLC) which have recently been introduced and applied. Even though DDLC has meanwhile become the default parametrization used in the system identification toolbox of the software package MATLAB, an analysis of properties of DDLC, which are relevant to identification, has not been performed up to now. In this paper, we provide insights into the geometry and topology of the DDLC construction and show a number of results which are important for actual identification such as maximum likelihood-type estimation.     

Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services

The prevalence of dynamic-content web services, exemplified by search and online social networking, has motivated an increasingly wide web-facing front end. Horizontal scaling in the Cloud is favored for its elasticity, and distributed design of load balancers is highly desirable. Existing algorithms with a centralized design, such as Join-the-Shortest-Queue (JSQ), incur high communication overhead for distributed dispatchers.We propose a novel class of algorithms called Join-Idle-Queue (JIQ) for distributed load balancing in large systems. Unlike algorithms such as Power-of-Two, the JIQ algorithm incurs no communication overhead between the dispatchers and processors at job arrivals. We analyze the JIQ algorithm in the large system limit and find that it effectively results in a reduced system load, which produces 30-fold reduction in queueing overhead compared to Power-of-Two at medium to high load. An extension of the basic JIQ algorithm deals with very high loads using only local information of server load.     

Algebraic and geometric approximation of waves among obstacles

Complex phenomena, such as the wave propagation in a medium, are thought to require highly sophisticated machineries for understanding their mechanics. In this paper, two wave phenomena, diffraction and interference, are implemented using solid modeling operations. The geometric model for the waves from a source is a cone. A trimmed cone is the DIFFERENCE between a cone and the given boundary. The wave propagation is modelled by the UNION of the cones (or trimmed cones). The intellectual contribution of this paper is on the dynamics of interface evolution. It answers the question of how a symmetric wave in the near field becomes asymmetric in a field far from the source. The analytical contribution is on the algebraic and geometric structures. Seemingly complex phenomena can be modelled with set operations on simple geometry such as cones.     

Propagation algorithms for lexicographic ordering constraints

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O(n) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.