Integer matrix diagonalization

We consider algorithms for computing the Smith normal form of integer matrices. A variety of different strategies have been proposed, primarily aimed at avoiding the major obstacle that occurs in such computations-explosive growth in size of intermediate entries. We present a new algorithm with excellent performance. We investigate the complexity of such computations, indicating relationships with NP-complete problems. We also describe new heuristics which perform well in practice. Wie present experimental evidence which shows our algorithm outperforming previous methods. (C) 1997 Academic Press Limited.

Mean anisotropy of homogeneous Gaussian random fields and anisotropic norms of linear translation-invariant operators on multidimensional integer lattices

Sensitivity of output of a linear operator to its input can be quantified in various ways. In Control Theory, the input is usually interpreted as disturbance and the output is to be minimized in some sense. In stochastic worst-case design settings, the disturbance is considered random with imprecisely known probability distribution. The prior set of probability measures can be chosen so as to quantify how far the disturbance deviates from the white-noise hypothesis of Linear Quadratic Gaussian control. Such deviation can be measured by the minimal Kullback-Leibler informational divergence from the Gaussian distributions with zero mean and scalar covariance matrices. The resulting anisotropy functional is defined for finite power random vectors. Originally, anisotropy was introduced for directionally generic random vectors as the relative entropy of the normalized vector with respect to the uniform distribution on the unit sphere. The associated a-anisotropic norm of a matrix is then its maximum root mean square or average energy gain with respect to finite power or directionally generic inputs whose anisotropy is bounded above by a≥0. We give a systematic comparison of the anisotropy functionals and the associated norms. These are considered for unboundedly growing fragments of homogeneous Gaussian random fields on multidimensional integer lattice to yield mean anisotropy. Correspondingly, the anisotropic norms of finite matrices are extended to bounded linear translation invariant operators over such fields.

Heuristic algorithm for computing reversal distance with multigene families via binary integer programming

Hannenhalli and Pevzner developed the first polynomial-time algorithm for the combinatorial problem of sorting of signed genomic data. Their algorithm solves the minimum number of reversals required for rearranging a genome to another when gene duplication is nonexisting. In this paper, we show how to extend the Hannenhalli-Pevzner approach to genomes with multigene families. We propose a new heuristic algorithm to compute the reversal distance between two genomes with multigene families via the concept of binary integer programming without removing gene duplicates. The experimental results on simulated and real biological data demonstrate that the proposed algorithm is able to find the reversal distance accurately. ©2005 IEEE

Extended GCD and Hermite normal form algorithms via lattice basis reduction

Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We present an algorithm which uses lattice basis reduction to produce small integer multipliers x(1), ..., x(m) for the equation s = gcd (s(1), ..., s(m)) = x(1)s(1) + ... + x(m)s(m), where s1, ... , s(m) are given integers. The method generalises to produce small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.

Non-diagonal solutions of the reflection equation for the trigonometric A((1)) (n-1) vertex model

We obtain a class of non-diagonal solutions of the reflection equation for the trigonometric A(n-1)((1)) vertex model. The solutions can be expressed in terms of intertwinner matrix and its inverse, which intertwine two trigonometric R-matrices. In addition to a discrete (positive integer) parameter l, 1 less than or equal to l less than or equal to n, the solution contains n + 2 continuous boundary parameters.

A low-temperature insulating phase at v=1.5 for 2D holes in high-mobility SiSi1-xGex heterostructures with Landau level degeneracy

Magneto-transport measurements of the 2D hole system (2DHS) in p-type Si-Si1-xGex heterostructures identify the integer quantum Hall effect (IQHE) at dominantly odd-integer filling factors v and two low-temperature insulating phases (IPs) at v = 1.5 and v less than or similar to 0.5, with re-entrance to the quantum Hall effect at v = 1. The temperature dependence, current-voltage characteristics, and tilted field and illumination responses of the IP at v = 1.5 indicate that the important physics is associated with an energy degeneracy of adjacent Landau levels of opposite spin, which provides a basis for consideration of an intrinsic, many-body origin.

Analysis and implementation of a new constant acceleration subcycling algorithm

An algorithm for explicit integration of structural dynamics problems with multiple time steps is proposed that averages accelerations to obtain subcycle states at a nodal interface between regions integrated with different time steps. With integer time step ratios, the resulting subcycle updates at the interface sum to give the same effect as a central difference update over a major cycle. The algorithm is shown to have good accuracy, and stability properties in linear elastic analysis similar to those of constant velocity subcycling algorithms. The implementation of a generalised form of the algorithm with non-integer time step ratios is presented. (C) 1997 by John Wiley & Sons, Ltd.

Fluorescence spectrum of a two-level atom driven by a multiple modulated field

We investigate the fluorescence spectrum of a two-level atom driven by a multiple amplitude-modulated field. The driving held is modeled as a polychromatic field composed of a strong central (resonant) component and a large number of symmetrically detuned sideband fields displaced from the central component by integer multiples of a constant detuning. Spectra obtained here differ qualitatively from those observed for a single pair of modulating fields [B. Blind, P.R. Fontana, and P. Thomann, J. Phys. B 13, 2717 (1980)]. In the case of a small number of the modulating fields, a multipeaked spectrum is obtained with the spectral features located at fixed frequencies that are independent of the number of modulating fields and their Rabi frequencies. As the number of the modulating fields increases, the spectrum ultimately evolves to the well-known Mellow triplet with the sidebands shifted from the central component by an effective Rabi frequency whose magnitude depends on the initial relative phases of the components of the driving held. For equal relative phases, the effective Rabi frequency of the driving field can be reduced to zero resulting in the disappearance of fluorescence spectrum, i.e., the atom can stop interacting with the field. When the central component and the modulating fields are 180 degrees out of phase, the spectrum retains its triplet structure with the sidebands located at frequencies equal to the sum of the Rabi frequencies of the component of the driving field. Moreover, we shaw that the frequency of spontaneous emission can be controlled and switched from one frequency to another when the Rabi frequency or initial phase of the modulating fields are varied.

Mathematical methods for spatially cohesive reserve design

The problem of designing spatially cohesive nature reserve systems that meet biodiversity objectives is formulated as a nonlinear integer programming problem. The multiobjective function minimises a combination of boundary length, area and failed representation of the biological attributes we are trying to conserve. The task is to reserve a subset of sites that best meet this objective. We use data on the distribution of habitats in the Northern Territory, Australia, to show how simulated annealing and a greedy heuristic algorithm can be used to generate good solutions to such large reserve design problems, and to compare the effectiveness of these methods.

Existence and embeddings of partial Steiner triple systems of order ten with cubic leaves

Denote the set of 21 non-isomorphic cubic graphs of order 10 by L. We first determine precisely which L is an element of L occur as the leave of a partial Steiner triple system, thus settling the existence problem for partial Steiner triple systems of order 10 with cubic leaves. Then we settle the embedding problem for partial Steiner triple systems with leaves L is an element of L. This second result is obtained as a corollary of a more general result which gives, for each integer v greater than or equal to 10 and each L is an element of L, necessary and sufficient conditions for the existence of a partial Steiner triple system of order v with leave consisting of the complement of L and v - 10 isolated vertices. (C) 2004 Elsevier B.V. All rights reserved.

First-principles quantum simulations of dissociation of molecular condensates: Atom correlations in momentum space

We investigate the quantum many-body dynamics of dissociation of a Bose-Einstein condensate of molecular dimers into pairs of constituent bosonic atoms and analyze the resulting atom-atom correlations. The quantum fields of both the molecules and atoms are simulated from first principles in three dimensions using the positive-P representation method. This allows us to provide an exact treatment of the molecular field depletion and s-wave scattering interactions between the particles, as well as to extend the analysis to nonuniform systems. In the simplest uniform case, we find that the major source of atom-atom decorrelation is atom-atom recombination which produces molecules outside the initially occupied condensate mode. The unwanted molecules are formed from dissociated atom pairs with nonopposite momenta. The net effect of this process-which becomes increasingly significant for dissociation durations corresponding to more than about 40% conversion-is to reduce the atom-atom correlations. In addition, for nonuniform systems we find that mode mixing due to inhomogeneity can result in further degradation of the correlation signal. We characterize the correlation strength via the degree of squeezing of particle number-difference fluctuations in a certain momentum-space volume and show that the correlation strength can be increased if the signals are binned into larger counting volumes.

Vehicle routing and crew scheduling for metropolitan mail distribution at Australia Post

This paper presents a new multi-depot combined vehicle and crew scheduling algorithm, and uses it, in conjunction with a heuristic vehicle routing algorithm, to solve the intra-city mail distribution problem faced by Australia Post. First we describe the Australia Post mail distribution problem and outline the heuristic vehicle routing algorithm used to find vehicle routes. We present a new multi-depot combined vehicle and crew scheduling algorithm based on set covering with column generation. The paper concludes with a computational investigation examining the affect of different types of vehicle routing solutions on the vehicle and crew scheduling solution, comparing the different levels of integration possible with the new vehicle and crew scheduling algorithm and comparing the results of sequential versus simultaneous vehicle and crew scheduling, using real life data for Australia Post distribution networks.