Home > Publications > Concurrent Programming and Composite Newton Methods

Concurrent Programming and Composite Newton Methods

Abstract:

The most widely used, robust, and general-purpose numerical methods for approximating the solution to systems of nonlinear algebraic equations (NAEs) are based on Newton’s method. Many variants of Newton’s method exist in order to take advantage of problem structure. However, no Newton variant converges quickly for all problems and initial guesses. It is generally impossible to know a priori which variant of Newton’s method will be effective for a given problem: some variants and initial guesses may not lead to convergence at all, or if they do, the convergence may be extremely slow. New multi-core computer architectures allow the use of multiple Newton variants in parallel to potentially enhance the overall convergence for a given problem. For example, by sharing intermediate results each variant can make use of the best iterate generated thus far. This results in a sequential combination of Newton variants that we call a composite Newton method. In this paper, we survey concurrent pro- gramming techniques, describe an implementation of composite Newton methods, and give some experimental results.

Author: Craig Thompson

Advisor: Raymond J. Spiteri

Download: cthompson_bsc_report