On the necessity of the invariance conditions for reach control on polytopes

We study the Reach Control Problem (RCP) to make the solutions of an affine system defined on a polytopic state space reach and exit a prescribed facet of the polytope in finite time without first leaving the polytope. So-called invariance conditions are used to prevent solutions from leaving the polytope through facets which are not designated as the exit facet. These conditions are known to be necessary for solvability of the RCP on polytopes by continuous state feedback. We study whether the invariance conditions are also necessary for solvability of the RCP on polytopes by open-loop controls. We show by way of a counterexample that surprisingly the answer is negative. We identify a suitable class of polytopes for which the invariance conditions remain necessary conditions.     

多面体上彷射系统可达性问题研究

研究n维多面体上自治仿射系统的可达性问题. 目的在于得到多面体上最大正不变集和每个极大面的反向可达集(吸引域). 研究最大稳定不变仿射子空间, 并给出不变集和吸引域的性质, 最后通过分割算法确定两者的边界.     

Effective lattice point counting in rational convex polytopes

This paper discusses algorithms and software for the enumeration of all lattice points inside a rational convex polytope: we describe LattE, a computer package for lattice point enumeration which contains the first implementation of A. Barvinok’s algorithm (Math. Oper. Res. 19 (1994) 769).We report on computational experiments with multiway contingency tables, knapsack type problems, rational polygons, and flow polytopes. We prove that these kinds of symbolic–algebraic ideas surpass the traditional branch-and-bound enumeration and in some instances LattE is the only software capable of counting. Using LattE, we have also computed new formulas of Ehrhart (quasi-)polynomials for interesting families of polytopes (hypersimplices, truncated cubes, etc).We end with a survey of other “algebraic–analytic” algorithms, including a “homogeneous” variation of Barvinok’s algorithm which is very fast when the number of facet-defining inequalities is much smaller compared to the number of vertices.     

Program package for multicanonical simulations of U(1) lattice gauge theory

We document our Fortran 77 code for multicanonical simulations of 4D U(1) lattice gauge theory in the neighborhood of its phase transition. This includes programs and routines for canonical simulations using biased Metropolis heatbath updating and overrelaxation, determination of multicanonical weights via a Wang-Landau recursion, and multicanonical simulations with fixed weights supplemented by overrelaxation sweeps. Measurements are performed for the action, Polyakov loops and some of their structure factors. Many features of the code transcend the particular application and are expected to be useful for other lattice gauge theory models as well as for systems in statistical physics.

Program summary

Program title: STMC_U1MUCACatalogue identifier: AEET_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEET_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.: 18 376No. of bytes in distributed program, including test data, etc.: 205 183Distribution format: tar.gzProgramming language: Fortran 77Computer: Any capable of compiling and executing Fortran codeOperating system: Any capable of compiling and executing Fortran codeClassification: 11.5Nature of problem: Efficient Markov chain Monte Carlo simulation of U(1) lattice gauge theory close to its phase transition. Measurements and analysis of the action per plaquette, the specific heat, Polyakov loops and their structure factors.Solution method: Multicanonical simulations with an initial Wang-Landau recursion to determine suitable weight factors. Reweighting to physical values using logarithmic coding and calculating jackknife error bars.Running time: The prepared tests runs took up to 74 minutes to execute on a 2 GHz PC.     

Polytope-based computation of polynomial ranges

Polynomial ranges are commonly used for numerically solving polynomial systems with interval Newton solvers. Often ranges are computed using the convex hull property of the tensorial Bernstein basis, which is exponential size in the number n of variables. In this paper, we consider methods to compute tight bounds for polynomials in n variables by solving two linear programming problems over a polytope. We formulate a polytope defined as the convex hull of the coefficients with respect to the tensorial Bernstein basis, and we formulate several polytopes based on the Bernstein polynomials of the domain. These Bernstein polytopes can be defined by a polynomial number of halfspaces. We give the number of vertices, the number of hyperfaces, and the volume of each polytope for n=1,2,3,4, and we compare the computed range widths for random n-variate polynomials for n?10. The Bernstein polytope of polynomial size gives only marginally worse range bounds compared to the range bounds obtained with the tensorial Bernstein basis of exponential size.     

STRINGVACUA. A Mathematica package for studying vacuum configurations in string phenomenology

We give a simple tutorial introduction to the Mathematica package STRINGVACUA, which is designed to find vacua of string-derived or inspired four-dimensional N=1 supergravities. The package uses powerful algebro-geometric methods, as implemented in the free computer algebra system Singular, but requires no knowledge of the mathematics upon which it is based. A series of easy-to-use Mathematica modules are provided which can be used both in string theory and in more general applications requiring fast polynomial computations. The use of these modules is illustrated throughout with simple examples.

Program summary

Program title: STRINGVACUACatalogue identifier: AEBZ_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEBZ_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GNU GPLNo. of lines in distributed program, including test data, etc.: 31 050No. of bytes in distributed program, including test data, etc.: 163 832Distribution format: tar.gzProgramming language: “Mathematica” syntaxComputer: Home and office spec desktop and laptop machines, networked or stand aloneOperating system: Windows XP (with Cygwin), Linux, Mac OS, running Mathematica V5 or aboveRAM: Varies greatly depending on calculation to be performedClassification: 11.1External routines: Linux: The program “Singular” is called from Mathematica. Windows: “Singular” is called within the Cygwin environment from Mathematica.Nature of problem: A central problem of string-phenomenology is to find stable vacua in the four-dimensional effective theories which result from compactification.Solution method: We present an algorithmic method, which uses techniques of algebraic geometry, to find all of the vacua of any given string-phenomenological system in a huge class.Running time: Varies greatly depending on calculation requested.     

On the construction and display of a polytopal mesh for the N-dimensional hypercube and (N + 1) simplex

By considering the analytical properties of polytopes it is possible to design a general data structure, a polytopal mesh, to represent such N-dimensional objects. Further investigation of the N-dimensional hypercube leads to the construction of a ternary code for representing the hypercube and the interconnection between levels of the polytopal mesh. This technique has been extended to other convex polytopes and specific examples of the N-dimensional cross polytope and simplex are given. Various projection techniques are used to display the convex polytopes on a two dimensional viewport.     

PDSW: A program for the calculation of photon energy distribution resulting from radioactive elements in seawater

Photons, when emitted from radioactive sources in seawater, are subsequent to multiple scattering mechanisms, namely the photoelectric effect, the Compton scattering and the pair production effect. Thus, the monoenergetic emission of photons in seawater will result in equilibrium in a distribution of photons with different energies. PDSW is a MATLAB program which calculates this distribution and can be found useful for the characterization of measured spectra obtained by gamma detectors such as NaI(Tl). PDSW has been developed as an autonomous MATLAB function in order to make possible to integrate it in other applications. All calculations are performed using a typical value for seawater salinity (3.5%).

Program summary

Title of program: PDSWCatalogue identifier: ADWWProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWWProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputer: x86Operating systems: WindowsProgramming language used: MATLABMemory required: 10 MbNumber of bits in a word: 32Number of processors used: 1Vectorized or parallelized?: noNumber of bytes in distributed program, including test data, etc.: 16 378Number of lines in distributed program, including test data, etc.: 3004Distribution format:tar.gzCPC Program Library subprograms used: noneNature of physical problem: Calculation of photon energy distribution in seawater taking into account the photoelectric effect, the Compton scattering and the pair production effect.Method of solution: Analytical calculation of the continuity equation for photon energy distribution in seawater and numerical integration of this equation in equilibrium.Restrictions on the complexity of the program: Very small resolution results in large memory requirements and high execution time.Typical running time: (Maximum energy-minimum resolution) 20 sUnusual features of the program: none     

Feynman Integral Evaluation by a Sector decomposiTion Approach (FIESTA)

We present a new program performing the sector decomposition and integrating the expression afterwards. The program takes a set of propagators and a set of indices as input and returns the epsilon-expansion of the corresponding integral.

Program summary

Program title: FIESTACatalogue identifier: AECP_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AECP_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GPL v2No. of lines in distributed program, including test data, etc.: 88 281No. of bytes in distributed program, including test data, etc.: 6 153 480Distribution format: tar.gzProgramming language: Wolfram Mathematica 6.0 [3] and CComputer: from a desktop PC to supercomputerOperating system: Unix, Linux, WindowsRAM: depends on the complexity of the problemClassification: 4.4, 4.12, 5, 6.5External routines: QLink [1], Vegas [2]Nature of problem: The sector decomposition approach to evaluating Feynman integrals falls apart into the sector decomposition itself, where one has to minimize the number of sectors; the pole resolution and epsilon expansion; and the numerical integration of the resulting expression.Solution method: The sector decomposition is based on a new strategy. The sector decomposition, pole resolution and epsilon-expansion are performed in Wolfram Mathematica 6.0 [3]. The data is stored on hard disk via a special program, QLink [1]. The expression for integration is passed to the C-part of the code, that parses the string and performs the integration by the Vegas algorithm [2]. This part of the evaluation is perfectly parallelized on multi-kernel computers.Restrictions: The complexity of the problem is mostly restricted by the CPU time required to perform the evaluation of the integral, however there is currently a limit of maximum 11 positive indices in the integral; this restriction is to be removed in future versions of the code.Running time: Depends on the complexity of the problem.References:[1] http://qlink08.sourceforge.net, open source.[2] G.P. Lepage, The Cornell preprint CLNS-80/447, 1980.[3] http://www.wolfram.com/products/mathematica/index.html2.     

Kranc: a Mathematica package to generate numerical codes for tensorial evolution equations

We present a suite of Mathematica-based computer-algebra packages, termed “Kranc”, which comprise a toolbox to convert certain (tensorial) systems of partial differential evolution equations to parallelized C or Fortran code for solving initial boundary value problems. Kranc can be used as a “rapid prototyping” system for physicists or mathematicians handling very complicated systems of partial differential equations, but through integration into the Cactus computational toolkit we can also produce efficient parallelized production codes. Our work is motivated by the field of numerical relativity, where Kranc is used as a research tool by the authors. In this paper we describe the design and implementation of both the Mathematica packages and the resulting code, we discuss some example applications, and provide results on the performance of an example numerical code for the Einstein equations.

Program summary

Title of program: KrancCatalogue identifier: ADXS_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXS_v1_0Program obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandDistribution format: tar.gzComputer for which the program is designed and others on which it has been tested: General computers which run Mathematica (for code generation) and Cactus (for numerical simulations), tested under LinuxProgramming language used: Mathematica, C, Fortran 90Memory required to execute with typical data: This depends on the number of variables and gridsize, the included ADM example requires 4308 KBHas the code been vectorized or parallelized: The code is parallelized based on the Cactus framework.Number of bytes in distributed program, including test data, etc.: 1 578 142Number of lines in distributed program, including test data, etc.: 11 711Nature of physical problem: Solution of partial differential equations in three space dimensions, which are formulated as an initial value problem. In particular, the program is geared towards handling very complex tensorial equations as they appear, e.g., in numerical relativity. The worked out examples comprise the Klein-Gordon equations, the Maxwell equations, and the ADM formulation of the Einstein equations.Method of solution: The method of numerical solution is finite differencing and method of lines time integration, the numerical code is generated through a high level Mathematica interface.Restrictions on the complexity of the program: Typical numerical relativity applications will contain up to several dozen evolution variables and thousands of source terms, Cactus applications have shown scaling up to several thousand processors and grid sizes exceeding 500³.Typical running time: This depends on the number of variables and the grid size: the included ADM example takes approximately 100 seconds on a 1600 MHz Intel Pentium M processor.Unusual features of the program: based on Mathematica and Cactus     

The density matrix renormalization group for strongly correlated electron systems: A generic implementation

The purpose of this paper is (i) to present a generic and fully functional implementation of the density-matrix renormalization group (DMRG) algorithm, and (ii) to describe how to write additional strongly-correlated electron models and geometries by using templated classes. Besides considering general models and geometries, the code implements Hamiltonian symmetries in a generic way and parallelization over symmetry-related matrix blocks.

Program summary

Program title: DMRG++Catalogue identifier: AEDJ_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEDJ_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: See file LICENSENo. of lines in distributed program, including test data, etc.: 15 795No. of bytes in distributed program, including test data, etc.: 83 454Distribution format: tar.gzProgramming language: C++, MPIComputer: PC, HP clusterOperating system: Any, tested on LinuxHas the code been vectorized or parallelized?: YesRAM: 1 GB (256 MB is enough to run included test)Classification: 23External routines: BLAS and LAPACKNature of problem: Strongly correlated electrons systems, display a broad range of important phenomena, and their study is a major area of research in condensed matter physics. In this context, model Hamiltonians are used to simulate the relevant interactions of a given compound, and the relevant degrees of freedom. These studies rely on the use of tight-binding lattice models that consider electron localization, where states on one site can be labeled by spin and orbital degrees of freedom. The calculation of properties from these Hamiltonians is a computational intensive problem, since the Hilbert space over which these Hamiltonians act grows exponentially with the number of sites on the lattice.Solution method: The DMRG is a numerical variational technique to study quantum many body Hamiltonians. For one-dimensional and quasi one-dimensional systems, the DMRG is able to truncate, with bounded errors and in a general and efficient way, the underlying Hilbert space to a constant size, making the problem tractable.Running time: The test program runs in 15 seconds.     

NumSBT: A subroutine for calculating spherical Bessel transforms numerically

A previous subroutine, LSFBTR, for computing numerical spherical Bessel (Hankel) transforms is updated with several improvements and modifications. The procedure is applicable if the input radial function and the output transform are defined on logarithmic meshes and if the input function satisfies reasonable smoothness conditions. Important aspects of the procedure are that it is simply implemented with two successive applications of the fast Fourier transform, and it yields accurate results at very large values of the transform variable. Applications to the evaluation of overlap integrals and the Coulomb potential of multipolar charge distributions are described.

Program summary

Program title: NumSBTCatalogue identifier: AANZ_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AANZ_v2_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.: 476No. of bytes in distributed program, including test data, etc.: 4451Distribution format: tar.gzProgramming language: Fortran 90Computer: GenericOperating system: LinuxClassification: 4.6Catalogue identifier of previous version: AANZ_v1_0Journal reference of previous version: Comput. Phys. Comm. 30 (1983) 93Does the new version supersede the previous version?: NoNature of problem: This program is a subroutine which, for a function defined numerically on a logarithmic mesh in the radial coordinate, generates the spherical Bessel, or Hankel, transform on a logarithmic mesh in the transform variable. Accurate results for large values of the transform variable are obtained, that would not be otherwise obtainable.Solution method: The program applies a procedure proposed by the author [1] that treats the problem as a convolution. The calculation then requires two applications of the fast Fourier transform method.Reasons for new version: The method of computing the transform at small values of the transform variable has been substantially changed and the whole procedure simplified. In addition, the possibility of computing the transform for a single transform variable value has been incorporated. The code has also been converted to Fortran 90 from Fortran 77.Restrictions: The procedure is most applicable to smooth functions defined on (0,∞) with a limited number of nodes.Running time: The example provided with the distribution takes a few seconds to execute.References:[1] J.D. Talman, J. Comp. Phys. 29 (1978) 35.     

Solution of few-body problems with the stochastic variational method II: Two-dimensional systems

A computational approach is presented for efficient solution of two-dimensional few-body problems, such as quantum dots or excitonic complexes, using the stochastic variational method. The computer program can be used to calculate the energies and wave functions of various two-dimensional systems.

Program summary

Program title: svm-2dCatalogue identifier: AEBE_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEBE_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.: 5091No. of bytes in distributed program, including test data, etc.: 130 963Distribution format: tar.gzProgramming language: Fortran 90Computer: The program should work on any system with a Fortran 90 compilerOperating system: The program should work on any system with a Fortran 90 compilerClassification: 7.3Nature of problem: Variational calculation of energies and wave functions using Correlated Gaussian basis.Solution method: Two-dimensional few-electron problems are solved by the variational method. The ground state wave function is expanded into Correlated Gaussian basis functions and the parameters of the basis states are optimized by a stochastic selection procedure. Accurate results can be obtained for 2-6 electron systems.Running time: A couple of hours for a typical system.     

Resolution of singularities for multi-loop integrals

We report on a program for the numerical evaluation of divergent multi-loop integrals. The program is based on iterated sector decomposition. We improve the original algorithm of Binoth and Heinrich such that the program is guaranteed to terminate. The program can be used to compute numerically the Laurent expansion of divergent multi-loop integrals regulated by dimensional regularisation. The symbolic and the numerical steps of the algorithm are combined into one program.

Program summary

Program title: sector_decompositionCatalogue identifier: AEAG_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEAG_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.: 47 506No. of bytes in distributed program, including test data, etc.: 328 485Distribution format: tar.gzProgramming language: C++Computer: allOperating system: UnixRAM: Depending on the complexity of the problemClassification: 4.4External routines: GiNaC, available from http://www.ginac.de, GNU scientific library, available from http://www.gnu.org/software/gslNature of problem: Computation of divergent multi-loop integrals.Solution method: Sector decomposition.Restrictions: Only limited by the available memory and CPU time.Running time: Depending on the complexity of the problem.     

TiReX: Replica-exchange molecular dynamics using Tinker

We present a driver program for performing replica-exchange molecular dynamics simulations with the Tinker package. Parallelization is based on the Message Passing Interface, with every replica assigned to a separate process. The algorithm is not communication intensive, which makes the program suitable for running even on loosely coupled cluster systems. Particular attention is paid to the practical aspects of analyzing the program output.

Program summary

Program title: TiReXCatalogue identifier: AEEK_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEEK_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.: 43 385No. of bytes in distributed program, including test data, etc.: 502 262Distribution format: tar.gzProgramming language: Fortran 90/95Computer: Most UNIX machinesOperating system: LinuxHas the code been vectorized or parallelized?: parallelized with MPIClassification: 16.13External routines: TINKER version 4.2 or 5.0, built as a libraryNature of problem: Replica-exchange molecular dynamics.Solution method: Each replica is assigned to a separate process; temperatures are swapped between replicas at regular time intervals.Running time: The sample run may take up to a few minutes.     

RAEEM: A Maple package for finding a series of exact traveling wave solutions for nonlinear evolution equations

In Maple 8, by taking advantage of the package RIF contained in DEtools, we developed a package RAEEM which is a comprehensive and complete implementation of such methods as the tanh-method, the extended tanh-method, the Jacobi elliptic function method and the elliptic equation method. RAEEM can entirely automatically output a series of exact traveling wave solutions, including those of polynomial, exponential, triangular, hyperbolic, rational, Jacobi elliptic, Weierstrass elliptic type. The effectiveness of the package is illustrated by applying it to a large variety of equations. In addition to recovering previously known solutions, we also obtain more general forms of some solutions and new solutions.

Program summary

Title of program: RAEEMCatalogue identifier: ADUPProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADUPProgram obtained from: CPC Program Library, Queen's University of Belfast, N. IrelandComputers: PC Pentium IVInstallations: CopyOperating systems: Windows 98/2000/XPProgram language used: Maple 8Memory required to execute with typical data: depends on the problem, minimum about 8M wordsNo. of bits in a word: 8No. of lines in distributed program, including test data, etc.: 3163No. of bytes in distributed program, including the test data, etc.: 26 720Distribution format: tar.gzNature of physical problem: Our program provides exact traveling wave solutions, which describe various phenomena in nature, and thus can give more insight into the physical aspects of problems. These solutions may be easily used in further applications.Restriction on the complexity of the problem: The program can handle system of nonlinear evolution equations with any number of independent and dependent variables, in which each equation is a polynomial (or can be converted to a polynomial) in the dependent variables and their derivatives.Typical running time: It depends on the input equations as well as the degrees of the desired polynomial solutions. For most of the equations we have computed, the running time is no more than 100 s.