Parallel Asynchronous Modified Newton Methods for Network Flows

Didier El Baz (1) , Moussa Elkihel (1)

1 LAAS-CDA - Équipe Calcul Distribué et Asynchronisme

We consider single commodity strictly convex network flow problems. The dual problem is unconstrained, differentiable and well suited for solution via parallel iterative methods. We propose and prove convergence of parallel asynchronous modified Newton algorithms for solving the dual problem. Parallel asynchronous Newton multisplitting algorithms are also considered, their convergence is also shown. A first set of computational results is presented and analyzed.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]; Analyse numérique [cs.NA]; Réseaux et télécommunications [cs.NI]

Didier El Baz, Moussa Elkihel. Parallel Asynchronous Modified Newton Methods for Network Flows. IEEE International Parallel and Distributed Processing Symposium Workshop (IPDPSW 2015), May 2015, Hyderabad, India. pp.1135-1142, ⟨10.1109/IPDPSW.2015.34⟩. ⟨hal-02115940⟩