Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity

The computational complexity of internal diffusion-limited aggregation (DLA) is examined from both a theoretical and a practical point of view. We show that for two or more dimensions, the problem of predicting the cluster from a given set of paths is complete for the complexity class CC, the subset of P characterized by circuits composed of comparator gates. CC-completeness is believed to imply that, in the worst case, growing a cluster of size n requires polynomial time in n even on a parallel computer. A parallel relaxation algorithm is presented that uses the fact that clusters are nearly spherical to guess the cluster from a given set of paths, and then corrects defects in the guessed cluster through a nonlocal annihilation process. The parallel running time of the relaxation algorithm for two-dimensional internal DLA is studied by simulating it on a serial computer. The numerical results are compatible with a running time that is either polylogarithmic in n or a small power of n. Thus the computational resources needed to grow large clusters are significantly less on average than the worst-case analysis would suggest. For a parallel machine with k processors, we show that random clusters in d dimensions can be generated in ((n/k+logk)n ^2/d ) steps. This is a significant speedup over explicit sequential simulation, which takes (n ^1+2/d ) time on average. Finally, we show that in one dimension internal DLA can be predicted in (logn) parallel time, and so is in the complexity class NC.     

Two-dimensional monomer-dimer systems are computationally intractable

The classic problem of counting monomer-dimer arrangements on a two-dimensional lattice is analyzed using techniques from theoretical computer science. Under a certain assumption, made precise in the text, it can be shown that the general problem is computationally intractable. This negative result contrasts with the special case of a system with monomer density zero, for which efficient solutions have been known for some time. A second, much easier result, obtained under the same assumption, is that the partition function of a three-dimensional Ising system is computationally intractable. Again, the negative result contrasts with known efficient techniques for evaluating the partition function of a two-dimensional system.     

The computational complexity of pattern formation

The computational complexity of diffusion-limited aggregation and fluid invasion in porous media is studied. The time requirements on an idealized parallel computer for simulating the patterns formed by these models are investigated. It is shown that these growth models are P-complete. These results provide strong evidence that such pattern formation processes are inherently sequential and cannot be simulated efficiently in parallel.     

The computational complexity of the Lorentz lattice gas

The Lorentz lattice gas is studied from the perspective of computational complexity theory. It is shown that using massive parallelism, particle trajectories can be simulated in a time that scales logarithmically in the length of the trajectory. This result characterizes the logical depth of the Lorentz lattice gas and allows us to compare it to other models in statistical physics.     

The parallel complexity of growth models

This paper investigates the parallel complexity of several nonequilibrium growth models.Invasion percolation, Eden growth, ballistic deposition, andsolid-on-solid growth are all seemingly highly sequential processes that yield self-similar or self-affine random clusters. Nonetheless, we present fast parallel randomized algorithms for generating these clusters. The running times of the algorithms scale asO(log² N), whereN is the system size, and the number of processors required scales as a polynomial inN. The algorithms are based on fast parallel procedures for finding minimum-weight paths; they illuminate the close connection between growth models and self-avoiding paths in random environments. In addition to their potential practical value, our algorithms serve to classify these growth models as less complex than other growth models, such asdiffusion-limited aggregation, for which fast parallel algorithms probably do not exist.     

A measure of statistical complexity based on predictive information with application to finite spin systems

We propose the binding information as an information theoretic measure of complexity between multiple random variables, such as those found in the Ising or Potts models of interacting spins, and compare it with several previously proposed measures of statistical complexity, including excess entropy, Bialek et al.?s predictive information, and the multi-information. We discuss and prove some of the properties of binding information, particularly in relation to multi-information and entropy, and show that, in the case of binary random variables, the processes which maximise binding information are the ‘parity’ processes. The computation of binding information is demonstrated on Ising models of finite spin systems, showing that various upper and lower bounds are respected and also that there is a strong relationship between the introduction of high-order interactions and an increase of binding-information. Finally we discuss some of the implications this has for the use of the binding information as a measure of complexity.     

The Application of Superconducting Tunnel Junction Detectors to Astronomy

Detectors based on the superconducting-insulating-superconducting (SIS) junction long ago surpassed Schottky-diode semiconductor detectors as the most sensitive heterodyne mixers in the millimeter and submillimeter (far-infrared) wavelength range. Other novel superconducting device configurations have been applied as direct detectors. Though still in the early stages of development, and yet to find widespread application, they have demonstrated advantages over traditional semiconductor detectors in specialized situations. Exciting progress has been made in recent years in developing the superconducting tunnel junctions (STJ) as a photon detector for optical and near-optical wavelengths, where silicon CCD's are currently dominant. I examine some of the areas in which the properties of STJ detectors may best match the instrument capabilities that astronomical observations require, and discuss the implications of the intrinsic spectral resolution of the STJ. This capability will enable a significant increase in observing efficiency, once the technology matures, that should justify increased complexity of cryogenic systems, particularly for instruments to be used on the next generation of large ground-based telescopes.     

Monte Carlo Transition Dynamics and Variance Reduction

For Metropolis Monte Carlo simulations in statistical physics, efficient, easy- to-implement, and unbiased statistical estimators of thermodynamic properties are based on the transition dynamics. Using an Ising model example, we demonstrate (problem-specific) variance reductions compared to conventional histogram estimators. A proof of variance reduction in a microstate limit is presented.     

The Percolation Signature of the Spin Glass Transition

Magnetic ordering at low temperature for Ising ferromagnets manifests itself within the associated Fortuin–Kasteleyn (FK) random cluster representation as the occurrence of a single positive density percolating network. In this paper we investigate the percolation signature for Ising spin glass ordering—both in short-range (EA) and infinite-range (SK) models—within a two-replica FK representation and also within the different Chayes–Machta–Redner two-replica graphical representation. Based on numerical studies of the ±J EA model in three dimensions and on rigorous results for the SK model, we conclude that the spin glass transition corresponds to the appearance of two percolating clusters of unequal densities.     

The Proof That the Standard Transformations of E and B Are Not the Lorentz Transformations

In this paper it is exactly proved that the standard transformations of the three-dimensional (3D) vectors of the electric and magnetic fields E and B are not relativistically correct transformations. Thence the 3D vectors E and B are not well-defined quantities in the 4D space-time and, contrary to the general belief, the usual Maxwell equations with the 3D E and B are not in agreement with the special relativity. The 4-vectors E ^a and B ^a , as well-defined 4D quantities, are introduced instead of ill-defined 3D E and B. The proof is given in the tensor and the Clifford algebra formalisms.     

The spin dynamics of the random transverse Ising chain with a double-Gaussian disorder

The dynamical properties of one-dimensional random transverse Ising model （RTIM） with a double-Gaussian disorder is investigated by the recursion method. Based on the first twelve recurrences derived analytically, the spin autocorrelation function （SAF） and associated spectral density at high temperature were obtained numerically. Our results indicate that when the standard deviation σg （or OrB） of the exchange couplings Ji （or the random transverse fields Bi） is small, no long-time tail appears in the SAE The spin system undergoes a crossover from a central-peak behavior to a collectivemode behavior, which is the dynamical characteristics of RTIM with the bimodal disorder. However, when σJ （or σB） is large enough, the system exhibits similar dynamics behaviors to those of the RTIM with the Gaussian disorder, i.e., the system exhibits an enhanced central-peak behavior for large σJ or a disordered behavior for large σB. In this instance, SAFs exhibit a similar long-time tail, i.e., C（t） ~ t ^-2 for large t. Similar properties are obtained when Ji （or Bi） satisfy the double-exponential distribution or the double-uniform distribution. Besides, when both the standard deviations and the mean values of the exchange couplings are small, the effects of the Gaussian random bonds may drive the system undergo two crossovers from a triplet state to a doublet state, and then to a collective-mode state.     

Wavevector-Dependent Susceptibility in <Emphasis Type="Italic">Z</Emphasis>-Invariant Pentagrid Ising Model

We study the q-dependent susceptibility χ(q) of a Z-invariant ferromagnetic Ising model on a Penrose tiling, as first introduced by Korepin using de Bruijn's pentagrid for the rapidity lines. The pair-correlation function for this model can be calculated exactly using the quadratic difference equations from our previous papers. Its Fourier transform χ(q) is studied using a novel way to calculate the joint probability for the pentagrid neighborhoods of the two spins, reducing this calculation to linear programming. Since the lattice is quasiperiodic, we find that χ(q) is aperiodic and has everywhere dense peaks, which are not all visible at very low or high temperatures. More and more peaks become visible as the correlation length increases—that is, as the temperature approaches the critical temperature. Supported in part by NSF Grant No. PHY 01-00041.     

A mean-field,effective medium theory of random binary alloys III. The ising model with competing interactions

The Ising model with competing interactions is studied in a mean field effective medium approach. The phase diagram of such model alloys is studied. We conclude that for all ratios of the competing interaction moments, a spin glass phase always exists at low temperatures for certain concentration regimes.     

混沌伪随机序列的复杂度的稳定性研究

增强统计复杂度能反映混沌伪随机序列的随机本质,在此基础上提出了k错增强统计复杂度的定义,用来衡量混沌伪随机序列复杂度的稳定性,并证明了其两个基本特性.以Logistic,Henon,Cubic,Chebyshev和Tent映射产生的混沌伪随机序列为例,说明了该方法的应用.仿真结果表明,该方法能区分不同混沌伪随机序列的稳定性,是一种衡量混沌序列稳定性的有效方法. 关键词： 稳定性 k错增强统计复杂度')" href="#">k错增强统计复杂度 混沌 伪随机序列     

The evans-vigier field,B (3): Derivation of the de Broglie matter-wave equation from the Hamilton-Jacobi equation

The emergence of the Evans-Vigier fieldB ⁽³⁾ of vacuum electromagnetism has been accompanied by a novel charge quantization condition inferred from 0(3) gauge theory. This finding is used to derive the de Broglie matter-wave equation from the classical Hamilton-Jacobi (HJ) equation of one electron in the electromagnetic field. The HJ equation is used with the charge quantization condition to show that, in a perfectly elastic photon-electron interaction, complete transfer of angular momentum occurs self-consistently, and the electron acquires the angular momentum of the photon. In this limit the electron travels infinitesimally near the speed of light, and its concomitant electromagnetic fields become indistinguishable from those of the uncharged photon. This result independently proves the validity of the charge quantization condition and demonstrates unequivocally the existence of the vacuum fieldB ⁽³⁾.     

Unification of electromagnetism and gravitation: The equations of electrodynamics derived from the Riemann tensor in general relativity

The equations of free-space electrodynamics are derived directly from the Riemann curvature tensor and the Bianchi identity of general relativity by contracting on two indices to give a novel antisymmetric Ricci tensor. Within a factore/h, this is the field-strength tensor G of free-space electrodynamics. The Bianchi identity for G describes free-space electrodynamics in a manner analogous to, but more general than, Maxwell's equations for electrodynamics, the critical difference being the existence in general and special relativity of the Evans-Vigier fieldB ⁽³⁾.     

Study of the three-dimensional Ising model on film geometry with the cluster Monte Carlo method

Topological properties of clusters are used to extract critical parameters. This method is tested for the bulk properties ofd=2 percolation and thed=2, 3 Ising model. For the latter we obtain an accurate value of the critical temperatureJ/k _B T _c=0.221617(18). In the case of thed=3 Ising model with film geometry the critical value of the surface coupling at the special transitions is determined as J_1c/J=1.5004(20) together with the critical exponents ₁ ^m =0.237(5) and=0.461(15).     

Progress in numerical simulations of systems with a θ-vacuum like term: The two- and three-dimensional Ising model within an imaginary magnetic field

Using the approach developed in Azcoiti et al. (2003) [1], we succeeded in reconstructing the behaviour of the antiferromagnetic Ising model with imaginary magnetic field iθ for two and three dimensions in the low temperature regime. A mean-field calculation, expected to work well for high dimensions, is also carried out, and the mean-field results coincide qualitatively with those of the two- and three-dimensional Ising model. The mean-field analysis reveals also a phase structure more complex than the one expected for QCD with a topological θ-term.