A Block-Parallel Newton Method via Overlapping Epsilon Decompositions

Abstract

The purpose of this paper is to present a block-parallel Newton method for solving large nonlinear systems. A graph-theoretic decomposition algorithm is first used to partition the Jacobian into weakly coupled, possibly overlapping blocks. It is then shown that it suffices to invert only the diagonal blocks to carry out the Newton iterates. A rigorous justification of this practice is provided by using a convergence result of Kantorovich in the expanded space of the iterates, where overlapping blocks appear as disjoint. The individual blocks, or a group of blocks, can be inverted by a dedicated processor, making the new block-diagonal Newton method ideally suited for parallel processing. Applications to the power flow problem are presented and parallelization issues are discussed.