umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the Ising problem and some matrix operations
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2007 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

The first part of the dissertation concerns the Ising problem proposed to Ernst Ising by his supervisor Wilhelm Lenz in the early 20s. The Ising model, or perhaps more correctly the Lenz-Ising model, tries to capture the behaviour of phase transitions, i.e. how local rules of engagement can produce large scale behaviour.

Two decades later Lars Onsager solved the Ising problem for the quadratic lattice without an outer field. Using his ideas solutions for other lattices in two dimensions have been constructed. We describe a method for calculating the Ising partition function for immense square grids, up to linear order 320 (i.e. 102400 vertices).

In three dimensions however only a few results are known. One of the most important unanswered questions is at which temperature the Ising model has its phase transition. In this dissertation it is shown that an upper bound for the critical coupling Kc, the inverse absolute temperature, is 0.29 for the tree dimensional cubic lattice.

To be able to get more information one has to use different statistical methods. We describe one sampling method that can use simple state generation like the Metropolis algorithm for large lattices. We also discuss how to reconstruct the entropy from the model, in order to obtain parameters as the free energy.

The Ising model gives a partition function associated with all finite graphs. In this dissertation we show that a number of interesting graph invariants can be calculated from the coefficients of the Ising partition function. We also give some interesting observations about the partition function in general and show that there are, for any N, N non-isomorphic graphs with the same Ising partition function.

The second part of the dissertation is about matrix operations. We consider the problem of multiplying them when the entries are elements in a finite semiring or in an additively finitely generated semiring. We describe a method that uses O(n3 / log n) arithmetic operations.

We also consider the problem of reducing n x n matrices over a finite field of size q using O(n2 / logq n) row operations in the worst case.

Ort, förlag, år, upplaga, sidor
Umeå: Matematik och matematisk statistik , 2007. , s. 7
Serie
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 37
Nyckelord [en]
Ising problem, phase tansition, matrix multiplicatoin, matrix inversion
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-1129ISBN: 987-91-7264-323-9 (tryckt)OAI: oai:DiVA.org:umu-1129DiVA, id: diva2:140305
Disputation
2007-05-31, MA 121, MIT, Umeå, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2007-05-10 Skapad: 2007-05-10 Senast uppdaterad: 2011-04-21Bibliografiskt granskad
Delarbeten
1. Series expansion for the density of states of the Ising and Potts models
Öppna denna publikation i ny flik eller fönster >>Series expansion for the density of states of the Ising and Potts models
Manuskript (Övrigt vetenskapligt)
Identifikatorer
urn:nbn:se:umu:diva-2344 (URN)
Tillgänglig från: 2007-05-10 Skapad: 2007-05-10 Senast uppdaterad: 2010-01-13Bibliografiskt granskad
2. Computation of the Ising partition function for two-dimensional square grids
Öppna denna publikation i ny flik eller fönster >>Computation of the Ising partition function for two-dimensional square grids
Visa övriga...
2004 (Engelska)Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 69, nr 4, s. 19-, artikel-id 046104Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

An improved method for obtaining the Ising partition function for $n \times n$ square grids with periodic boundary is presented. Our method applies results from Galois theory in order to split the computation into smaller parts and at the same time avoid the use of numerics. Using this method we have computed the exact partition function for the $320 \times 320$-grid, the $256 \times 256$-grid, and the $160 \times 160$-grid, as well as for a number of smaller grids. We obtain scaling parameters and compare with what theory prescribes.

Ort, förlag, år, upplaga, sidor
New York: American Physical Society through the American Institute of Physics, 2004
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:umu:diva-7684 (URN)10.1103/PhysRevE.69.046104 (DOI)
Tillgänglig från: 2008-01-11 Skapad: 2008-01-11 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
3. A Monte Carlo sampling scheme for the Ising model
Öppna denna publikation i ny flik eller fönster >>A Monte Carlo sampling scheme for the Ising model
Visa övriga...
2004 (Engelska)Ingår i: Journal of statistical physics, ISSN 0022-4715, E-ISSN 1572-9613, Vol. 114, nr 1-2, s. 455-480Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper we describe a Monte Carlo sampling scheme for the Ising model and similar discrete-state models. The scheme does not involve any particular method of state generation but rather focuses on a new way of measuring and using the Monte Carlo data. We show how to reconstruct the entropy S of the model, from which, e.g., the free energy can be obtained. Furthermore we discuss how this scheme allows us to more or less completely remove the effects of critical fluctuations near the critical temperature and likewise how it reduces critical slowing down. This makes it possible to use simple state generation methods like the Metropolis algorithm also for large lattices.

Ort, förlag, år, upplaga, sidor
Springer, 2004
Nyckelord
Monte Carlo methods, density of states, microcanonical
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:umu:diva-2346 (URN)10.1023/B:JOSS.0000003116.17579.5d (DOI)000186548300016 ()
Tillgänglig från: 2007-05-10 Skapad: 2007-05-10 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
4. The Multivariate Ising Polynomial of a Graph
Öppna denna publikation i ny flik eller fönster >>The Multivariate Ising Polynomial of a Graph
Manuskript (Övrigt vetenskapligt)
Identifikatorer
urn:nbn:se:umu:diva-2347 (URN)
Tillgänglig från: 2007-05-10 Skapad: 2007-05-10 Senast uppdaterad: 2010-01-13Bibliografiskt granskad
5. Fast multiplication of matrices over a finitely generated semiring
Öppna denna publikation i ny flik eller fönster >>Fast multiplication of matrices over a finitely generated semiring
2008 (Engelska)Ingår i: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 107, nr 6, s. 230-234Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper we show that n×n matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q2nω), where nω is the complexity for matrix multiplication over a ring (Strassen: ω<2.807, Coppersmith and Winograd: ω<2.376).

We first present a combinatorial matrix multiplication algorithm for the case of semirings with q elements, with complexity O(n3/log2qn), matching the best known methods in this class.

Next we show how the ideas used can be combined with those of the fastest known boolean matrix multiplication algorithms to give an O(q2nω) algorithm for matrices of, not necessarily finite, semirings with q additive generators.

For finite semirings our combinatorial algorithm is simple enough to be a practical algorithm and is expected to be faster than the O(q2nω) algorithm for matrices of practically relevant sizes.

Nyckelord
Matrix multiplication, Semirings
Identifikatorer
urn:nbn:se:umu:diva-2348 (URN)10.1016/j.ipl.2008.03.004 (DOI)
Tillgänglig från: 2007-05-10 Skapad: 2007-05-10 Senast uppdaterad: 2019-07-05Bibliografiskt granskad
6. On the complexity of matrix reduction over finite fields
Öppna denna publikation i ny flik eller fönster >>On the complexity of matrix reduction over finite fields
2007 (Engelska)Ingår i: Advances in Applied Mathematics, ISSN 0196-8858, Vol. 39, nr 4, s. 428-452Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We study matrix elimination over finite fields, and present an algorithm which is asymptotically faster than the traditional Gauss--Jordan elimination. We also bound the average and worst-case complexity for the problem, proving that our algorithm is close to being optimal, and show related concentration results for random matrices.

Next we present the results of a large computational study of the complexities for small matrices and fields. Here we determine the exact distribution of the complexity for matrices from $\mathrm{GL}_{n}(\mathbb{F}_{q})$, with $n$ an $q$ small

Finally we consider an extension of the problems studied for finite fields to finite semifields. We give a conjecture on the behaviour of a natural analogue of $\mathrm{GL}_{n}$ for semifields and prove this for a certain class of semifields.

Nyckelord
Matrix reduction, Complexity, Finite fields, Semifields
Identifikatorer
urn:nbn:se:umu:diva-7595 (URN)doi:10.1016/j.aam.2006.08.008 (DOI)
Tillgänglig från: 2008-01-11 Skapad: 2008-01-11 Senast uppdaterad: 2018-06-09Bibliografiskt granskad

Open Access i DiVA

fulltext(226 kB)722 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 226 kBChecksumma SHA-1
7dc8957e2aae4ab906f5a0eeaab09d5a7014c551248ffce58e16679afe6a5b55e17606ee
Typ fulltextMimetyp application/pdf

Av organisationen
Institutionen för matematik och matematisk statistik
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 722 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 956 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf