Damped Arrow-Hurwicz algorithm for sphere packing
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 iter...
Tallennettuna:
| Päätekijät: | , , |
|---|---|
| Aineistotyyppi: | Artikkeli |
| Julkaistu: |
2016
|
| Aiheet: | |
| Linkit: | https://arxiv.org/abs/1605.05473 http://arxiv.org/abs/1605.05473 |
| Tagit: |
Ei tageja, Lisää ensimmäinen tagi!
|
| _version_ | 1879179270808403968 |
|---|---|
| author | Degond, Pierre Ferreira, Marina A. Motsch, Sébastien |
| author_browse | Degond, Pierre Ferreira, Marina A. Motsch, Sébastien |
| author_facet | Degond, Pierre Ferreira, Marina A. Motsch, Sébastien |
| author_sort | Degond, Pierre |
| building | arXiv |
| collection | Acceso abierto |
| description | 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. |
| doi_str_mv | 10.1016/j.jcp.2016.11.047 |
| first_indexed | 2026-10-16T01:29:57Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-1605.05473</identifier><datestamp>2026-06-04</datestamp>
<dc:title>Damped Arrow-Hurwicz algorithm for sphere packing</dc:title>
<dc:creator>Degond, Pierre</dc:creator>
<dc:creator>Ferreira, Marina A.</dc:creator>
<dc:creator>Motsch, Sébastien</dc:creator>
<dc:subject>Numerical Analysis</dc:subject>
<dc:description>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. </dc:description>
<dc:date>2016-05-18</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/1605.05473</dc:identifier>
<dc:identifier>http://arxiv.org/abs/1605.05473</dc:identifier>
<dc:identifier>doi:10.1016/j.jcp.2016.11.047</dc:identifier>
</oai_dc:dc> |
| id | arxiv-1605.05473 |
| institution | arXiv |
| last_indexed | 2026-10-16T01:29:57Z |
| publishDate | 2016 |
| publishDateRange | 2016 |
| publishDateSort | 2016 |
| record_format | oai_dc |
| spelling | arxiv-1605.054732026-06-04 Damped Arrow-Hurwicz algorithm for sphere packing Degond, Pierre Ferreira, Marina A. Motsch, Sébastien Numerical Analysis 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. 2016-05-18 text https://arxiv.org/abs/1605.05473 http://arxiv.org/abs/1605.05473 doi:10.1016/j.jcp.2016.11.047 |
| spellingShingle | Numerical Analysis Degond, Pierre Ferreira, Marina A. Motsch, Sébastien Damped Arrow-Hurwicz algorithm for sphere packing |
| title | Damped Arrow-Hurwicz algorithm for sphere packing |
| title_full | Damped Arrow-Hurwicz algorithm for sphere packing |
| title_fullStr | Damped Arrow-Hurwicz algorithm for sphere packing |
| title_full_unstemmed | Damped Arrow-Hurwicz algorithm for sphere packing |
| title_short | Damped Arrow-Hurwicz algorithm for sphere packing |
| title_sort | damped arrow hurwicz algorithm for sphere packing |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/1605.05473 http://arxiv.org/abs/1605.05473 |
| work_keys_str_mv | AT degondpierre dampedarrowhurwiczalgorithmforspherepacking AT ferreiramarinaa dampedarrowhurwiczalgorithmforspherepacking AT motschsebastien dampedarrowhurwiczalgorithmforspherepacking |