Potts models with magnetic field: Arithmetic,geometry, and computation

We give a sheaf theoretic interpretation of Potts models with external magnetic field, in terms of constructible sheaves and their Euler characteristics. We show that the polynomial countability question for the hypersurfaces defined by the vanishing of the partition function is affected by changes in the magnetic field: elementary examples suffice to see non-polynomially countable cases that become polynomially countable after a perturbation of the magnetic field. The same recursive formula for the Grothendieck classes, under edge-doubling operations, holds as in the case without magnetic field, but the closed formulae for specific examples like banana graphs differ in the presence of magnetic field. We give examples of computation of the Euler characteristic with compact support, for the set of real zeros, and find a similar exponential growth with the size of the graph. This can be viewed as a measure of topological and algorithmic complexity. We also consider the computational complexity question for evaluations of the polynomial, and show both tractable and NP-hard examples, using dynamic programming.     

First excitations of the spin 1/2 Heisenberg antiferromagnet on the kagomé lattice

We study the exact low energy spectra of the spin 1/2 Heisenberg antiferromagnet on small samples of the kagomé lattice of up to N=36 sites. In agreement with the conclusions of previous authors, we find that these low energy spectra contradict the hypothesis of Néel type long range order. Certainly, the ground state of this system is a spin liquid, but its properties are rather unusual. The magnetic () excitations are separated from the ground state by a gap. However, this gap is filled with nonmagnetic () excitations. In the thermodynamic limit the spectrum of these nonmagnetic excitations will presumably develop into a gapless continuum adjacent to the ground state. Surprisingly, the eigenstates of samples with an odd number of sites, i.e. samples with an unsaturated spin, exhibit symmetries which could support long range chiral order. We do not know if these states will be true thermodynamic states or only metastable ones. In any case, the low energy properties of the spin 1/2 Heisenberg antiferromagnet on the kagomé lattice clearly distinguish this system from either a short range RVB spin liquid or a standard chiral spin liquid. Presumably they are facets of a generically new state of frustrated two-dimensional quantum antiferromagnets. Received: 27 November 1997 / Accepted: 29 January 1998     

k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．     

Kalman filtering of a space-time Markov random field

In this paper, finite-dimensional recursive filters for space-time Markov random fields are derived. These filters can be used with the expectation maximization (EM) algorithm to yield maximum likelihood estimates of the parameters of the model.     

Solving Problems with Min-Type Functions by Disjunctive Programming

We consider applications of disjunctive programming to global optimization and problems with equilibrium constraints. We propose a modification of the algorithm of F. Beaumont for disjunctive programming problems and show its numerical efficiency.     

A stochastic algorithm using one sample point per iteration and diminishing stepsizes

A stochastic algorithm for finding stationary points of real-valued functions defined on a Euclidean space is analyzed. It is based on the Robbins-Monro stochastic approximation procedure. Gradient evaluations are done by means of Monte Carlo simulations. At each iteratex _i , one sample point is drawn from an underlying probability space, based on which the gradient is approximated. The descent direction is against the approximation of the gradient, and the stepsize is 1/i. It is shown that, under broad conditions, w.p.1 if the sequence of iteratesx ₁,x ₂,...generated by the algorithm is bounded, then all of its accumulation points are stationary.     

Maximizing a Linear Fractional Function on a Pareto Efficient Frontier

We consider the problem of maximizing a linear fractional function on the Pareto efficient frontier of two other linear fractional functions. We present a finite pivoting-type algorithm that solves the maximization problem while computing simultaneously the efficient frontier. Application to multistage efficiency analysis is discussed. An example demonstrating the computational procedure is included.     

Effective magnetic properties of a composite material with circular conductive elements

Effective magnetic properties of a composite meta-material consisting of periodically arranged circular conductive elements are studied theoretically. A general expression for the effective bulk permeability is obtained with mutual effects and lattice ordering being taken into account. The resonance frequency of the permeability is found to be strongly dependent on the size and shape of the unit cell. Frequency dispersion of the permeability is studied with special attention paid to the frequency range, where negative values of the permeability are possible. Corresponding recommendations for optimisation of the meta-materials with negative permeability are made. The results are confirmed by numerical simulations of the finite structure behaviour in an external magnetic field. Received 19 April 2002 Published online 31 July 2002     

A search technique for global optimization in a chaotic environment

We describe a new algorithm which uses the trajectories of a discrete dynamical system to sample the domain of an unconstrained objective function in search of global minima. The algorithm is unusually adept at avoiding nonoptimal local minima and successfully converging to a global minimum. Trajectories generated by the algorithm for objective functions with many local minima exhibit chaotic behavior, in the sense that they are extremely sensitive to changes in initial conditions and system parameters. In this context, chaos seems to have a beneficial effect: failure to converge to a global minimum from a given initial point can often be rectified by making arbitrarily small changes in the system parameters.