# Application of Polynomial Algorithms to a Random Elastic Medium

## Models

Fortunately, recent works of Henley, Kondev and their co-workers provided us with a large class of just such models whose degrees of freedom are described in terms of colors, tilings (dimer) and loops, precisely the natural language for considering network flow optimizations. More importantly, these models all permit a solid-on-solid (SOS) representation whose large-scale height fluctuations are governed by a few elastic constants and a locking potential that is periodic in heights. As an illustration, we consider here a fully-packed loop (FPL) model defined on a honeycomb lattice. All configurations of occupied bonds which form closed loops and cover every site exactly once are allowed, as in the example of Fig.1(a). The corresponding SOS surface is a (111)-interface of a simple cubic lattice constructed as follows. Define integer heights at the centers of the hexagons of this honeycomb lattice then orient all bonds of the resulting triangular lattice connecting the centers such that elementary triangles pointing upward are circled clockwise; assign $`+1`$ to the difference of neighboring heights along the oriented bonds if a loop is crossed and $`2`$ otherwise. This yields single-valued heights up to an overall constant.

We introcude quenched disorder via random bond weights on the honeycomb lattice, chosen independently and uniformly from integers in the interval \[$`w`$, $`w`$\] with $`w=500`$. The total energy is the sum of the bond weights along all loops and strings. The FPL model is shown to be equivalent to an array of fluxlines confined in a plane with the heights corresponding to the displacement fields of the fluxlines. The SOS surface described above can be viewed as an elastic surface embedded in a $`3d`$ random potential that is periodic in heights modulo 3 since the smallest “step” of the surface is three. The coarse-grained effective Hamiltonian becomes

$$H=𝑑𝐫\left[\frac{K}{2}\left(h(𝐫)\right)^2u\mathrm{cos}\left(\frac{2\pi }{3}h(𝐫)\gamma (𝐫)\right)\right],$$
(1)   
where the random bond weights enter as random phase $`\gamma (𝐫)`$. Note also both $`K`$ and $`u`$ depend on the disorder strength $`w`$ since it is the only energy scale in the problem. This is the well studied model for charge-density waves (CDW).

Dislocations are added to the FPL model by “violating” the fully-packed constraint. One dislocation pair is an open string in an otherwise fully-packed system as shown in Fig.1(b). The height change along any path encircling one end of the string is the Burgers charge $`\pm 3`$ of a dislocation so that the heights become multi-valued. Note that the configurations with and without a dislocation pair only differ along a domain “wall”, as shown in Fig.1(c). Dislocations with higher Burgers charges $`\pm 6`$ can also be created by introducing holes instead of strings.

## Algorithms

It turns out that the ground states of the disordered FPL model can be obtained via polynomial algorithms. A general description of such an optimization problem is given by the so-called linear programming which is to identify a set of variables minimizing a linear objective function subject to a set of linear constraints. Most physical problems are restricted to integer-valued variables. Such an integer optimization problem in general is nondeterministic polynomial (NP) which implies that polynomial and exact algorithms are unlikely to be found. However, for a special class of problems where the linear constraints other than the upper and lower bounds on the variables can be interpreted as “flow conservation” at the nodes of a graph while the variables are identified with the flows on the edges of the graph, the optimization problem is polynomial. Recent applications mentioned above fall into this class. Since most textbooks contain details on the proof of this result and existing C++ codes for these polynomial algorithms can be found in the LEDA library, we shall only discuss how to transform the search for the ground states into an integer min-cost-flow problem on a suitably designed graph. The min-cost-flow problem is to find the flow pattern of minimum total cost for sending a specific amount of flow from a given node $`s`$ to another given node $`t`$ in a graph $`G`$ in which the flow $`x`$ on every edge has an upper bound $`u_b`$ and a lower bound $`l_b`$ ($`l_bxu_b`$) as well as a unit cost $`c`$. The total cost is of course given by summing $`cx`$ over all edges in $`G`$.

Suppose that the bipartite honeycomb lattice with periodic boundary conditions contains $`2N`$ sites which we divide into two sublattices of $`N`$ A-sites and $`N`$ B-sites. We can construct a graph $`G`$ as follows. In addition to all sites and bonds of the honeycomb lattice, this graph contains two extra sites, denoted as $`s`$ (the source) and $`t`$ (the sink), and extra $`2N`$ bonds (the leads). All bonds of the honeycomb lattice are directed from A-sites to B-sites with $`l_b=0`$, $`u_b=1`$, and $`c`$ being the corresponding random bond weight, while the remaining $`N`$ in-leads are directed from $`s`$ to A-sites and $`N`$ out-leads from B-sites to $`t`$ with $`l_u=1`$, $`u_b=2`$, and $`c=0`$ for all $`2N`$ leads. Therefore, the ground state energy of a loop configuration with or without defects is equivalent to the minimum-cost flow if loops and strings are identified with bonds on the honeycomb lattice that have flow (note that the flow value on these bonds must be either zero or unity). Simple inspection shows that this identification can indeed be made with the above choice of bounds if the amount of flow sustained between $`s`$ and $`t`$, with flow conservation on all other nodes, is between $`N`$ and $`2N`$ units.

Given the amount of flow sustained, the minimum-cost-flow algorithm establishes the flow pattern of the minimum cost. Various interesting physical situations can be simulated by simple variations. $`2N`$ units of flow, for example, lead to the ground state of fully-packed loops (no dislocations). $`2N1`$ units of flow, on the other hand, give the ground state with one dislocation pair without a priori fixing the pair location. Keeping $`2N1`$ units of flow while changing $`u_b`$ of a particular in-lead and out-lead from $`2`$ to $`1`$ simulates a fixed pair of dislocations with the Burgers charges $`\pm 3`$. If using $`2N2`$ units of flow instead and changing $`u_b`$ of a particular in-lead and out-lead from $`2`$ to $`0`$, we obtain a pair of dislocations (holes) with the Burgers charges $`\pm 6`$ at fixed locations. Clearly, dislocations of any desired density can be achieved by suitably varying the flow between $`N`$ and $`2N`$ units. Moreover, introducing another extra link from $`t`$ back to $`s`$ with a negative unit cost $`E_c`$ allows us to determine the optimal amount of flow sustained (thus the optimal dislocation density) with $`E_c`$ being the core energy. This last simple variation results in the min-cost-circulation problem in network flow optimization.

## Numerical results

For a given disorder realization, two ground-state energies, $`E_1`$ and $`E_0`$, were obtained respectively for cases with and without dislocations. The defect energy $`E_dE_1E_0`$ was then determined. Various $`L\times L`$ sample sizes with $`L=12,24,48,96,192`$, and $`384`$ ($`480`$ for optimized defects) were simulated with at least $`10^4`$ disorder averages for each size.

We first describe our results for a single dislocation pair where the core energy $`E_c`$ is set to zero. The elastic constant of an elastic medium can be measured in various ways by observing its response to perturbations. Here we perturb the system with a fixed dislocation pair (large-scale topological excitation). The defect energy $`E_d`$ in this case is the elastic energy cost $`E_{ela}`$ which according to the elastic theory should scale as $`E_{ela}Kb^2/2\pi \mathrm{ln}(L)`$. This is indeed consistent with our numerical results shown in Fig.2, and the elastic constant $`K`$ is found to be $`126(2)`$ and $`125(1)`$ from dislocations pairs with the the Burgers charges $`\pm 3`$ and $`\pm 6`$ respectively. When the dislocation pair is allowed to be placed optimally, $`E_d`$ also contains the disorder energy gain $`E_{dis}`$ in addition to $`E_{ela}`$, i.e., $`E_d=E_{ela}+E_{dis}`$. As shown clearly in Fig. 2, $`E_{dis}`$ dominates over $`E_{ela}`$ resulting in the negative $`E_d`$, and moreover, $`E_{dis}`$ drops faster than $`\mathrm{ln}(L)`$. Detailed analysis showed that the numerical results are consistent with the theoretical prediction $`E_{dis}\mathrm{ln}^{3/2}(L)`$, a result independent of the disorder strength $`w`$. Therefore the elastic phase of large systems is unstable to dislocation pairs. With no restrictions on their number, dislocations will proliferate thereby driving the elastic constant $`K`$ to zero.

We now discuss our results on multiple dislocations which are summarized in Fig. 3. It is indeed clear from the inset that the elastic energy cost $`E_{ela}`$ for introducing a pair of fixed dislocations into the state where the number of dislocations is already optimal is independent of the separation of the fixed pair implying a zero elastic constant $`K`$. This is consistent with the result on a related model. The relation between the optimal dislocation density $`\rho `$ and the core energy $`E_c`$ is, however, found to be

$$\rho e^{(E_c/E_0)^\alpha }$$
(2)   
with $`\alpha =0.74(3)`$. This exponent remains elusive to us at the present.

## Conclusion and Outlook

In conclusion, we studied the energetics of dislocation pairs in a $`2d`$ random elastic medium by applying polynomial algorithms to $`2d`$ disordered FPL model and found the elastic phase is unstable against the proliferation of dislocations, and thus providing evidence against the formation of a Bragg glass in two dimensions.

Further exploration of these disordered $`2d`$ lattice models with SOS representations will certainly help to address the fundamental issue of how non-random critical systems are affected by quenched disorder since most of these non-random models are critical. For example, the non-random FPL model flows to the densely-packed loop (DPL) fixed point of the O(n) model upon the perturbation of holes. How this DPL fixed point get modified by bond randomness (if at all) can now be examined by using non-bipartite matching algorithms. Another exciting extension of these polynomial algorithms to compute the energetics of dislocation loops in $`3d`$ random elastic media is now also feasible. Compared with the past few years in which polynomial and exact algorithms have been productively explored, it is fair to say that the next few years will see a rapid closing-in on a class of even NP-hard disordered systems which allow polynomial and approximant algorithms with near-optimal solutions of guaranteed bounds.

We thank J. Kondev, C.L. Henley and A.A. Middleton for useful discussions. Part of this work is done in collaboration with D.S. Fisher which is also gratefully acknowledged.