Parallel Newton Two-Stage Multisplitting Iterative Methods for Nonlinear Systems

Parallel Newton two-stage iterative methods to solve nonlinear systems are studied. These algorithms are based on both the multisplitting technique and the two-stage iterative methods. Convergence properties of these methods are studied when the Jacobian matrix is either monotone or an H-matrix. Furthermore, in order to illustrate the performance of the algorithms studied, computational results about these methods on a distributed memory multiprocessor are discussed.This revised version was published online in October 2005 with corrections to the Cover Date.     

Parallel Newton methods for the nonlinear complementarity problem

In this paper, we discuss how the basic Newton method for solving the nonlinear complementarity problem can be implemented in a parallel computation environment. We propose some synchronized and asynchronous Newton methods and establish their convergence.This work was based on research supported by the National Science Foundation under grant ECS-8407240 and by a University Research and Development grant from Cray Research Inc. The research was initiated when the authors were with the University of Texas at Dallas.     

Parallel Interior-Point Method for Linear and Quadratic Programs with Special Structure

This paper concerns the use of iterative solvers in interior-point methods for linear and quadratic programming problems. We state an adaptive termination rule for the inner iterative scheme and we prove the global convergence of the obtained algorithm, exploiting the theory developed for inexact Newton methods. This approach is promising for problems with special structure on parallel computers. We present an application on Cray T3E/256 and SGI Origin 2000/64 arising in stochastic linear programming and robust optimization, where the constraint matrix is block-angular and extremely large.     

Dynamic block GMRES: an iterative method for block linear systems

We present variants of the block-GMRES() algorithms due to Vital and the block-LGMRES(,) by Baker, Dennis and Jessup, obtained with replacing the standard QR factorization by a rank-revealing QR factorization in the Arnoldi process. The resulting algorithm allows for dynamic block deflation whenever there is a linear dependency between the Krylov vectors or the convergence of a right-hand-side occurs. implementations of the algorithms were tested on a number of test matrices and the results show that in some cases a substantial reduction of the execution time is obtained. Also a parallel implementation of our variant of the block-GMRES() algorithm, using and was tested on parallel computer, showing good parallel efficiency. This work was carried out while the author was at IM/UFRGS.     

Globally Convergent Inexact Quasi-Newton Methods for Solving Nonlinear Systems

Large scale nonlinear systems of equations can be solved by means of inexact quasi-Newton methods. A global convergence theory is introduced that guarantees that, under reasonable assumptions, the algorithmic sequence converges to a solution of the problem. Under additional standard assumptions, superlinear convergence is preserved.     

Newton additive and multiplicative Schwarz iterative methods

Daniel B. Szyld^¶Department of Mathematics, Temple University, Philadelphia, PA 19122, USA ^{Convergence properties are presented for Newton additive andmultiplicative Schwarz (AS and MS) iterative methods for thesolution of nonlinear systems in several variables. These methodsconsist of approximate solutions of the linear Newton step usingeither AS or MS iterations, where overlap between subdomainscan be used. Restricted versions of these methods are also considered.These Schwarz methods can also be used to precondition a Krylovsubspace method for the solution of the linear Newton steps.Numerical experiments on parallel computers are presented, indicatingthe effectiveness of these methods.}     

On a flexible elimination algorithm with applications to panel element equations

A flexible elimination algorithm is presented and is appliedto the solution of dense systems of linear equations. Propertiesof the algorithm are exploited in relation to panel elementmethods for potential flow and subsonic compressible flow. Furtherproperties in relation to distributed computing are also discussed.     

有界约束非线性系统的结合Lanczos分解技术不精确Newton法

提出了结合Lanczos分解技术不精确Newton法求解有界变量约束非线性系统．通过Lanczos分解技术解一个仿射二次模型获得迭代方向．利用内点回代线搜索技术,沿着这个方向得到一个可接受的步长．在合理的假设条件下,证明了算法的整体收敛性与局部超线性收敛速率．此外,数值结果表明了算法的有效性．     

关于Brown方法的半局部收敛性

在本文中,我们讨论解非线性方程组的Brown方法的半局部收敛性。通过对Brown方法的算法结构作深入的分析,我们将Brown方法变换成带有特殊误差项的近似Newton法,基于这种等价变形,我们建立了Brown方法的半局部收敛定理,从而完善了Brown方法的收敛理论。     

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

Augmented Lagrangians which are quadratic in the multiplier

We present a class of new augmented Lagrangian functions with the essential property that each member is concave quadratic when viewed as a function of the multiplier. This leads to an improved duality theory and to a related class of exact penalty functions. In addition, a relationship between Newton steps for the classical Lagrangian and the new Lagrangians is established.This work was supported in part by ARO Grant No. DAAG29-77-G-0125.     

Inexact Newton methods for the nonlinear complementarity problem

An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application. This research was based on work supported by the National Science Foundation under grant ECS-8407240.     

Distributed versus Centralized Storage and Control for Parallel Branch and Bound: Mixed Integer Programming on the CM-5

This paper describes parallel, non-shared-memoryimplementation of the classical general mixed integer branch and boundalgorithm, with experiments on the CM-5 family of parallel processors. Themain issue in such an implementation is whether task scheduling and certaindata-storage functions should be handled by a single processor, orspread among multiple processors. The centralized approach riskscreating processing bottlenecks, while the more decentralizedimplementations differ more from the fundamental serial algorithm.Extensive computational tests on standard MIPLIB problems comparecentralized, clustered, and fully decentralized task scheduling methods, using a novel combination of random work scattering and rendezvous-basedglobal load balancing, along with a distributed control by tokentechnique. Further experiments compare centralized and distributedschemes for storing heuristic pseudo-cost branching data. The distributed storage method is based on continual asynchronous reductionalong a tree of redundant storage sites. On average, decentralized taskscheduling appears at least as effective as central control, butpseudo-cost storage should be kept as centralized as possible.