Damped Arrow-Hurwicz algorithm for sphere packing

DOI10.1016/J.JCP.2016.11.047zbMATH Open1378.65121arXiv1605.05473OpenAlexW2400330803MaRDI QIDQ680083FDOQ680083

Authors: Pierre Degond, Marina A. Ferreira, Sebastien Motsch 

Publication date: 22 January 2018

Published in: Journal of Computational Physics (Search for Journal in Brave)

Abstract: We consider algorithms that, from an arbitrarily sampling of $N$ spheres (possibly overlapping), find a close packed configuration without overlapping. These problems can be formulated as minimization problems with non-convex constraints. For such packing problems, we observe that the classical iterative Arrow-Hurwicz algorithm does not converge. We derive a novel algorithm from a multi-step variant of the Arrow-Hurwicz scheme with damping. We compare this algorithm with classical algorithms belonging to the class of linearly constrained Lagrangian methods and show that it performs better. We provide an analysis of the convergence of these algorithms in the simple case of two spheres in one spatial dimension. Finally, we investigate the behaviour of our algorithm when the number of spheres is large.

Full work available at URL: https://arxiv.org/abs/1605.05473

Recommendations

• Algorithms for congruent sphere packing and applications
• A Multi-sphere Scheme for 2D and 3D Packing Problems
• Algorithm for random close packing of spheres with periodic boundary conditions
• A heuristic algorithm for a packing problem of equal spheres in a sphere
• Iterated dynamic neighborhood search for packing equal circles on a sphere
• Algorithms of optimal ball packing into ellipsoids
• scientific article; zbMATH DE number 3849991
• A local search-based method for sphere packing problems
• scientific article; zbMATH DE number 5629935
• Particle packing algorithm for SPH schemes

zbMATH Keywords

nonconvex minimization problemnon-overlapping constraintssphere packing problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Ordinary Differential Equations with Applications
• An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimizing the packing of cylinders into a rectangular container: A nonlinear approach
• A literature review on circle and sphere packing problems: models and methodologies
• A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics.
• Disk packing in a square: a new global optimization approach
• Tilt Stability of a Local Minimum
• Title not available (Why is that?)
• Dynamic numerical investigation of random packing for spherical and nonconvex particles
• Physical Perspectives on the Global Optimization of Atomic Clusters
• A time-stepping scheme for inelastic collisions. Numerical handling of the nonoverlapping constraint.
• Crowd motion from the granular standpoint
• Efficient Global Geometry Optimization of Atomic and Molecular Clusters
• A contextualized historical analysis of the Kuhn-Tucker theorem in nonlinear programming: The impact of World War II

Cited In (4)

• The Arrow-Hurwicz iterative finite element method for the stationary thermally coupled incompressible magnetohydrodynamics flow
• A new continuum theory for incompressible swelling materials
• A micro-macro hybrid model with application for material and pedestrian flow
• Convergence analysis of a heuristic collective sphere packing algorithm

Uses Software

• BacSim

This page was built for publication: Damped Arrow-Hurwicz algorithm for sphere packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q680083)