Information theoretic approach to ground-state phase transitions for two and three-dimensional frustrated spin systems
Abstract
The information theoretic observables entropy (a measure of disorder), excess entropy (a measure of complexity) and multi information are used to analyze ground-state spin configurations for disordered and frustrated model systems in and . For both model systems, ground-state spin configurations can be obtained in polynomial time via exact combinatorial optimization algorithms, which allowed us to study large systems with high numerical accuracy. Both model systems exhibit a continuous transition from an ordered to a disordered ground state as a model parameter is varied. By using the above information theoretic observables it is possible to detect changes in the spatial structure of the ground states as the critical point is approached. It is further possible to quantify the scaling behavior of the information theoretic observables in the vicinity of the critical point. For both model systems considered, the estimates of critical properties for the ground-state phase transitions are in good agreement with existing results reported in the literature.
pacs:
75.40.Mg, 05.70.JkI Introduction
The standard analysis of physical phase transitions involves the analysis of order parameters and other derivatives of the free energy goldenfeld1992 . An alternative approach is based not on physical but information-theoretic approaches, an approach which has recently started to be occasionally used in the analysis of (more or less) complex systems crutchfield2010 .
The presented study extends on previous studies that employed information-theoretic methods to measure entropy (i.e. disorder and randomness) and statistical complexity (i.e. structure, patterns and correlations) for -dimensional systems Arnold1996 ; Crutchfield1997 ; Feldman2003 ; Feldman2008 . For systems, the excess entropy constitutes a well understood information-theoretic measure of complexity. Effectively, it accounts for the rapidity of entropy convergence. While the extension of entropy to higher dimensions is rather intuitive, the extension of excess entropy is not. As a remedy, in Ref. Feldman2003 , three different approaches were developed in order to extend the definition of excess entropy to , allowing to quantify the complexity for spatial systems in higher dimensions.
Most previous studies focused on characterizing the above information-theoretic observables for systems without disorder, only. As regards this, the local states method Schlijper1990 , proposed for the calculation of free energies within importance-sampling Monte Carlo (MC) simulations, was based on entropy estimation techniques for lattice models with discrete interactions and translation-invariant interactions (i.e. non-disordered, pure systems). It combined upper and lower bounds for the entropy density to compute free energies (along with an error estimate). A comparison of numerical simulations to exact results for the Ising ferromagnet indicated that it yields reliable estimates already for short simulation runs (even in the critical region).
Using quite similar entropy estimation techniques, the simulations reported in Ref. Feldman2003 were performed for the square lattice Ising model with nearest and next nearest neighbor interactions. By means of single spin-flip Metropolis dynamics at a comparatively low temperature, two variants of the excess entropy were put under scrutiny. A careful analysis indicated that these are sensitive to changes in the spatial structure of the spin configurations as the nearest neighbor coupling strength was varied. They were further found to be superior to conventional structure factors. This study allows to conclude that the excess entropy in comprises a general purpose measures of structure.
Only recently, Ref. Robinson2011 used similar methods to characterize local, i.e. lattice site dependent, entropies and local excess entropies for the Kaya-Berker model. The latter is based on the Ising antiferromagnet (IAFM) on a triangular lattice, wherein a particular sublattice is diluted, only. The IAFM exhibits geometric frustration and does not order at finite temperature. In contrast to the pure model, the Kaya-Berker model orders at finite temperature if at least a fraction of the sites on the diluted sublattice are deleted. The simulations were performed using single spin-flip Metropolis dynamics at fixed dilution , where the freezing temperature amounts to . In the simulation, various temperatures down to were considered. It was found that the distribution of local entropies broadens in the glassy phase below , indicating that for low temperatures local entropy is not homogeneously distributed over the lattice. Further, the average of the local excess entropy was observed to exhibit a pronounced peak at the critical temperature, indicating that it is sensitive to structural changes for the configurations as a result of the spin glass ordering. Finally, complexity-entropy diagrams for the frustrated Kaya-Berker model, recorded at various temperatures, were found to be qualitatively different from those corresponding to pure models (see Ref. Feldman2008 ). This study allows to conclude that local entropy density and local excess entropy are valuable observables that yield insight to local structure and randomness for frustrated systems.
Here, we aim to characterize the spatial structure displayed by exact ground states (GSs) of disordered model systems in terms of the information-theoretic observables entropy and excess entropy. For this purpose we consider the random bond Ising model ( RBIM) as well as the random field Ising model ( RFIM), which both exhibit disorder-driven zero-temperature phase transitions. More precise, we use one of the approaches developed in Ref. Feldman2003 , aimed at understanding spatial patterns for systems by parsing them into sequences. In addition we also consider the multi-information, which, for the ordinary Ising ferromagnet in the thermodynamic limit was proved to be maximized at the critical point Erb2004 . In contrast to the previous studies we work at , aiming to characterize the ground-state phase transitions that appear as the disorder is varied for the above two disordered model systems (see sect. II). In doing so, we were interested whether one can observe a change in the structure of the ground states by using the above information-theory inspired observables. Further, if the latter is possible, it is of interest to quantify the scaling behavior of these observables in the vicinity of the phase transition.
The remainder of the presented article is organized as follows. In section II we introduce the spin models that are considered in the presented study. In section III, the information-theoretic observables entropy and excess entropy are introduced and illustrated in more detail. Section IV reports on the numerical results, further discussed in section V. An elaborate summary of the presented article is available at the papercore database papercore .
Ii Models
Next, we present the two models which were studied in this work, the RBIM and the RFIM.
ii.1 random bond Ising model
We investigated GSs for the RBIM, considering a square lattice of side length . The respective model consists of Ising spins, for which a particular spin configuration might be written as , where . The energy of a given spin configuration is measured by the Edwards-Anderson Hamiltonian edwards1975
(1) |
where the sum is understood to run over all pairs of nearest-neighbor spins (on a square lattice), with periodic boundary conditions (BCs) in the -direction and free BCs in the -direction. In the above energy function, the bonds are quenched random variables drawn from the disorder distribution
(2) |
where the width of the distribution was fixed to . Consequently, one realization of the disorder consists of a mixture of antiferromagnetic bonds () that prefer an antiparallel alignment of the coupled spins, and ferromagnetic bonds () in favor of parallel aligned spins. In general, the competitive nature of these interactions gives rise to frustration. A plaquette, i.e. an elementary square on the lattice, is said to be frustrated if it is bordered by an odd number of antiferromagnetic bonds. In effect, frustration rules out a GS in which all the bonds are satisfied. As limiting cases one can identify the random bond Ising ferromagnet (FM) as and the (Gaussian) Edwards Anderson Ising spin glass (SG) edwards1975 ; SG2dReview2007 ; Hartmann2DSG2011 at . A GS spin configuration is simply a minimizer of the energy function Eq. 1. Thus, regarding the GSs as a function of the variable , we expect to find a ferromagnetic phase (spin glass phase) for () wherein denotes the critical point at which the FM-SG transition, i.e. a continuous disorder-driven phase transition, takes place. Samples of GSs for the RBIM for different values of the parameter are shown in Fig. 1(a).
The Ising spin glass is a paradigmatic model for a disordered magnet. Since the effects of the disorder are well visible at zero temperature, the investigation of ground state properties is of prime importance. For a planar version of this model, e.g., a square lattice with periodic boundary conditions in only one direction, a solution of the GS problem is possible by means of a mapping to an appropriate minimum-weight perfect-matching problem. This latter problem can be solved by means of exact combinatorial optimization algorithms from computer science SG2dReview2007 ; opt-phys2001 ; bieche1980 ; barahona1982 ; thomas2007 ; pardella2008 , whose running time increases only polynomially with the system size. Hence, very large systems can be treated exactly, giving very precise and reliable estimates for the observables. The GS problem for lattice dimensions or systems subject to an external magnetic field belong to the class of nondeterministic polynomial (NP)-hard problems bieche1980 ; cipra2000 . For those problems, no exact algorithm with a polynomial running time has been found so far. From a conceptual point of view, the existence of numerically exact and highly efficient algorithms for the SG with periodic boundary conditions in at most one direction motivates the special interest in this setup during the last decades.
As pointed out above, for the RBIM on planar lattice graphs (including the Ising spin glass), GS spin configurations can be found in polynomial time. We here use a particular mapping to an appropriate minimum-weight perfect matching problem, presented in Ref. pardella2008 . The use of this approach permits the treatment of large systems, easily up to , on single processor systems. In a previous study Melchert2009 , we performed such GS calculations and employed a finite-size scaling analysis for systems of moderate sizes () to locate the critical point at which the transitions takes place. Therefore, we analyzed the Binder parameter binder1981 and is expected to scale as , where is a size-independent function and signifies the critical exponent that describes the divergence of the correlation length as the critical point is approached. The magnetization is simply the sum of all spin-values in the GS spin configuration, i.e. . Using the data collapse anticipated by the scaling assumption above we obtained and (for a further study of this transition, yielding similar results using renormalization group techniques, see Ref. McMillan1984 ). Finally, we characterized the transition using a finite-size scaling analysis for the largest and second-largest ferromagnetic clusters of spins within the GS spin configurations. These clusters form as one proceeds from spin glass ordered to ferromagnetic ground states. The results obtained from the related scaling analysis support the results obtained earlier by considering the Binder parameter and magnetization. that is associated to the magnetization
ii.2 random field Ising model
We further investigated GSs for the RFIM on a simple cubic lattice of side length . The respective model consists of Ising spins, and the energy of a given spin configuration is measured by the Hamiltonian
(3) |
where the first sum is understood to run over all pairs of nearest-neighbor spins on a simple cubic lattice with fully periodic BCs. In the above energy function, the bonds that couple adjacent spins are ferromagnetic, i.e. , and the local fields () introduce disorder to the model. The values of the local fields are independently drawn from the disorder distribution
(4) |
where the mean of the distribution is fixed to zero and the width amounts to . Thus, one realization of the disorder consists of ferromagnetic spin-spin couplings with each spin coupled to a local random field.
The RFIM is a basic model for random systems fischer1991 ; young1998 and also gives rise to frustration. While in order to minimize Eq. 3 the ferromagnetic spin-spin coupling will tend to align coupled spins in parallel, the random fields will tend to align the spins parallel to the local field, possibly introducing a paramagnetic effect on the GSs. For a field width that is small compared to the ferromagnetic coupling, i.e. for , one might expect a dominance of the ferromagnetic spin-spin coupling in the GS spin configurations. In contrast to this, for a comparatively large field width, the orientation of the majority of spins in a GS will be determined by the local random fields, suggesting a paramagnetic GS for large values of . As a result, at , the RFIM exhibits a disorder driven, continuous ferromagnet to paramagnet (PM) transition regarding the ground state structure at a finite value . Samples of GSs for the RFIM for different values of the field strength are shown in Fig. 1(b).
The solution of the GS problem for the general RFIM (not only its variant) is possible by means of a mapping to an appropriate maximum-flow problem bastea1999 ; opt-phys2001 ; rieger2002 . This latter problem can be solved in polynomial time by means of exact combinatorial optimization algorithms from computer science. As for the RBIM this offers the possibility to study large systems, easily up to , giving very precise and reliable estimates for the observables.
Using such optimization methods, the critical point and critical exponents for the GS phase transition can be obtained by analyzing the magnetic properties of the model hartmann1998 ; dAuriac1997 ; hartmann2001 . For the RFIM we here quote the values for the critical point and for the critical exponent that describes the divergence of the correlation length as the critical point is approached.
Further, the RFIM also exhibits a particular percolation transition. I.e., regarding the simultaneous spanning of up and down spin domains as a function of the field strength , Ref. Seppala2002 report on the percolation critical point and the value (note that for random percolation in one has ; see Ref. stauffer1994 ). However, the results appeared to depend on the particular spanning criterion. In this regard, in the limit of the spanning probability approaching to zero (indicating the onset of percolation) the scaling analysis extrapolated to .
Iii Information-theoretic observables in and extension to and
In the current section we introduce basic notations from information theory, needed to define the entropy rate, excess entropy, and multi information that might be associated to a () sequence of symbols. In this regard, for the definition of the entropy rate and excess entropy we follow the notation of Refs. Shalizi2001 ; Crutchfield2003 ; Feldman2008 . For the definition of the multi information we follow Ref. Erb2004 . In the above references, a more elaborate discussion of the individual information-theoretic observables can be found.
A prerequisite for the definition of these observables is the -block Shannon entropy for a block of consecutive random variables . Each random variable might assume values , where the set denotes a finite alphabet (subsequently, the random variables will be identified with Ising spins, in which case will denote the binary alphabet ). For denoting a particular symbol block of length , the -block Shannon entropy reads
(5) |
where signifies the joint probability for blocks of consecutive symbols (i.e. spin orientations in the present context). In the above formula, the sum runs over all possible blocks, i.e., combinations of of consecutive symbols from .
iii.1 Entropy density, excess entropy, and multi information for one-dimensional symbol sequences
Using the -block Shannon entropy, the asymptotic entropy density for a system is given by
(6) |
A sequence of finite- approximations to the asymptotic entropy density that typically converges faster than the expression above is provided by the conditional entropies
(7) |
As given above, denotes the entropy of a single variable (spin) conditioned on a block of adjacent variables (spins). Thus, is the randomness that still remains, even after correlations over blocks of infinite length are accounted for. Viewed as a function of block size, the finite- conditional entropies converge to the asymptotic value from above. Hence, at small length scales the system tends to look more random than it is in the limit .
For one-dimensional systems, there are three different but equivalent expressions for the excess entropy. These are based on the convergence properties of the entropy density, the subextensive part of the block entropy in the limit of large block sizes, and, the mutual information between two semi-infinite blocks of variables, see Refs. Feldman2003 ; Feldman2008 . Here, we focus on the definition of excess entropy that relates to the convergence properties of the entropy density in the form
(8) |
The conditional entropies constitute upper bounds on the entropy rate, allowing for an improving estimate of for increasing . Thus, the individual terms in the sum comprise the entropy density overestimates on the level of blocks of finite length . In total, the excess entropy measures the area between and the horizontal line at . As such, accounts for the randomness that is present at small lengths and that vanishes in the limit of large block sizes.
In and in the limit of large block sizes, the multi information is given by the first summand in Eq. 8, i.e.
(9) |
Albeit is closely related to (this holds only in the limit of large block sizes ; see Ref. Erb2004 for a more general discussion of the multi information), it captures somewhat different characteristics regarding the convergence of the entropy density. In this regard it measures the decrease of average uncertainty in the description of the system by switching from the level of single variables (spins) statistics to the statistics attained as .
iii.2 Extension to and
Following Ref. Feldman2003 , the most general approach designed to write the entropy density as the entropy of a particular variable conditioned on a block of neighboring variables (similar to the case), uses so called neighborhood templates of a given size. In general, for a neighborhood template only spins in the same row left of a “target spin” and the spins in all rows below the target spin are considered. Fig. 2(a) shows such a finite-size template for a system, covering an overall number of spins. Similar to Ref. Feldman2003 we use the parameter in the conditional entropy (Eq. 7), to account for a successive addition of single sites from the neighborhood template shown in Fig. 2(a). Therein, the numbers within the cells indicate the order in which the lattice sites are added to the neighborhood template (from initial numerical experiments we found that it is not necessary to exceed () for the RBIM ( RFIM)). In this regard, let the subscript denote the relative position of a variable in the neighborhood template, specifying its distance to the target variable in terms of site-to-site hops (in particular the target variable is labeled ). Then, the order in which the sites are picked from the template reflects the increasing Euclidean distance of the particular lattice site to the target site. Thereby, we follow the convention that if there is a draw regarding the distance of two or more lattice sites, we add them to the neighborhood template from the top left to the bottom right, increasing the value of before (see the order of spins through in Fig. 2(a)). As an example note that . We followed a similar approach in , where the corresponding neighborhood template is shown in Fig. 2(b), and where e.g. .
Note that by the procedure discussed above, we disregarded the practice that if the interactions between the variables are of finite range, the neighborhood template only needs to be as “thick” as the interaction range Schlijper1990 ; Feldman2003 . For disordered model systems that exhibit competing interactions, nontrivial correlations between the spin degrees of freedom might emerge that extend towards the intrinsic range of the interactions (for a brief discussion of this issue and its implications, in particular for the design of an efficient cluster algorithm for the fully frustrated Ising model, see Ref. Kandel1992 ). Consequently, for the RBIM and RFIM we considered it more adequate to include more than just the nearest neighbors for the construction of a neighbor template.
Subsequently, and configurations of spins are analyzed by parsing them into one dimensional sequences using the order of the spins as illustrated in Fig. 2. The resulting sequences can then be analyzed using Eqs. 7 and 8, above. From a practical point of view it will subsequently be necessary to truncate the sums in Eqs. 7, 8 to a maximally feasible neighborhood size .
Iv Results
Here, our approach is somewhat different than that reported in Ref. Robinson2011 . In that study, one particular realization of disorder for the Kaya-Berker model was put under scrutiny at a particular value of the dilution parameter and for different temperatures (above as well as below the freezing temperature of the system). For that particular disorder instance and for a given temperature, a single-spin flip Metropolis dynamics was used to generate independent spin configurations. These spin configurations were then used to accumulate statistics for spin blocks (specified by the utilized neighborhood template) that provide means to estimate conditional entropies on either local (i.e. lattice site dependent) or global scale, where the latter is a spatial average of the local conditional entropies. As pointed out by the authors of Ref. Robinson2011 , it is important to accumulate spin-block statistics in a lattice site dependent manner so as to not overestimate the entropy of the system. A later average over the local observables yield the correct thermodynamic entropy, as verified by the authors.
However, note that here we work at , aiming to characterize ground state phase transitions for disordered model systems in and . I.e. for each realization of the disorder (and due to the particular disorder distributions used in the presented study), there is one particular spin configuration that qualifies as a ground state (aside from a trivial degeneracy stemming from the global spin-flip symmetry of the energy function Eqs. 1. As a remedy, in order to collect statistics for blocks of spins we sweep the neighborhood template over the full lattice (as one would do for pure systems, see Ref. Feldman2008 ), thus averaging over different ”local” configurations of the disorder. For one ground state and for a chosen block size , this yields one spatially averaged estimate for the conditional entropy on the level of -spin blocks. The results are then averaged over many realizations of the disorder. In doing so, we were interested whether one can observe a change in the structure of the ground states by using the above information-theory inspired observables, and how this compares to phase transitions, which were previously observed when using standard statistical-physics observables.
Furthermore, it is of interest to quantify the scaling behavior of these observables in the vicinity of the phase transition. Note that we also performed additional simulations using the definition of and neighbor-templates as used in Ref. Schlijper1990 and found no qualitative difference to the results reported below.
iv.1 Results for the Rbim
Entropy density:
As evident from Fig. 3(a), the entropy density for the RBIM for exhibits a rapid convergence. In this regard, for a neighborhood size of the average entropy density appears to take its asymptotic value for the full range of considered parameters . However, for the numerical simulations at we considered the maximally feasible neighborhood size . For smaller system sizes, had to be adjusted to somewhat smaller values to assure that for a given system size the measurement of the conditional entropies at a given level are based on sufficient statistics for the underlying -block shannon entropies. In this regard, at we used . The average entropy densities, restricted to neighborhood sizes through , are shown in Fig. 3(b). It can be seen that for small (large) values of the entropy density converges to a comparatively large (small) value representing the disordered (i.e. SG ordered) and ordered (i.e. ferromagnetic) phase, respectively. Especially the curve corresponding to exhibits a steep decrease in the interval . Moreover, the fluctuations of the entropy density are peaked at (not shown). As it appears, this parameter value is close to the asymptotic critical point that indicates the SG to FM transition for the RBIM McMillan1984 ; Melchert2009 in the limit of large system sizes.
Excess entropy:
A finite-size scaling analysis of the system size dependent peak position of the average excess entropy (see Fig. 4(a)) was performed in the following way: polynomials of order were fitted to the data curves at different system sizes in order to obtain an estimate of the peak position. Thereby, the index labels independent estimates of the peak positions as obtained by bootstrap resampling practicalGuide2009 . For the analysis, we considered bootstrap data sets, e.g. resulting in the final estimate . Anticipating the scaling form
(10) |
see inset of Fig. 4(a), and considering the fit interval yields the fit parameters , and for a reduced chi-square (). Note that as , the location of the peak disagrees with the location of the SG to FM transition. The latter estimate was obtained from an analysis of the binder-parameter for the GS magnetization Melchert2009 . Earlier simulations, using a transfer-matrix approach at finite temperature and extrapolated to , report on McMillan1984 .
A similar scaling analysis for the location of the peaks related to the finite-size susceptibilities by means of Gaussian fit-functions results in the estimate . Further, the width of the Gaussian fit-function obeys the scaling
(11) |
where and (, ). Note that the inverse of the latter fit parameter reads and is thus strikingly close to the critical exponent Melchert2009 ( McMillan1984 ) that characterizes the SG to FM transition.
Multi-information:
A scaling analysis of the system size dependent peak position displayed by the average multi-information (see Fig. 4(c)) according to the scaling assumption Eq. 10 in the range yields the fit-parameters , , and , i.e. (, ). Neglecting the smallest system size, i.e. restricting the fit interval to , leads to the estimate which is even closer to the known critical point.
Further, an analysis of the position and width of the peaks related to the finite-size fluctuations by means of Gaussian fit-functions results in the additional estimate (see Fig. 4(d)). As above, the widths obay the scaling form of Eq. 11, where a fit yields and , i.e. (, ; inset of Fig. 4(d)).
Note that here, both estimates of and both estimates of the exponent are reasonably close to those found earlier for the RBIM. Hence, this might indicate that in comparison to the full excess entropy, the multi-information is more sensitive to structural changes at the order-to-disorder transition in the RBIM.
Geometric properties of the GSs:
Upon increasing the value of the disorder parameter from to , it is possible to identify ferromagnetic clusters of spins with increasing size. A finite size scaling analysis of the relative size of the largest and second largest ferromagnetic clusters of spins for the independent GSs can be utilized to characterize the SG to FM transition in the RBIM. E.g. as reported in Ref. Melchert2009 , the relative size of the largest ferromagnetic cluster scales as , where a data collapse (for system sizes ) yields the scaling parameters , , and . Note that the results obtained for the multi-information is also in excellent agreement with those obtained from an analysis of the largest cluster size, which constitutes an observable that links to the geometric properties of the GS spin configurations.
iv.2 Results for the Rfim
Entropy density:
As can be seen from Fig. 5(a), the entropy density for the RFIM (the figure shows the data for ) convergence rapidly. I.e. for a neighborhood size of the average entropy density appears to take its asymptotic value for the full range of considered field strengths . During the numerical simulations, carried out on cubic systems of side length through , we thus considered the maximally feasible neighborhood size . The average entropy densities for are shown in Fig. 5(b). For the RFIM the ordered, i.e., ferromagnetic (FM)) and disordered, i.e., paramagnetic (PM) phases are located at small and large values of the disorder parameter , respectively. As discussed above, the curve corresponding to exhibits a steep decrease in the interval , which already allows to shed some light on where the characteristics of the model at change from ferromagnetic to paramagnetic. In a previous study, using the finite-size scaling of standard physical quantities, the critical strength of the random field at which the FM to PM transition takes place was found to be hartmann2001 .
Excess entropy:
The scaling analysis of the system size dependent peak position of the average excess entropy (see Fig. 6(a)) was performed similar to the RBIM above. Assuming that the system size dependent peak locations exhibit a scaling of the form
(12) |
see inset of Fig. 6(a), yields the fit parameters , and (, ). Note that as , the location of the peak extrapolates to a value that is close by the critical point , describing the transition of the probability for a simultaneous spanning of up and down spin domains from to , see Ref. Seppala2002 . A similar scaling analysis for the location of the peaks related to the finite-size susceptibilities , again by means of polynomials of order , results in the estimate , see inset of 6(b). As it appears, the estimates of obtained from the excess entropy and its fluctuation do not match up well.
Multi-information:
A finite-size scaling analysis of the system size dependent peak position shown by the average multi-information (see Fig. 6(c)) according to the scaling assumption Eq. 12 in the range yields the fit-parameters , , and (, ). Further, an analysis of the peak location for the related finite-size fluctuations results in the estimates , and (, ); see Fig. 6(d).
Note that here, both estimates of and both estimates of the exponent match up well. Also, the numerical estimates agree with the numerical value of within errorbars and the numerical value of (obtained by means of the above analyses) is in good agreement with the correlation length exponent reported in Ref. hartmann2001 . Further, they are in good agreement with the numerical values to which the scaling analysis for the percolation criterion in Ref. Seppala2002 extrapolates to. Again, these results indicate that the multi-information is very sensitive to structural changes in GS spin configurations at the order-to-disorder transition.
iv.3 The phase transition in purely information theoretic coordinates
In the above analyses the information theoretic coordinates entropy density and excess entropy , giving measures of randomness and complexity, respectively, were studied as a function of a model specific parameter. So as to facilitate a comparison of different models complexity-entropy diagrams are of great use Crutchfield1989 . A survey of complexity-entropy diagrams for different model systems can be found in Ref. Feldman2008 . The complexity-entropy relationship for the RBIM and RFIM for different system sizes are shown in Fig. 7. As evident from the figure, the curves for both models exhibit similar features. I.e. they have an isolated peak at a particular value of . This is similar to the complexity-entropy curve for the Ising FM, where the corresponding peak is located at entropy density with a peak height of , see Ref. Feldman2008 . In order to illustrate finite-size effects for the complexity-entropy diagram, three different system sizes for both models are shown. A scaling analysis of the finite-size peak locations indicates that for the RBIM ( RFIM) the peak shifts to the entropy density value () as . Comparing with the result of the FM mentioned before, one can say that for the RBIM and the RFIM, the order-disorder transition appears at smaller entropy but is connected with a higher complexity. Note, for the considered models, the complexity-entropy diagram contains the FM phase in the parameter range . The SG phase for the RBIM (PM phase for the RFIM) is found for .
V Discussion
Regarding the excess entropy, conceptually similar analyses carried out on spin configurations for the Ising FM, reported in Ref. Feldman2008 . The respective study concluded that the excess entropy is peaked at a temperature in the paramagnetic (i.e. disordered) phase above the true critical temperature . Qualitatively similar results on the mutual information for the Ising FM (and more general classical spin models) were recently presented in Ref. Wilms2011 . There, the authors conclude that the mutual information (equivalent to the excess entropy for systems; see Ref. Crutchfield2003 ) reaches a peak-value in the paramagnetic phase close to the system parameter (for this corresponds to ), again in disagreement with the critical point of the underlying model. Further, the authors note that the true critical point appears to coincide with the inflection point where the first derivative of the excess entropy tends to minus infinity in the thermodynamic limit (however, the authors present no systematic analysis of this observation). Hence, it is not too surprising that a finite-size scaling analysis for the peaks of the bare excess entropy does not directly allow to identify the critical point of the model considered here. Similar to the previous studies for the Ising FM, we here find that the excess entropy assumes an isolated peak at a parameter-value located slightly below the true critical point in the disordered phase. However, a scaling analysis reveals that in the thermodynamic limit, the peak of the related finite-size fluctuations is located right at the critical point.
The multi-information was introduced by Erb and Ay in Ref. Erb2004 , where the authors considered the multi-information to characterize spin-configuration for the Ising FM in the thermodynamic limit by analytic means. Among other things, the authors conclude that the multi-information exhibits an isolated global maximum right at the critical temperature (see Theorem 3.3 of Ref. Erb2004 ). Here, we find that in contrast to the excess entropy and in qualitative agreement with analytic results for the Ising FM, the peak of the multi-information tends towards the critical points reported in the literature as . However, the critical point to which the effective, system size dependent critical points related to the peaks of the excess entropy for the RFIM converges is in good agreement with the precise location that corresponds to a particular percolation transition for the respective spin model. Nevertheless, given the so far achieved numerical accuracy, it is still not clear to us whether these two transition points are really distinct. Anyway, both observables studied in this work basically turned out to be useful information-theoretic measures that might be used to distinguish the ordered and disordered phase of frustrated model systems, as e.g. the RBIM and RFIM. Further, the finite size scaling of these observables allows to estimate critical points and exponents that are in good agreement with the critical properties reported in the literature.
Given these promising results for systems exhibiting quenched disorder, it would be of particular interest to apply these methods to structural glasses binder2011 , where a simple way of analyzing snapshots of configurations is still missing biroli2008 .
Acknowledgements.
We thank F. Krzakala for valuable discussions and for pointing out Ref. biroli2008 . OM acknowledges financial support from the DFG (Deutsche Forschungsgemeinschaft) under grant HA3169/3-1. The simulations were performed at the HPC Cluster HERO, located at the University of Oldenburg (Germany) and funded by the DFG through its Major Instrumentation Programme (INST 184/108-1 FUGG) and the Ministry of Science and Culture (MWK) of the Lower Saxony State.References
- [1] N. Goldenfeld. Lectures on phase transitions and the renormalization group. Addison-Wesely, Reading (MA), 1992.
- [2] J. Crutchfield and K. Wiesner. Simplicity and complexity. Physics World, 23(2):36, 2010.
- [3] D. V. Arnold. Information-theoretic Analysis of Phase Transitions. Complex Systems, 10:143–155, 1996.
- [4] James P. Crutchfield and David P. Feldman. Statistical complexity of simple one-dimensional spin systems. Phys. Rev. E, 55:R1239–R1242, 1997.
- [5] D. P. Feldman and J. P. Crutchfield. Structural information in two-dimensional patterns: Entropy convergence and excess entropy. Phys. Rev. E, 67:051104, 2003. A summary of this article is available at papercore.org, see http://www.papercore.org/Feldman2003.
- [6] D. P. Feldman, C. S. McTague, and J. P. Crutchfield. The organization of intrinsic computation: Complexity-entropy diagrams and the diversity of natural information processing. CHAOS, 18:043106, 2008.
- [7] A. G. Schlijper, A. R. D. van Bergen, and B. Smit. Local-states method for the calculation of free energies in Monte Carlo simulations of lattice models. Phys. Rev. A, 41:1175–1178, 1990. A summary of this article is available at papercore.org, see http://www.papercore.org/Schlijper1990.
- [8] M. D. Robinson, D. P. Feldman, and S. R. McKay. Local entropy and structure in a two-dimensional frustrated system. CHAOS, 21:037114, 2011.
- [9] I. Erb and N. Ay. Mulit-Information in the thermodynamic Limit. J. Stat. Phys., 115:949, 2004.
- [10] Papercore, 2009. Papercore is a free and open access database for summaries of scientific (currently mainly physics) papers. For a summary of this article, see http://www.papercore.org/Melchert2012.
- [11] S. F. Edwards and P. W. Anderson. Theory of spin glasses. J. Phys. F, 5:965, 1975.
- [12] A. K. Hartmann. Domain Walls, Droplets and Barriers in Two-Dimensional Ising Spin Glasses. In W. Janke, editor, Rugged Free Energy Landscapes, page 67, Berlin, 2007. Springer.
- [13] A. K. Hartmann. Ground states of two-dimensional ising spin glasses: Fast algorithms, recent developments and a ferromagnet-spin glass mixture. J. Stat. Phys., 144:519–540, 2011.
- [14] A. K. Hartmann and H. Rieger. Optimization Algorithms in Physics. Wiley-VCH, Weinheim, 2001.
- [15] I. Bieche, R. Maynard, R. Rammal, and J. P. Uhry. On the ground states of the frustration model of a spin glass by a matching method of graph theory. J. Phys. A: Math. Gen., 13:2553, 1980.
- [16] F. Barahona. On the computational complexity of Ising spin glass models. J. Phys. A, 15:3241, 1982.
- [17] C. K. Thomas and A. A. Middleton. Matching Kasteleyn cities for spin glass ground states. Phys. Rev. B, 76:220406, 2007.
- [18] G. Pardella and F. Liers. Exact ground states of large two-dimensional planar Ising spin glasses. Phys. Rev. E, 78:056705, 2008.
- [19] B. A. Cipra. The Ising Model Is NP–Complete. SIAM News, 33, 2000.
- [20] O. Melchert and A. K. Hartmann. Scaling behavior of domain walls at the ferromagnet to spin-glass transition. Phys. Rev. B, 79:184402, 2009.
- [21] K. Binder. Finite size scaling analysis of ising model block distribution functions. Z. Phys. B, 43:119, 1981.
- [22] W. L. McMillan. Domain-wall renormalization-group study of the two-dimensional random Ising model. Phys. Rev. B, 29:4026–4029, 1984. A summary of this article is available at papercore.org, see http://www.papercore.org/McMillan1984.
- [23] K. H. Fischer and J. A. Hertz. Spin Glasses. Cambridge University Press, Cambridge, 1991.
- [24] A. P. Young, editor. Spin glasses and random fields. World Scientific, Singapore, 1998.
- [25] S. Bastea, A. Burkov, C. Moukarzel, and P. M. Duxbury. Combinatorial optimization methods in disordered systems. Comp. Phys. Comm., 121-122:199, 1999. Proceedings of the Europhysics Conference on Computational Physics CCP 1998.
- [26] H. Rieger. Application of exact combinatorial optimization algorithms to the physics of disordered systems. Comp. Phys. Comm., 147:702, 2002.
- [27] A. K. Hartmann and U. Nowak. Universality in three dimensional random-field ground states. Eur. Phys. J. B, 7:105–109, 1999.
- [28] J.-C. Anglès d’Auriac and N. Sourlas. The 3d random field Ising model at zero temperature. Europhys. Lett., 39(5):473, 1997.
- [29] A. K. Hartmann and A. P. Young. Specific-heat exponent of random-field systems via ground-state calculations. Phys. Rev. B, 64:214419, 2001.
- [30] E. T. Seppälä, A. M. Pulkkinen, and M. J. Alava. Percolation in three-dimensional random field Ising magnets. Phys. Rev. B, 66:144403, 2002. A summary of this article is available at papercore.org, see http://www.papercore.org/Seppälä2002.
- [31] D. Stauffer and A. Aharony. Introduction to Percolation Theory. Taylor and Francis, London, 1994.
- [32] C. R. Shalizi and J. P. Crutchfield. Computational Mechanics: Pattern and Prediction, Structure and Simplicity. J. Stat. Phys., 104:817–878, 2001.
- [33] J. P. Crutchfield and D. P. Feldman. Regularities unseen, randomness observed: Levels of entropy convergence. CHAOS, 13:25–54, 2003.
- [34] D. Kandel, R. Ben-Av, and E. Domany. Cluster Monte Carlo dynamics for the fully frustrated Ising model. Phys. Rev. B, 45:4700–4709, 1992. A summary of this article is available at papercore.org, see http://www.papercore.org/Kandel1992.
- [35] A. K. Hartmann. Practical Guide to Computer Simulations. World Scientific, Singapore, 2009.
- [36] J. P. Crutchfield and K. Young. Inferring statistical complexity. Phys. Rev. Lett., 63:105–108, 1989.
- [37] J. Wilms, M. Troyer, and F. Verstraete. Mutual information in classical spin models. J. Stat. Mech., 2011(10):P10011, 2011.
- [38] K. Binder and W. Kob. Glassy Materials and Diosordred Solids. World Scientific, Singapore, 2011.
- [39] G. Biroli, J.-P. Bouchaud, , T. S. Cavagna, A. Grigera, and P. Verrocchio. Thermodynamic signature of growing amorphous order in glass-forming liquids. Nature Physics, 4:771–775, 2008.