Analysis of decomposition algorithms via nonlinear splitting functions

This paper provides a structural analysis of decomposition algorithms using a generalization of linear splitting methods. This technique is used to identify explicitly the essential similarities and differences between several classical algorithms. Similar concepts can be used to analyze a large class of multilevel hierarchical structures.This research was supported in part by ONR Contract No. N00014-76-C-0346, in part by the US Department of Energy, Division of Electric Energy Systems, Contract No. ERDA-E(49-18)-2087 at the Massachusetts Institute of Technology, and in part by the Joint Services Electronics Program, Contract No. DAAG-29-78-C-0016.The authors would like to thank Dr. P. Varaiya, University of California at Berkeley, and Dr. D. Bertsekas for their comments and suggestions.