Inexact Newton methods and mixed non linear complementary problems
by
Luca Bergamaschi
University of Padua
Coauthors: Giovanni Zilli (University of Padua)

Inexact Newton methods and mixed non linear complementary problems

Luca Bergamaschi and Giovanni Zilli
Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate
Universitá di Padova, Via Belzoni 7, 35131 Padova, ITALY
(berga@dmsa.unipd.it, zilli@dmsa.unipd.it)

Abstract

In this communication we present the results obtained in the solution of sparse and large systems of nonlinear equations by Inexact Newton-like methods [] combined with a block iterative row-projection linear solver [], []. A simple p-block partitioning of the Jacobian matrix A was used for solving in parallel a set of nonlinear test problems with sizes ranging from 1024 to 131072 on the CRAY T3E under the MPI environment. The matrix H = [ A₁⁺, ... , A_i⁺, ... , A_p⁺], where A_i⁺ = A_i^T(A_i A_i^T)^-1 is the Moore-Penrose pseudo inverse of the m_i ×n block A_i, was employed as a preconditioner. We also adopt a suitable block row partitionings of the matrix A in such a way that A_i A_i^T = I,   i=1, ... p, and consequently, A_i⁺ = A_i^T. This allows to simplify the solution of the least squares subproblems at each step of the inner iteration.

Our methods may be used to solve more general problems as the non linear mixed complementary problems [] (including linear and non linear programming problems, variational inequalities etc.). In fact, the interior point solution [] of a mixed complementary problem, due to the presence of a logarithmic penalty, can be viewed as a variant of an Inexact Newton method applied to a particular system of non linear equations.

We have applied this inexact interior point algorithm for the solution of some non linear complementary probles as the obstacle Bratu problem and the Lubrication problem []. We provide numerical results in both sequential and parallel implementations.

References

[]

Zilli, G. and Bergamaschi, L., Parallel Newton methods for sparse systems of nonlinear equations, Rendiconti del Circolo Matematico di Palermo II-58, 247-257, 1999.

[]

Bergamaschi L., Moret I., and Zilli, G., Inexact quasi-Newton methods for sparse systems of nonlinear equations, J. Fut. Gen. Comput. Sys., (2000). (To appear)

[]

Dembo, R.S., Eisenstat, S.C., and Steihaug, T., Inexact Newton methods, SIAM. J. on Numer. Anal. 19, 400-408, 1982.

[]

Dirske, S. P., and Ferris, M. C., MCLIB: A collection of nonlinear mixed complementary problems, Tech. Rep., CS Depth., University of Winsconsin, Madison, WS, 1994.

[]

Wright, S.J., Primal-Dual Interior-Point Methods, Siam, Philadelphia, 1997.

Date received: January 25, 2000