| 1. |
- Alava, Mikko, et al.
(författare)
-
Circumspect descent prevails in solving random constraint satisfaction problems
- 2008
-
Ingår i: Proceedings of the National Academy of Sciences of the United States of America. - : Proceedings of the National Academy of Sciences. - 0027-8424 .- 1091-6490. ; 105:40, s. 15253-15257
-
Tidskriftsartikel (refereegranskat)abstract
- We study the performance of stochastic local search algorithms for random instances of the K-satisfiability (K-SAT) problem. We present a stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by never going upwards in energy. ChainSAT is a focused algorithm in the sense that it focuses on variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large K-SAT instances almost surely in linear time, up to high clause-to-variable ratios a; for example, for K = 4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.
|
|
| 2. |
- Hosseinzadeh Delandar, Arash, 1982-
(författare)
-
Numerical Modeling of Plasticity in FCC Crystalline Materials Using Discrete Dislocation Dynamics
- 2015
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Plasticity in crystalline solids is controlled by the microscopic line defects known as “dislocations”. Decisive role of dislocations in crystal plasticity in addition to fundamentals of plastic deformation are presented in the current thesis work. Moreover, major features of numerical modeling method “Discrete Dislocation Dynamics (DDD)” technique are described to elucidate a powerful computational method used in simulation of crystal plasticity.First part of the work is focused on the investigation of strain rate effect on the dynamic deformation of crystalline solids. Single crystal copper is chosen as a model crystal and discrete dislocation dynamics method is used to perform numerical uniaxial tensile test on the single crystal at various high strain rates. Twenty four straight dislocations of mixed character are randomly distributed inside a model crystal with an edge length of 1 µm subjected to periodic boundary conditions. Loading of the model crystal with the considered initial dislocation microstructure at constant strain rates ranging from 103 to 105s1 leads to a significant strain rate sensitivity of the plastic flow. In addition to the flow stress, microstructure evolution of the sample crystal demonstrates a considerable strain rate dependency. Furthermore, strain rate affects the strain induce microstructure heterogeneity such that more heterogeneous microstructure emerges as strain rate increases.Anisotropic characteristic of plasticity in single crystals is investigated in the second part of the study. Copper single crystal is selected to perform numerical tensile tests on the model crystal along two different loading directions of [001] and [111] at two high strain rates. Effect of loading orientation on the macroscopic behavior along with microstructure evolution of the model crystal is examined using DDD method. Investigation of dynamic response of single crystal to the mechanical loading demonstrates a substantial effect of loading orientation on the flow stress. Furthermore, plastic anisotropy is observed in dislocation density evolution such that more dislocations are generated as straining direction of single crystal is changed from [001] to [111] axis. Likewise, strain induced microstructure heterogeneity displays the effect of loading direction such that more heterogeneous microstructure evolve as single crystal is loaded along [111] direction. Formation of slip bands and consequently localization of plastic deformation are detected as model crystal is loaded along both directions.
|
|
| 3. |
- Lemoy, Remi, et al.
(författare)
-
Local search methods based on variable focusing for random K-satisfiability
- 2015
-
Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics. - 1539-3755 .- 1550-2376. ; 91:1, s. 013305-
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce variable focused local search algorithms for satisfiabiliity problems. Usual approaches focus uniformly on unsatisfied clauses. The methods described here work by focusing on random variables in unsatisfied clauses. Variants are considered where variables are selected uniformly and randomly or by introducing a bias towards picking variables participating in several unsatistified clauses. These are studied in the case of the random 3-SAT problem, together with an alternative energy definition, the number of variables in unsatisfied constraints. The variable-based focused Metropolis search (V-FMS) is found to be quite close in performance to the standard clause-based FMS at optimal noise. At infinite noise, instead, the threshold for the linearity of solution times with instance size is improved by picking preferably variables in several UNSAT clauses. Consequences for algorithmic design are discussed.
|
|
| 4. |
- Moilanen, Carolina, et al.
(författare)
-
Influence of strain rate, temperature and fatigue on the radial compression behaviour of Norway spruce
- 2017
-
Ingår i: Holzforschung. - : Walter de Gruyter GmbH. - 0018-3830 .- 1437-434X. ; 71:6, s. 505-514
-
Tidskriftsartikel (refereegranskat)abstract
- A dynamic elastoplastic compression model of Norway spruce for virtual computer optimization of mechanical pulping processes was developed. The empirical wood behaviour was fitted to a Voigt-Kelvin material model, which is based on quasi static compression and high strain rate compression tests (QSCT and HSRT, respectively) of wood at room temperature and at high temperature (80-100 degrees C). The effect of wood fatigue was also included in the model. Wood compression stress-strain curves have an initial linear elastic region, a plateau region and a densification region. The latter was not reached in the HSRT. Earlywood (EW) and latewood (LW) contributions were considered separately. In the radial direction, the wood structure is layered and can well be modelled by serially loaded layers. The EW model was a two part linear model and the LW was modelled by a linear model, both with a strain rate dependent term. The model corresponds well to the measured values and this is the first compression model for EW and LW that is based on experiments under conditions close to those used in mechanical pulping.
|
|
| 5. |
- Wu, Lu-Lu, et al.
(författare)
-
Witness of unsatisfiability for a random 3-satisfiability formula
- 2013
-
Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics. - 1539-3755 .- 1550-2376. ; 87:5, s. 052807-
-
Tidskriftsartikel (refereegranskat)abstract
- The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density alpha exceeds a critical value alpha(s) approximate to 4.267. Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density alpha > 19. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when a scales at least linearly with the variable number N, but the focused local search algorithm works for clause density alpha > cN(b) with b approximate to 0.59 and prefactor c approximate to 8. The exponent b can be further decreased by enlarging the single parameter S of the focused local search algorithm.
|
|
| 6. |
- Zeng, Hong-Li, et al.
(författare)
-
Maximum Likelihood Reconstruction for Ising Models with Asynchronous Updates
- 2013
-
Ingår i: Physical Review Letters. - 0031-9007 .- 1079-7114. ; 110:21, s. 210601-
-
Tidskriftsartikel (refereegranskat)abstract
- We describe how the couplings in an asynchronous kinetic Ising model can be inferred. We consider two cases: one in which we know both the spin history and the update times and one in which we know only the spin history. For the first case, we show that one can average over all possible choices of update times to obtain a learning rule that depends only on spin correlations and can also be derived from the equations of motion for the correlations. For the second case, the same rule can be derived within a further decoupling approximation. We study all methods numerically for fully asymmetric Sherrington-Kirkpatrick models, varying the data length, system size, temperature, and external field. Good convergence is observed in accordance with the theoretical expectations.
|
|
| 7. |
- Zeng, Hong-Li, et al.
(författare)
-
Network inference using asynchronously updated kinetic Ising model
- 2011
-
Ingår i: Physical Review E. - 1539-3755. ; 83:4, s. 041135-
-
Tidskriftsartikel (refereegranskat)abstract
- Network structures are reconstructed from dynamical data by respectively naive mean field (nMF) and Thouless-Anderson-Palmer (TAP) approximations. TAP approximation adds simple corrections to the nMF approximation, taking into account the effect of the focused spin on itself via its influence on other neighboring spins. For TAP approximation, we use two methods to reconstruct the network: (a) iterative method; (b) casting the inference formula to a set of cubic equations and solving it directly. We investigate inference of the asymmetric Sherrington-Kirkpatrick (aS-K) model using asynchronous update. The solutions of the set of cubic equations depend on temperature T in the aS-K model, and a critical temperature T-c approximate to 2.1 is found. The two methods for TAP approximation produce the same results when the iterative method is convergent. Compared to nMF, TAP is somewhat better at low temperatures, but approaches the same performance as temperature increases. Both nMF and TAP approximation reconstruct better for longer data length L, but for the degree of improvement, TAP performs better than nMF.
|
|
