Damped Arrow-Hurwicz algorithm for sphere packing

DOI10.1016/J.JCP.2016.11.047MaRDI QIDQ680083zbMATH OpenOpenAlexFDO

Authors Pierre Degond, Marina A. Ferreira, Sebastien Motsch

Publication date 22 January 2018

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3148887 (Why is no real title available?)
• scientific article; zbMATH DE number 50133 (Why is no real title available?)
• scientific article; zbMATH DE number 1206370 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• scientific article; zbMATH DE number 3291743 (Why is no real title available?)
• A contextualized historical analysis of the Kuhn-Tucker theorem in nonlinear programming: The impact of World War II
• 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.
• A time-stepping scheme for inelastic collisions. Numerical handling of the nonoverlapping constraint.
• An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping
• Crowd motion from the granular standpoint
• Disk packing in a square: a new global optimization approach
• Dynamic numerical investigation of random packing for spherical and nonconvex particles
• Efficient Global Geometry Optimization of Atomic and Molecular Clusters
• Optimizing the packing of cylinders into a rectangular container: A nonlinear approach
• Ordinary Differential Equations with Applications
• Physical Perspectives on the Global Optimization of Atomic Clusters
• Tilt Stability of a Local Minimum

Cited in

(4)

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

Describes a project that uses

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)