Simulation of the nonlinear mechanical response of materials with explicit representation of microstructural features is extremely challenging. These models typically involve a very large number of degrees of freedom, and are prone to convergence difficulties when searching for roots to nonlinear equilibrium equations. We focus on an idealized material model that is motivated by the microstructure of synthetic nacre: individual ‘bricks’ (representing ceramic platelets) interact through nonlinear cohesive springs (representing a small volume fraction of polymer that bonds the platelets). The model simulates composite fracture through rupture of the cohesive springs. The problem is cast in terms of energy minimization and is essentially described by ‘nearest neighbor’ interactions. The principal focus of this paper is to illustrate the computational gains achievable by the strategic marriage of robust, global Monte Carlo minimization algorithms to the graphics processing unit architecture, and to describe how they were realized on the Nvidia GPU. Results comparing the computation times for graphics processing unit and central processing unit implementations demonstrate that a new adaptive version of the simulated annealing algorithm yields a speedup of approximately 5 times, whereas the graphics processing unit implementation yields a speed-up of about 16 times over conventional four-core central processing unit implementations. The resulting speed enhancement for adaptive graphics processing unit minimization of a factor of 80 enables a far broader range of simulations than has previously been possible. Simulations involving as many as 300,000 bricks can be performed in hours, as compared to weeks required by central processing unit implementation. Many aspects of this approach are translatable to other physical problems involving energy minimization in systems with large numbers of degrees of freedom.