The Ising model is an important model in statistical physics, with over 10,000 papers published on the topic. This model assumes binary variables and only local pairwise interactions between neighbouring nodes. Inference for the general Ising model is NP-hard; this includes tasks such as calculating the partition function, finding a lowest-energy (ground) state and computing marginal probabilities. Past approaches have proceeded by working with classes of tractable Ising models, such as Ising models defined on a planar graph. For such models, the partition function and ground state can be computed exactly in polynomial time by establishing a correspondence with perfect matchings in a related graph. In this thesis we continue this line of research. In particular we simplify previous inference algorithms for the planar Ising model. The key to our construction is the complementary correspondence between graph cuts of the model graph and perfect matchings of its expanded dual. We show that our exact algorithms are effective and efficient on a number of real-world machine learning problems. We also investigate heuristic methods for approximating ground states of non-planar Ising models. We show that in this setting our approximative algorithms are superior than current state-of-the-art methods.

Thesis (Ph.D.) -- Mississippi State University. Computational Engineering. / Title from title screen. Includes bibliographical references.

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-06-28T18:00:24Z No. of bitstreams: 1 TeseMASA.pdf: 2952958 bytes, checksum: 7fd6c19f5dbc2b559baf911ba11a9787 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-07T18:17:28Z (GMT) No. of bitstreams: 1 TeseMASA.pdf: 2952958 bytes, checksum: 7fd6c19f5dbc2b559baf911ba11a9787 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-08-07T18:17:35Z (GMT) No. of bitstreams: 1 TeseMASA.pdf: 2952958 bytes, checksum: 7fd6c19f5dbc2b559baf911ba11a9787 (MD5) / Made available in DSpace on 2017-08-07T18:31:02Z (GMT). No. of bitstreams: 1 TeseMASA.pdf: 2952958 bytes, checksum: 7fd6c19f5dbc2b559baf911ba11a9787 (MD5) Previous issue date: 2012-10-11 / Fundação de Amparo à Pesquisa do Estado do Amazonas (FAPEAM) / In this work, we present the results obtained for Ising models and Heisenberg spin 1/2, where two and three-dimensional, with disorder or frustration. We apply effective field theory associated with the Operator Differential Technique - TOD. A new formulation of this technique has enabled the development of a numerical implementation where the coefficients are now constructed fully automatically. This allowed growing up the number N of spins of the cluster and thus observe the behavior of the system when it tends to the real case (N→∞), which is bounded by the computational time needed to carry out all operations. We apply this methodology to study the Ising model with random field - RFIM, where we use three probability distributions for the field: bimodal, gaussian and gaussian double-peaked. The phase-diagrams were obtained in t - h plane for the cases Ferromagnetic-F and Antiferromagnetic-AF with the aid of Maxwell's construction procedure (equality of the free energies at line phase transition) identifying the tricritical point - PTC in each case. We present two proposals for obtaining the free energy, and in one of them it was possible to study the behavior of the thermodynamic properties in the regions of 1st and 2nd order. For a second application of numerical implementation, we use the quantum model of anisotropic Heisenberg spin (1/2) (with anisotropy parameter Δ), which lies in the particular cases that are important: one-dimensional Ising (Δ=1) and isotropic Heisenberg (Δ=0), being applied in the study of magnetic thin films formed by monolayers where the presence of free surfaces substantially alters the system behavior. We simulate this case, the spin frustration of considering interactions between the first (J₁) and second (J₂) interactions with neighboring F and AF respectively, being related by the parameter α=J₁/J₂. We studied the influence of increasing the dimensionality of the system, made by increasing the number of layers (L) of the film, the behavior of the phase diagram α - t. Finally, we apply the relations of the Renormalization Group in the Heisenberg Hamiltonian for a thin film to study the behavior of critical exponents as a function of parameters such as temperature and number of layers. / Apresentamos nesta tese os resultados obtidos para os modelos de Ising e Heisenberg de spin 1/2, nos casos bi e tridimensional, com desordem ou frustração. Aplicamos a teoria de campo efetivo associada à Técnica do Operador Diferencial - TOD. Uma nova formulação desta técnica permitiu o desenvolvimento de um algoritmo onde os coeficientes são agora construídos de forma totalmente automática. Isso possibilitou crescermos o número N de spins do aglomerado e assim observar o comportamento do sistema quando tende para o caso real (N→∞), tendo como limite o tempo computacional necessário para efetivar todas as operações. Aplicamos esta metodologia no estudo do modelo de Ising com campo aleatório - RFIM, onde utilizamos três distribuições de probabilidade para o campo: bimodal, gaussiana e gaussiana duplo-pico. Os diagramas de fase no plano t - h foram obtidos para os casos Ferromagnético-F e Antiferromagnético-AF com auxílio do procedimento da construção de Maxwell (igualdade das energias livres na linha de transição de fase), identificando o ponto tricrítico - PTC em cada caso. Apresentamos duas propostas para obtenção da energia livre, sendo que em uma delas foi possível o estudo do comportamento das propriedades termodinâmicas nas regiões de 1ª e 2ª ordem. Para uma segunda aplicação dessa implementação numérica, utilizamos o modelo de Heisenberg quântico de spin 1/2 anisotrópico (com parâmetro de anisotropia Δ), que recai nos casos particulares importantes que são: Ising unidimensional (Δ=1) e Heisenberg isotrópico (Δ=0), sendo aplicado no estudo de filmes finos magnéticos formados por monocamadas onde a presença de superfícies livres altera consideravelmente o comportamento do sistema. Simulamos nesse caso, a frustração dos spins considerando interações entre primeiros (J₁) e segundos (J₂) vizinhos com interações F e AF respectivamente, estando relacionados através do parâmetro α=J₁/J₂. Estudamos a influência do aumento da dimensionalidade do sistema, feito através do acréscimo no número de camadas (L) do filme, no comportamento do diagrama de fases t - α. Para finalizar, aplicamos as relações do Grupo de Renormalização no Hamiltoniano Heisenberg para um filme fino para o estudo do comportamento dos expoentes críticos em função de parâmetros como a temperatura e número de camadas.

Made available in DSpace on 2016-05-17T16:51:00Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-12-20. Added 1 bitstream(s) on 2016-05-17T16:54:18Z : No. of bitstreams: 1 000855902.pdf: 1054323 bytes, checksum: 8821779dca285c4030ab51997270af7e (MD5) / Revisamos o método de Monte Carlo aplicado a modelos de spin discretos e a uma teoria de campos escalar na rede, com espcial ênfase no algoritmo de Metropolis. Inicialmente consideramos um modelo de spins de Ising com interacções de longo alcance em uma rede complexa de mundo pequeno. Em vista da não extensividade do modelo, generalizamos o modelo de Metropolis para a termoestatística não extensiva de Tsallis. Simulações numéricas são implementadas com o algoritmo generalizado para redes bi- e tridimensionais. A seguir, revisamos o método de regularização na rede para a teoria quântica de um campo escalar autointeragente. Empregamos o algoritmo de Metropolis para simular a teoria nar ede e estudamos o comportamento das constantes de acoplamento renormalizadas quártica and sêxtupla em função da constante de acoplamento não renormalizada. Apresentamos resultados de simulações para redes Euclideanas em duas e três dimensões nos regimes de acoplamento intermediário e forte / We review the application of the Monte Carlo method to a discrete spin model and to a scalar field theory on the lattice with special emphasis on the Metropolis algorithm. Initially we consider an Ising spin model with long range interactions on a complex small world network. In view of the nonextensive nature of the model, we have have generalized the Metropolis algorithm to the Tsallis nonextensive thermostatistics. Numerical simulations with the generalized algorithm are implemented for two-and three-dimensional lattices. Next we review the lattice regularization method for the quantum theory of a selfinteracting scalar field. We use the Metropolis algorithm to simulate the theory on the lattice and study the behavior of the renormalized quartic and sextic coupling constants as a function of the unrenormalized coupling constant. Results of simulations are presented for Euclidean lattices in two and three dimensions at intermediate and strong couplings

Neste trabalho estudamos um ferromagneto de Ising em uma rede bidimensional. Consideramos fases espacialmente anisotrópicas em um modelo de Ising dipolar frustrado na presença de um campo externo, em uma aproximação de campo médio e também em outros dois modelos com configurações mais simples das paredes de domínio. Em um primeiro momento, foi estudado o modelo de Ising em uma rede quadrada, no qual há a competição entre a interação de troca, a qual favorece um estado uniforme, e a interação dipolar, que favorece a presença de domínios. Os domínios de equilíbrio observados têm a estrutura de listras ou faixas simétricas, quebrando a isotropia espacial do sistema. Na segunda parte do estudo, é adicionado ao sistema um campo magnético externo, o qual é homogêneo; este campo favorece uma orientação preferencial das faixas, gerando um padrão de modulação de faixas assimétricas. Este campo externo está também em competição com a interação dipolar, favorecendo o estado uniforme. Experimentos recentes [1, 2] mostram uma transição de fases inversa uniforme-moduladauniforme, a medida que se diminui a temperatura para um campo externo fixo. Resultados analíticos em um modelo de Ginzburg-Landau [3] mostram a curva reentrante campo vs. temperatura, perto do ponto crítico, onde o modelo é válido. No estudo a campo nulo, analisamos o comportamento do sistema com o aumento da intensidade relativa entre os parâmetros de interação de troca e dipolar δ. Observamos que, para grandes valores de δ, o sistema apresenta uma grande metaestabilidade e o período de modulação das faixas cresce fortemente próximo `a transição. Na região de δ grande, o semi-período da modulação h obedece `a relação h(δ) ∼ eδ/2, de acordo com estudos realizados em [4]. No estudo com campo externo, através de uma análise numérica, mostramos que os graus de liberdade internos das paredes de domínio são essenciais para a presença da transição inversa. Também mostramos que em um modelo com paredes estreitas não é observada a reentrância (transição inversa). Em altas temperaturas os graus de liberdade adicionais do modelo de campo médio aumentam a entropia do sistema, reduzindo a energia livre. Em temperaturas baixas as paredes de domínio tornam-se mais estreitas e com os correspondentes graus de liberdade congelados, o que, eventualmente, induz a transição inversa para a fase homogênea. Mostramos também que, aumentando o campo magnético a uma temperatura constante, a largura da faixa aumenta muito rapidamente ao aproximar-se da linha de campo crítico, e diverge na transição. Nosso objetivo é obter o diagrama de fases para o modelo de Ising deste sistema, e explicar a origem da transição inversa observada em filmes magnéticos ultrafinos com anisotropia perpendicular. / In this work we study a Ising ferromagnet on a two-dimensional lattice. We consider spatially anisotropic phases in a dipolar frustrated Ising model in an external field in a mean field approximation and also in two other models with a simpler configuration of the domain walls. At first, was studied the Ising model on a square lattice, in which there is the competition between the exchange interaction, which favors a uniform state, and the dipolar interaction, which favors the presence of domains. The equilibrium domains have the structure of symmetric stripes or bands, breaking the isotropy of the system. In the second part of the study, it is added to the system an external magnetic field, which is homogeneous; this field favors a preferential orientation of stripes, generating a modulation pattern of asymmetric bands. This external field is also in competition with the dipolar interaction, favoring the uniform state. Recent experiments [1, 2] show an inverse phase transition uniform-modulated-uniform, as the temperature is reduced at fixed external field. Analytical results in a Ginzburg- Landau model [3] show the reentrant curve field vs. temperature, near the critical point, where the model is valid. In the zero field case, we analyzed the system behavior with growing values of the parameter δ, which measures the relative intensity between the exchange and dipolar interactions. We observe that, for large values of δ, the system displays a large metastability and the modulation period of stripes grows strongly near the transition. In the region of large δ , the half-period of modulation h, follows the relation h(δ) ∼ eδ/2, according to studies conducted in [4]. At high temperatures the additional degrees of freedom of mean-field model increase the entropy of the system, reducing the free energy of the stripe phase. At low temperatures the domain walls becomes narrower and the corresponding degrees of freedom frozen, which eventually induces an inverse transition to the homogenous phase. We also show that, for growing external field at constant temperature, the stripe width grows strongly when approaching the critical field line, and diverges at the transition. Our goal is to obtain the phase diagram for the Ising model on this system, and explain the origin of the inverse symmetry breaking transition observed in ultrathin magnetic films with perpendicular anisotropy.

O modelo bidimensional de Ising com interações competitivas entre um termo ferromagnético, de curto alcance, e outro antiferromagnético, de longo alcance, é o modelo mais simples para descrever filmes finos e materiais magnéticos quase-bidimensionais. A frustração, introduzida pelo termo dipolar no Hamiltoniano, é responsável por uma dinâmica lenta e uma fenomenologia rica. Neste trabalho estudamos as propriedades de equilíbrio e fora de equilíbrio do modelo Ising-Dipolar para certos valores de (j (parâmetro que mede a intensidade de uma interação frente à outra). Calculamos várias quantidades termodinâmicas, como energia livre, entropia e calor específico, e determinamos a natureza da transição de fase para δ = 1. Verificamos que a relaxação da função de autocorrelação spin-spin, acima da temperatura de transição, é do tipo stretch exponentíal. Além disso, realizamos experiências de não equilíbrio, como coarsening, em que verificamos a presença de uma fase metaestável, e histerese, em que conseguimos super-resfriar a fase desordenada para δ= 2. / The two-dimensional lsing model with competitive short-range ferromagnetic and longrange antiferromagnetic interactions, is the simplest model to describe thin films and quasitwo- dimensional magnetic materiaIs. The frustration, introduced by the dipolar term in the Hamiltonian, is responsible for a slow down in the dynamics and a rich phenomenology. ln this work we studied the equilibrium and off-equilibrium properties of the lsing-Dipolar model for certain <5values (parameter that measures the intensity between the two terms). We calculated several thermodynamical quantities, as free energy, entropy and specific heat, and checked the nature of the phase transition for δ = 1. We verified that the relaxation of the spin-spin autocorrelation function, above the transition temperature, is stretch exponential. Moreover, we did out of equilibrium experiments, as coarsening, where we verified the presence of a metastable phase, and hysteresis, where we supercooled the disordered phase for δ= 2.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas. Programa de Pós-graduação em Física / Made available in DSpace on 2012-10-24T07:03:35Z (GMT). No. of bitstreams: 1 263951.pdf: 1104154 bytes, checksum: 3a8c63467c9f5e9ae09671339ab75c35 (MD5) / Estudamos o comportamento crítico de uma liga binária Fe1-xRux em uma estrutura BCC e com desordem temperada para concentrações de rutênio x=0% e x=6%. Este estudo é realizado em uma abordagem de Monte Carlo e com dados analisados através do método de repesagem dos múltiplos histogramas. Através de uma análise de escala de tamanho ?nito feita para várias grandezas termodinâmicas, obtemos estimativas para os expoentes críticos a, ß, ? e ? e temperatura crítica do modelo. Nossos resultados para x=0% estão em excelente acordo com os resultados para o modelo de Ising tridimensional sem desordem presentes na literatura, como era esperado. Também mostramos que nossas estimativas dos expoentes críticos para x=6% são consistentes com os valores reportados para a linha de transição entre as fases paramagnética e ferromagnética de ambos modelos de Ising aleatoriamente diluído e ±J. Comparamos o comportamento da magnetização em função da temperatura com o obtido por Paduani e Branco (2008), con?rmando o resultado obtido por campo médio. Entretanto, a comparação da temperatura crítica obtida neste trabalho com a medida experimental sugere que o modelo (inicialmente obtido de uma abordagem de campo médio) precissa ser ser modicado.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas. Programa de Pós-graduação em Física / Made available in DSpace on 2012-10-22T11:35:10Z (GMT). No. of bitstreams: 1 246861.pdf: 534401 bytes, checksum: aff6ab2309addcd73150f8373cea5465 (MD5) / Demonstramos neste trabalho que a modulação dos parâmetros de interação dos hamiltonianos de Ising e Blume-Capel, segundo seqüências aperiódicas, pode ocasionar uma mudança de classe de universalidade na rede de Bethe e oscilação log-periódica da magnetização. Observamos possível mudança do expoente crítico da magnetização ß em relação a seu valor em sistemas homogêneos ou periódicos. Esta mudança não ocorre quando a seqüência de Fibonacci é usada. Na seqüência de duplicação de período caracterizamos o expoente ß como uma função da razão JA/JB. Na seqüência de Rudin-Shapiro obtemos evidências de que esta aperiodicidade causa mudança na classe de universalidade do sistema.

Neste trabalho estudamos um ferromagneto de Ising em uma rede bidimensional. Consideramos fases espacialmente anisotrópicas em um modelo de Ising dipolar frustrado na presença de um campo externo, em uma aproximação de campo médio e também em outros dois modelos com configurações mais simples das paredes de domínio. Em um primeiro momento, foi estudado o modelo de Ising em uma rede quadrada, no qual há a competição entre a interação de troca, a qual favorece um estado uniforme, e a interação dipolar, que favorece a presença de domínios. Os domínios de equilíbrio observados têm a estrutura de listras ou faixas simétricas, quebrando a isotropia espacial do sistema. Na segunda parte do estudo, é adicionado ao sistema um campo magnético externo, o qual é homogêneo; este campo favorece uma orientação preferencial das faixas, gerando um padrão de modulação de faixas assimétricas. Este campo externo está também em competição com a interação dipolar, favorecendo o estado uniforme. Experimentos recentes [1, 2] mostram uma transição de fases inversa uniforme-moduladauniforme, a medida que se diminui a temperatura para um campo externo fixo. Resultados analíticos em um modelo de Ginzburg-Landau [3] mostram a curva reentrante campo vs. temperatura, perto do ponto crítico, onde o modelo é válido. No estudo a campo nulo, analisamos o comportamento do sistema com o aumento da intensidade relativa entre os parâmetros de interação de troca e dipolar δ. Observamos que, para grandes valores de δ, o sistema apresenta uma grande metaestabilidade e o período de modulação das faixas cresce fortemente próximo `a transição. Na região de δ grande, o semi-período da modulação h obedece `a relação h(δ) ∼ eδ/2, de acordo com estudos realizados em [4]. No estudo com campo externo, através de uma análise numérica, mostramos que os graus de liberdade internos das paredes de domínio são essenciais para a presença da transição inversa. Também mostramos que em um modelo com paredes estreitas não é observada a reentrância (transição inversa). Em altas temperaturas os graus de liberdade adicionais do modelo de campo médio aumentam a entropia do sistema, reduzindo a energia livre. Em temperaturas baixas as paredes de domínio tornam-se mais estreitas e com os correspondentes graus de liberdade congelados, o que, eventualmente, induz a transição inversa para a fase homogênea. Mostramos também que, aumentando o campo magnético a uma temperatura constante, a largura da faixa aumenta muito rapidamente ao aproximar-se da linha de campo crítico, e diverge na transição. Nosso objetivo é obter o diagrama de fases para o modelo de Ising deste sistema, e explicar a origem da transição inversa observada em filmes magnéticos ultrafinos com anisotropia perpendicular. / In this work we study a Ising ferromagnet on a two-dimensional lattice. We consider spatially anisotropic phases in a dipolar frustrated Ising model in an external field in a mean field approximation and also in two other models with a simpler configuration of the domain walls. At first, was studied the Ising model on a square lattice, in which there is the competition between the exchange interaction, which favors a uniform state, and the dipolar interaction, which favors the presence of domains. The equilibrium domains have the structure of symmetric stripes or bands, breaking the isotropy of the system. In the second part of the study, it is added to the system an external magnetic field, which is homogeneous; this field favors a preferential orientation of stripes, generating a modulation pattern of asymmetric bands. This external field is also in competition with the dipolar interaction, favoring the uniform state. Recent experiments [1, 2] show an inverse phase transition uniform-modulated-uniform, as the temperature is reduced at fixed external field. Analytical results in a Ginzburg- Landau model [3] show the reentrant curve field vs. temperature, near the critical point, where the model is valid. In the zero field case, we analyzed the system behavior with growing values of the parameter δ, which measures the relative intensity between the exchange and dipolar interactions. We observe that, for large values of δ, the system displays a large metastability and the modulation period of stripes grows strongly near the transition. In the region of large δ , the half-period of modulation h, follows the relation h(δ) ∼ eδ/2, according to studies conducted in [4]. At high temperatures the additional degrees of freedom of mean-field model increase the entropy of the system, reducing the free energy of the stripe phase. At low temperatures the domain walls becomes narrower and the corresponding degrees of freedom frozen, which eventually induces an inverse transition to the homogenous phase. We also show that, for growing external field at constant temperature, the stripe width grows strongly when approaching the critical field line, and diverges at the transition. Our goal is to obtain the phase diagram for the Ising model on this system, and explain the origin of the inverse symmetry breaking transition observed in ultrathin magnetic films with perpendicular anisotropy.

Made available in DSpace on 2014-06-11T19:25:30Z (GMT). No. of bitstreams: 0 Previous issue date: 2003-02Bitstream added on 2014-06-13T20:33:12Z : No. of bitstreams: 1 wanzeller_wg_me_ift.pdf: 1104414 bytes, checksum: f6829a4e95fac397804869f7aa9967e9 (MD5) / A teoria da percolação de clusters é empregada para estudar a transição de fase magnética no modelo de Ising bidimensional utilizando simulações de Monte Carlo. A teoria da percolação é de interesse para problemas de transições de fase em matéria condensada e em biologia e química. Mais recentemente, conceitos da teoria de percolação de clusters têm sido invocados em estudos da transição de desconfinamento dos quarks e glúons a altas temperaturas na Cromadinâmica quântica. A dissertação apresenta uma revisão sucinta, mas autocontida, dos princípios básicos da teoria da percolação e sua relação aos fenômenos críticos, e dos principais métodos de Monte Carlo. Alguns resultados obtidos não são novos, no entanto, todos códigos numéricos para as simulações e estimativas de erros são originais. / Abstracts: Cluster percolation theory is employed to study the magnetic phase transition in the two dimensional Ising model using Monte Carlo simulations. Percolation theory is of interest in problems of phase transitions in condensed matter physics, and in biology and chemistry. More recently, concepts of percolation theory have been invoked in studies of quark-gluon deconfinement at high temperatures in quantum Chromodynamics. The dissertation presents a brief, but selfcontained review of the basic principles of percolation theory, the relation of percolation to critical phenomena, and discusses the main Monte Carlo methods. Some of the results obtained are to new, but all numerical codes employed in the simulations and erro estimate are original.