BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Alexander K. Hartmann

Alexander K. Hartmann appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
cond-mat.dis-nncond-mat.stat-mechphysics.comp-phphysics.data-anphysics.soc-phComputational Complexityastro-ph.IMBiological PhysicsBiomoleculeshep-latMachine Learningmath.PRQuantitative MethodsSocial and Information Networksstat.OT

Catalog footprint

What is connected

36works
15topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

36 published item(s)

preprint2026arXiv

The distribution of the maximum of independent resetting Brownian motions

The probability distribution of the maximum $M_t$ of a single resetting Brownian motion (RBM) of duration $t$ and resetting rate $r$, properly centred and scaled, is known to converge to the standard Gumbel distribution of the classical extreme value theory. This Gumbel law describes the typical fluctuations of $M_t$ around its average $\sim \ln (r t)$ for large $t$ on a scale of $O(1)$. Here we compute the large-deviation tails of this distribution when $M_t = O(t)$ and show that the large-deviation function has a singularity where the second derivative is discontinuous, signalling a dynamical phase transition. Then we consider a collection of independent RBMs with initial (and resetting) positions uniformly distributed with a density $ρ$ over the negative half-line. We show that the fluctuations in the initial positions of the particles modify the distribution of $M_t$. The average over the initial conditions can be performed in two different ways, in analogy with disordered systems: (i) the annealed case where one averages over all possible initial conditions and (ii) the quenched case where one considers only the contributions coming from typical initial configurations. We show that in the annealed case, the limiting distribution of the maximum is characterized by a new scaling function, different from the Gumbel law but the large-deviation function remains the same as in the single particle case. In contrast, for the quenched case, the limiting (typical) distribution remains Gumbel but the large-deviation behaviors are new and nontrivial. Our analytical results, both for the typical as well as for the large-deviation regime of $M_t$, are verified numerically with extremely high precision, down to $10^{-250}$ for the probability density of $M_t$.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Simulated annealing, optimization, searching for ground states

The chapter starts with a historical summary of first attempts to optimize the spin glass Hamiltonian, comparing it to recent results on searching largest cliques in random graphs. Exact algorithms to find ground states in generic spin glass models are then explored in Section 1.2, while Section 1.3 is dedicated to the bidimensional case where polynomial algorithms exist and allow for the study of much larger systems. Finally Section 1.4 presents a summary of results for the assignment problem where the finite size corrections for the ground state can be studied in great detail.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Large-deviations of the SIR model around the epidemic threshold

We numerically study the dynamics of the SIR disease model on small-world networks by using a large-deviation approach. This allows us to obtain the probability density function of the total fraction of infected nodes and of the maximum fraction of simultaneously infected nodes down to very small probability densities like $10^{-2500}$. We analyze the structure of the disease dynamics and observed three regimes in all probability density functions, which correspond to quick mild, quick extremely severe and sustained severe dynamical evolutions, respectively. Furthermore, the mathematical rate functions of the densities are investigated. The results indicate that the so called large-deviation property hold for the SIR model. Finally, we measured correlations with other quantities like the duration of an outbreak or the peak position of the fraction of infections, also in the rare regions which are not accessible by standard simulation techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Critical behavior of the Anderson model on the Bethe lattice via a large-deviation approach

We present a new large-deviation approach to investigate the critical properties of the Anderson model on the Bethe lattice close to the localization transition in the thermodynamic limit. Our method allows us to study accurately the distribution of the local density of states (LDoS) down to very small probability tails as small as $10^{-50}$ which are completely out of reach for standard numerical techniques. We perform a thorough analysis of the functional form and of the tails of the probability distribution of the LDoS which yields for the first time a direct, transparent, and precise estimation of the correlation volume close to the Anderson transition. Such correlation volume is found to diverge exponentially when the localization is approached from the delocalized regime, in a singular way that is in agreement with the analytic predictions of the supersymmetric treatment.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Phase transition in the bipartite z-matching

We study numerically the maximum $z$-matching problems on ensembles of bipartite random graphs. The $z$-matching problems describes the matching between two types of nodes, users and servers, where each server may serve up to $z$ users at the same time. By using a mapping to standard maximum-cardinality matching, and because for the latter there exists a polynomial-time exact algorithm, we can study large system sizes of up to $10^6$ nodes. We measure the capacity and the energy of the resulting optimum matchings. First, we confirm previous analytical results for bipartite regular graphs. Next, we study the finite-size behaviour of the matching capacity and find the same scaling behaviour as before for standard matching, which indicates the universality of the problem. Finally, we investigate for bipartite Erdős-Rényi random graphs the saturability as a function of the average degree, i.e., whether the network allows as many customers as possible to be served, i.e. exploiting the servers in an optimal way. We find phase transitions between unsaturable and saturable phases. These coincide with a strong change of the running time of the exact matching algorithm, as well with the point where a minimum-degree heuristic algorithm starts to fail.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Replica-symmetry breaking for directed polymers

Directed polymers on 1+1 dimensional lattices coupled to a heat bath at temperature $T$ are studied numerically for three ensembles of the site disorder. In particular correlations of the disorder as well as fractal patterning are considered. Configurations are directly sampled in perfect thermal equilibrium for very large system sizes with up to $N=L^2= 32768 \times 32768 \approx 10^{9}$ sites. The phase-space structure is studied via the distribution of overlaps and hierarchical clustering of configurations. One ensemble shows a simple behavior like a ferromagnet. The other two ensembles exhibit indications for complex behavior reminiscent of multiple replica-symmetry breaking. Also results for the ultrametricity of the phase space and the phase transition behavior of $P(q)$ when varying the temperature $T$ are studied. In total, the present model ensembles offer convenient numerical accesses to comprehensively studying complex behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Asymptotic behavior of the length of the longest increasing subsequences of random walks

We numerically estimate the leading asymptotic behavior of the length $L_{n}$ of the longest increasing subsequence of random walks with step increments following Student's $t$-distribution with parameter in the range $1/2 \leq ν\leq 5$. We find that the expected value $\mathbb{E}(L_{n}) \sim n^θ\ln{n}$ with $θ$ decreasing from $θ(ν=1/2) \approx 0.70$ to $θ(ν\geq 5/2) \approx 0.50$. For random walks with distribution of step increments of finite variance ($ν> 2$), this confirms previous observation of $\mathbb{E}(L_{n}) \sim \sqrt{n}\ln{n}$ to leading order. We note that this asymptotic behavior (including the subleading term) resembles that of the largest part of random integer partitions under the uniform measure and that, curiously, both random variables seem to follow Gumbel statistics. We also provide more refined estimates for the asymptotic behavior of $\mathbb{E}(L_{n})$ for random walks with step increments of finite variance.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

How many longest increasing subsequences are there?

We study the entropy $S$ of longest increasing subsequences (LIS), i.e., the logarithm of the number of distinct LIS. We consider two ensembles of sequences, namely random permutations of integers and sequences drawn i.i.d.\ from a limited number of distinct integers. Using sophisticated algorithms, we are able to exactly count the number of LIS for each given sequence. Furthermore, we are not only measuring averages and variances for the considered ensembles of sequences, but we sample very large parts of the probability distribution $p(S)$ with very high precision. Especially, we are able to observe the tails of extremely rare events which occur with probabilities smaller than $10^{-600}$. We show that the distribution of the entropy of the LIS is approximately Gaussian with deviations in the far tails, which might vanish in the limit of long sequences. Further we propose a large-deviation rate function which fits best to our observed data.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large deviations of a random walk model with emerging territories

We study an agent-based model of animals marking their territory and evading adversarial territory in one dimension, with respect to the distribution of the size of the resulting territories. In particular, we use sophisticated sampling methods to determine it over a large part of territory sizes, including atypically small and large configurations, which occur with probability of less than $10^{-30}$. We find hints for the validity of a large deviation principle, the shape of the rate function for the right tail of the distribution and insight into the structure of atypical realizations.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Optimal paths of non-equilibrium stochastic fields: the Kardar-Parisi-Zhang interface as a test case

Atypically large fluctuations in macroscopic non-equilibrium systems continue to attract interest. Their probability can often be determined by the optimal fluctuation method (OFM). The OFM brings about a conditional variational problem, the solution of which describes the "optimal path" of the system which dominates the contribution of different stochastic paths to the desired statistics. The OFM proved efficient in evaluating the probabilities of rare events in a host of systems. However, theoretically predicted optimal paths were observed in stochastic simulations only in diffusive lattice gases, where the predicted optimal density patterns are either stationary, or travel with constant speed. Here we focus on the one-point height distribution of the paradigmatic Kardar-Parisi-Zhang interface. Here the optimal paths, corresponding to the distribution tails at short times, are intrinsically non-stationary and can be predicted analytically. Using the mapping to the directed polymer in a random potential at high temperature, we obtain "snapshots" of the optimal paths in Monte-Carlo simulations which probe the tails with an importance sampling algorithm. For each tail we observe a very narrow "tube" of height profiles around a single optimal path which agrees with the analytical prediction. The agreement holds even at long times, supporting earlier assertions of the validity of the OFM in the tails well beyond the weak-noise limit.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Percolation of Fortuin-Kasteleyn clusters for the random-bond Ising model

We apply generalisations of the Swendson-Wang and Wolff cluster algorithms, which are based on the construction of Fortuin-Kasteleyn clusters, to the three-dimensional $\pm 1$ random-bond Ising model. The behaviour of the model is determined by the temperature $T$ and the concentration $p$ of negative (anti-ferromagnetic) bonds. The ground state is ferromagnetic for $0 \le p<p_c$, and a spin glass for $p_c < p \le 0.5$ where $p_c \simeq 0.222$. We investigate the percolation transition of the Fortuin-Kasteleyn clusters as function of temperature. Except for $p=0$ the Fortuin-Kasteleyn percolation transition occurs at a higher temperature than the magnetic ordering temperature. This was known before for $p=1/2$ but here we provide evidence for a difference in transition temperatures even for $p$ arbitrarily small. Furthermore, for all values of $p>0$, our data suggest that the percolation transition is universal, irrespective of whether the ground state exhibits ferromagnetic or spin-glass order, and is in the universality class of standard percolation. This shows that correlations in the bond occupancy of the Fortuin-Kasteleyn clusters are irrelevant, except for $p=0$ where the clusters are tied to Ising correlations so the percolation transition is in the Ising universality class.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Probing the large deviations of the Kardar-Parisi-Zhang equation at short time with an importance sampling of directed polymers in random media

The one-point distribution of the height for the continuum Kardar-Parisi-Zhang (KPZ) equation is determined numerically using the mapping to the directed polymer in a random potential at high temperature. Using an importance sampling approach, the distribution is obtained over a large range of values, down to a probability density as small as $10^{-1000}$ in the tails. The short time behavior is investigated and compared with recent analytical predictions for the large-deviation forms of the probability of rare fluctuations, showing a spectacular agreement with the analytical expressions. The flat and stationary initial conditions are studied in the full space, together with the droplet initial condition in the half-space.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convex Hulls of Multiple Random Walks: A Large-Deviation Study

We study the polygons governing the convex hull of a point set created by the steps of $n$ independent two-dimensional random walkers. Each such walk consists of $T$ discrete time steps, where $x$ and $y$ increments are i.i.d. Gaussian. We analyze area $A$ and perimeter $L$ of the convex hulls. We obtain probability densities for these two quantities over a large range of the support by using a large-deviation approach allowing us to study densities below $10^{-900}$. We find that the densities exhibit a universal scaling behavior as a function of $A/T$ and $L/\sqrt{T}$, respectively. As in the case of one walker ($n=1$), the densities follow Gaussian distributions for $L$ and $\sqrt{A}$, respectively. We also obtained the rate functions for the area and perimeter, rescaled with the scaling behavior of their maximum possible values, and found limiting functions for $T \rightarrow \infty$, revealing that the densities follow the large-deviation principle. These rate functions can be described by a power law for $n \rightarrow \infty$ as found in the $n=1$ case. We also investigated the behavior of the averages as a function of the number of walks $n$ and found good agreement with the predicted behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Practical Introduction to Clustering Data

Data clustering is an approach to seek for structure in sets of complex data, i.e., sets of "objects". The main objective is to identify groups of objects which are similar to each other, e.g., for classification. Here, an introduction to clustering is given and three basic approaches are introduced: the k-means algorithm, neighbour-based clustering, and an agglomerative clustering method. For all cases, C source code examples are given, allowing for an easy implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Convex Hulls of Random Walks: Large-Deviation Properties

We study the convex hull of the set of points visited by a two-dimensional random walker of T discrete time steps. Two natural observables that characterize the convex hull in two dimensions are its perimeter L and area A. While the mean perimeter <L> and the mean area <A> have been studied before, analytically and numerically, and exact results are known for large T (Brownian motion limit), little is known about the full distributions P(A) and P(L). In this paper, we provide numerical results for these distributions. We use a sophisticated large-deviation approach that allows us to study the distributions over a larger range of the support, where the probabilities P(A) and P(L) are as small as 10^{-300}. We analyze (open) random walks as well as (closed) Brownian bridges on the two-dimensional discrete grid as well as in the two-dimensional plane. The resulting distributions exhibit, for large T, a universal scaling behavior (independent of the details of the jump distributions) as a function of A/T and L/\sqrt{T}, respectively. We are also able to obtain the rate function, describing rare events at the tails of these distributions, via a numerical extrapolation scheme and find a linear and square dependence as a function of the rescaled perimeter and the rescaled area, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fragmentation properties of two-dimensional Proximity Graphs considering random failures and targeted attacks

The pivotal quality of proximity graphs is connectivity, i.e. all nodes in the graph are connected to one another either directly or via intermediate nodes. These types of graphs are robust, i.e., they are able to function well even if they are subject to limited removal of elementary building blocks, as it may occur for random failures or targeted attacks. Here, we study how the structure of these graphs is affected when nodes get removed successively until an extensive fraction is removed such that the graphs fragment. We study different types of proximity graphs for various node removal strategies. We use different types of observables to monitor the fragmentation process, simple ones like number and sizes of connected components, and more complex ones like the hop diameter and the backup capacity, which is needed to make a network N-1 resilient. The actual fragmentation turns out to be described by a second order phase transition. Using finite-size scaling analyses we numerically assess the threshold fraction of removed nodes, which is characteristic for the particular graph type and node deletion scheme, that suffices to decompose the underlying graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Large-deviation properties of resilience of power grids

We study the distributions of the resilience of power flow models against transmission line failures via a so-called backup capacity. We consider three ensembles of random networks and in addition, the topology of the British transmission power grid. The three ensembles are Erdős-Rényi random graphs, Erdős-Rényi random graphs with a fixed number of links, and spatial networks where the nodes are embedded in a two dimensional plane. We investigate numerically the probability density functions (pdfs) down to the tails to gain insight in very resilient and very vulnerable networks. This is achieved via large-deviation techniques which allow us to study very rare values which occur with probability densities below $10^{-160}$. We find that the right tail of the pdfs towards larger backup capacities follows an exponential with a strong curvature. This is confirmed by the rate function which approaches a limiting curve for increasing network sizes. Very resilient networks are basically characterized by a small diameter and a large power sign ratio. In addition, networks can be made typically more resilient by adding more links.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Non-equilibrium evolution of window overlaps in spin glasses

We investigate numerically the time dependence of "window" overlaps in a three-dimensional Ising spin glass below its transition temperature after a rapid quench. Using an efficient GPU implementation, we are able to study large systems up to lateral length $L=128$ and up to long times of $t=10^8$ sweeps. We find that the data scales according to the ratio of the window size $W$ to the non-equilibrium coherence length $ξ(t)$. We also show a substantial change in behavior if the system is run for long enough that it globally equilibrates, i.e. $ξ(t) \approx L/2$, where $L$ is the lattice size. This indicates that the local behavior of a spin glass depends on the spin configurations (and presumably also the bonds) far away. We compare with similar simulations for the Ising ferromagnet. Based on these results, we speculate on a connection between the non-equilibrium dynamics discussed here and averages computed theoretically using the "metastate".

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes

The Traveling Salesperson problem asks for the shortest cyclic tour visiting a set of cities given their pairwise distances and belongs to the NP-hard complexity class, which means that with all known algorithms in the worst case instances are not solveable in polynomial time, i.e., the problem is hard. Though that does not mean, that there are not subsets of the problem which are easy to solve. To examine numerically transitions from an easy to a hard phase, a random ensemble of cities in the Euclidean plane given a parameter σ, which governs the hardness, is introduced. Here, a linear programming approach together with suitable cutting planes is applied. Such algorithms operate outside the space of feasible solutions and are often used in practical application but rarely studied in physics so far. We observe several transitions. To characterize these transitions, scaling assumptions from continuous phase transitions are applied

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Score distributions of gapped multiple sequence alignments down to the low-probability tail

Assessing the significance of alignment scores of optimally aligned DNA or amino acid sequences can be achieved via the knowledge of the score distribution of random sequences. But this requires obtaining the distribution in the biologically relevant high-scoring region, where the probabilities are exponentially small. For gapless local alignments of infinitely long sequences this distribution is known analytically to follow a Gumbel distribution. Distributions for gapped local alignments and global alignments of finite lengths can only be obtained numerically. To obtain result for the small-probability region, specific statistical mechanics-based rare-event algorithms can be applied. In previous studies, this was achieved for pairwise alignments. They showed that, contrary to results from previous simple sampling studies, strong deviations from the Gumbel distribution occur in case of finite sequence lengths. Here we extend the studies to the for practical applications in Molecular Biology much more relevant case of multiple sequence alignments with gaps. We study the distributions of scores over a large range of the support, reaching probabilities as small as 10^-160, for global and local (sum-of-pair scores) multiple alignments. We find that even after suitable rescaling, eliminating the sequence-length dependence, the distributions for multiple alignment differ from the pairwise alignment case. Furthermore, we also show that the previously discussed Gaussian correction to the Gumbel distribution needs to be refined, also for the case of pairwise alignments.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Ageing at the Spin-Glass/Ferromagnet Transition: Monte Carlo Simulation using GPUs

We study the the non-equilibrium ageing behaviour of the +/-J Edwards-Anderson model in three dimensions for samples of size up to N=128^3 and for up to 10^8 Monte Carlo sweeps. In particular we are interested in the change of the ageing when crossing from the spin-glass phase to the ferromagnetic phase. The necessary long simulation times are reached by employing a CUDA-based GPU implementation, which allows for single-spin flip times as small as 8ps. We measure typical spin glass correlation functions in space and time to determine the growing length scale and extract the constituting exponents. We observe a clear signature of the disorder-driven equilibrium transition in the non-equilibrium behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Exact ground states of one-dimensional long-range random-field Ising magnets

We investigate the one-dimensional long-range random-field Ising magnet with Gaussian distribution of the random fields. In this model, a ferromagnetic bond between two spins is placed with a probability $p \sim r^{-1-σ}$, where $r$ is the distance between these spins and $σ$ is a parameter to control the effective dimension of the model. Exact ground states at zero temperature are calculated for system sizes up to $L = 2^{19}$ via graph theoretical algorithms for four different values of $σ\in \{0.25,0.4,0.5,1.0\}$ while varying the strength $h$ of the random fields. For each of these values several independent physical observables are calculated, i.e., magnetization, Binder parameter, susceptibility and a specific-heat-like quantity. The ferromagnet-paramagnet transitions at critical values $h_c(σ)$ as well as the corresponding critical exponents are obtained. The results agree well with theory and interestingly we find for $σ= 1/2$ the data is compatible with a critical random-field strength $h_c > 0$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Large-deviation properties of resilience of transportation networks

Distributions of the resilience of transport networks are studied numerically, in particular the large-deviation tails. Thus, not only typical quantities like average or variance but the distributions over the (almost) full support can be studied. For a proof of principle, a simple transport model based on the edge-betweenness and three abstract yet widely studied random network ensembles are considered here: Erdoes-Renyi random networks with finite connectivity, small world networks and spatial networks embedded in a two-dimensional plane. Using specific numerical large-deviation techniques, probability densities as small as 10^(-80) are obtained here. This allows one to study typical but also the most and the least resilient networks. The resulting distributions fulfill the mathematical large-deviation principle, i.e., can be well described by rate functions in the thermodynamic limit. The analysis of the limiting rate function reveals that the resilience follows an exponential distribution almost everywhere. An analysis of the structure of the network shows that the most-resilient networks can be obtained, as a rule of thumb, by minimizing the diameter of a network. Also, trivially, by including more links a network can typically be made more resilient. On the other hand, the least-resilient networks are very rare and characterized by one (or few) small core(s) to which all other nodes are connected. In total, the spatial network ensemble turns out to be most suitable for obtaining and studying resilience of real mostly finite-dimensional networks. Studying this ensemble in combination with the presented large-deviation approach for more realistic, in particular dynamic transport networks appears to be very promising.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Diluted antiferromagnets in a field seem to be in a different universality class than the random-field Ising model

We perform large-scale Monte Carlo simulations using the Machta-Newman-Chayes algorithms to study the critical behavior of both the diluted antiferromagnet in a field with 30% dilution and the random-field Ising model with Gaussian random fields for different field strengths. Analytical calculations by Cardy [Phys. Rev. B 29, 505 (1984)] predict that both models map onto each other and share the same universality class in the limit of vanishing fields. However, a detailed finite-size scaling analysis of both the Binder cumulant and the two-point finite-size correlation length suggests that even in the limit of small fields, where the mapping is expected to work, both models are not in the same universality class. Therefore, care should be taken when interpreting (experimental) data for diluted antiferromagnets in a field using the random-field Ising model. Based on our numerical data, we present analytical expressions for the phase boundaries of both models.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized black-box large deviation simulations: High-precision work distributions for extreme non-equilibrium processes in large systems

The distributions of work for strongly non-equilibrium processes are studied using a very general form of a large-deviation approach, which allows one to study distributions of almost arbitrary quantities of interest for equilibrium, non-equilibrium stationary and even non-stationary processes. The method is applied to varying quickly the external field in a wide range B=3 <-> 0 for critical (T=2.269) two-dimensional Ising system of size LxL=128x128. To obtain free energy differences from the work distributions, they must be studied in ranges where the probabilities are as small as 10^{-240}, which is not possible using direct simulation approaches. By comparison with the exact free energies, which are available for this model for the zero-field case, one sees that the present approach allows one to obtain the free energy with a very high relative precision of 10^{-4}. This works well also for non-zero field, i.e., for a case where standard umbrella-sampling methods seem to be not so efficient to calculate free energies. Furthermore, for the present case it is verified that the resulting distributions of work for forward and backward process fulfill Crooks theorem with high precision. Finally, the free energy for the Ising magnet as a function of the field strength is obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sampling fractional Brownian motion in presence of absorption: a Markov Chain method

We study fractional Brownian motion (fBm) characterized by the Hurst exponent H. Using a Monte Carlo sampling technique, we are able to numerically generate fBm processes with an absorbing boundary at the origin at discrete times for a large number of 10^7 time steps even for small values like H=1/4. The results are compatible with previous analytical results that the distribution of (rescaled) endpoints y follow a power law P(y) y^ϕwith ϕ=(1-H)/H, even for small values of H. Furthermore, for the case H=0.5 we also study analytically the finite-length corrections to the first order, namely a plateau of P(y) for y->0 which decreases with increasing process length. These corrections are compatible with the numerical results.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Excitations in high-dimensional random-field Ising magnets

Domain walls and droplet-like excitation of the random-field Ising magnet are studied in d={3,4,5,6,7} dimensions by means of exact numerical ground-state calculations. They are obtained using the established mapping to the graph-theoretical maximum-flow problem. This allows to study large system sizes of more than five million spins in exact thermal equilibrium. All simulations are carried out at the critical point for the strength h of the random fields, h=h_c(d), respectively. Using finite-size scaling, energetic and geometric properties like stiffness exponents and fractal dimensions are calculated. Using these results, we test (hyper) scaling relations, which seem to be fulfilled below the upper critical dimension d_u=6. Also, for d<d_u, the stiffness exponent can be obtained from the scaling of the ground-state energy.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Phase transition for cutting-plane approach to vertex-cover problem

We study the vertex-cover problem which is an NP-hard optimization problem and a prototypical model exhibiting phase transitions on random graphs, e.g., Erdoes-Renyi (ER) random graphs. These phase transitions coincide with changes of the solution space structure, e.g, for the ER ensemble at connectivity c=e=2.7183 from replica symmetric to replica-symmetry broken. For the vertex-cover problem, also the typical complexity of exact branch-and-bound algorithms, which proceed by exploring the landscape of feasible configurations, change close to this phase transition from "easy" to "hard". In this work, we consider an algorithm which has a completely different strategy: The problem is mapped onto a linear programming problem augmented by a cutting-plane approach, hence the algorithm operates in a space OUTSIDE the space of feasible configurations until the final step, where a solution is found. Here we show that this type of algorithm also exhibits an "easy-hard" transition around c=e, which strongly indicates that the typical hardness of a problem is fundamental to the problem and not due to a specific representation of the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Random number generators for massively parallel simulations on GPU

High-performance streams of (pseudo) random numbers are crucial for the efficient implementation for countless stochastic algorithms, most importantly, Monte Carlo simulations and molecular dynamics simulations with stochastic thermostats. A number of implementations of random number generators has been discussed for GPU platforms before and some generators are even included in the CUDA supporting libraries. Nevertheless, not all of these generators are well suited for highly parallel applications where each thread requires its own generator instance. For this specific situation encountered, for instance, in simulations of lattice models, most of the high-quality generators with large states such as Mersenne twister cannot be used efficiently without substantial changes. We provide a broad review of existing CUDA variants of random-number generators and present the CUDA implementation of a new massively parallel high-quality, high-performance generator with a small memory load overhead.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Ultrametric probe of the spin-glass state in a field

We study the ultrametric structure of phase space of one-dimensional Ising spin glasses with random power-law interaction in an external random field. Although in zero field the model in both the mean-field and non-mean-field universality classes shows an ultrametric signature [Phys. Rev. Lett. 102, 037207 (2009)], when a field is applied ultrametricity seems only present in the mean-field regime. The results for the non-mean field case in an external field agree with data for spin glasses studied within the Migdal-Kadanoff approximation. Our results therefore suggest that the spin-glass state might be fragile to external fields below the upper critical dimension.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Bias in generation of random graphs

We study the statistical properties of the generation of random graphs according the configuration model, where one assigns randomly degrees to nodes. This model is often used, e.g., for the scale-free degree distribution ~d^gamma. For the efficient variant, where non-feasible edges are rejected and the construction of a graph continues, there exists a bias, which we calculate explicitly for a small sample ensemble. We find that this bias does not disappear with growing system size. This becomes also visible, e.g., for scale-free graphs when measuring quantities like the graph diameter. Hence, the efficient generation of general scale-free graphs with a very broad distribution (gamma <2) remains an open problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Critical behavior of the Random-Field Ising Magnet with long range correlated disorder

We study the correlated-disorder driven zero-temperature phase transition of the Random-Field Ising Magnet using exact numerical ground-state calculations for cubic lattices. We consider correlations of the quenched disorder decaying proportional to r^a, where r is the distance between two lattice sites and a<0. To obtain exact ground states, we use a well established mapping to the graph-theoretical maximum-flow problem, which allows us to study large system sizes of more than two million spins. We use finite-size scaling analyses for values a={-1,-2,-3,-7} to calculate the critical point and the critical exponents characterizing the behavior of the specific heat, magnetization, susceptibility and of the correlation length close to the critical point. We find basically the same critical behavior as for the RFIM with delta-correlated disorder, except for the finite-size exponent of the susceptibility and for the case a=-1, where the results are also compatible with a phase transition at infinitesimal disorder strength. A summary of this work can be found at the papercore database at www.papercore.org.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Critical behavior of the Random-Field Ising model at and beyond the Upper Critical Dimension

The disorder-driven phase transition of the RFIM is observed using exact ground-state computer simulations for hyper cubic lattices in d=5,6,7 dimensions. Finite-size scaling analyses are used to calculate the critical point and the critical exponents of the specific heat, magnetization, susceptibility and of the correlation length. For dimensions d=6,7 which are larger or equal to the assumed upper critical dimension, d_u=6, mean-field behaviour is found, i.e. alpha=0, beta=1/2, gamma=1, nu=1/2. For the analysis of the numerical data, it appears to be necessary to include recently proposed corrections to scaling at and beyond the upper critical dimension.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

RNA secondary structure design

We consider the inverse-folding problem for RNA secondary structures: for a given (pseudo-knot-free) secondary structure find a sequence that has that structure as its ground state. If such a sequence exists, the structure is called designable. We implemented a branch-and-bound algorithm that is able to do an exhaustive search within the sequence space, i.e., gives an exact answer whether such a sequence exists. The bound required by the branch-and-bound algorithm are calculated by a dynamic programming algorithm. We consider different alphabet sizes and an ensemble of random structures, which we want to design. We find that for two letters almost none of these structures are designable. The designability improves for the three-letter case, but still a significant fraction of structures is undesignable. This changes when we look at the natural four-letter case with two pairs of complementary bases: undesignable structures are the exception, although they still exist. Finally, we also study the relation between designability and the algorithmic complexity of the branch-and-bound algorithm. Within the ensemble of structures, a high average degree of undesignability is correlated to a long time to prove that a given structure is (un-)designable. In the four-letter case, where the designability is high everywhere, the algorithmic complexity is highest in the region of naturally occurring RNA.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

How to evaluate ground-state landscapes of disordered systems thermodynamical correctly

Ground states of three-dimensional EA Ising spin glasses are calculated for sizes up to 14^3 using a combination of a genetic algorithm and cluster-exact approximation. For each realization several independent ground states are obtained. Then, by applying ballistic search and T=0 Monte-Carlo simulations, it is ensured that each ground state appears with the same probability. Consequently, the results represent the true T=0 thermodynamic behavior. The distribution P(|q|) of overlaps is evaluated. For increasing size the width of P(|q|) and the fraction of the distribution below q_0=0.5 converge to zero. This indicates that for the infinite system P(|q|) is a delta function, in contrast to previous results. Thus, the ground-state behavior is dominated by few large clusters of similar ground states.

0 citations0 reviewsNo code linkedOpen access
preprint1997arXiv

Ground state structure of diluted antiferromagnets and random field systems

A method is presented for the calculation of all exact ground states of diluted antiferromagnets and random field systems in an arbitrary range of fields. It works by calculating all jump-fields B,Δwhere the system changes it's ground state. For each field value all degenerated ground states are represented by a set of (anti-) ferromagnetic clusters and a relation between the clusters. So a complete description of the ground state structure of these systems is possible. Systems are investigated up to size 48^3 on the whole field-range and up to 160^3 for some particular fields. The behavior of order parameters is investigated, the number of jumps is analyzed and the degree of degeneracy as functions of size and fields is calculated.

0 citations0 reviewsNo code linkedOpen access