Parallel Newton two‐stage methods based on ILU factorizations for nonlinear systems

Parallel iterative algorithms based on the Newton method and on two of its variants, the Shamanskii method and the Chord method, for solving nonlinear systems are proposed. These algorithms are based on two‐stage multisplitting methods where incomplete LU factorizations are considered as a mean of constructing the inner splittings. Convergence properties of these parallel methods are studied for H‐matrices. Computational results of these methods on two parallel computing systems are discussed. The reported experiments show the effectiveness of these methods. Copyright © 2006 John Wiley & Sons, Ltd.     

矩阵分裂序列与线性二级迭代法

本文讨论线性非定常二级迭代法的收敛性．对于一般的基于矩阵分裂序列的迭代法,针对分裂序列本身找到了一种新的且相对较弱的收敛性条件,并因此得到了由非定常二级迭代法推广而来的广义二级迭代法的收敛结果．从而,用一种新的方法证明了非定常二级迭代法的收敛性．     

线性块SOR二级迭代法的收敛性质

内迭代次数充分大时,求解非奇异线性方程组的块SOR二级迭代法与经典的块SOR方法有相同的收敛性和大致相等的收敛速度.因此,用于块SOR方法有效的松弛因子,同样可有效地用于块SOR二级迭代法.     

H-Splittings and two-stage iterative methods

Summary Convergence of two-stage iterative methods for the solution of linear systems is studied. Convergence of the non-stationary method is shown if the number of inner iterations becomes sufficiently large. TheR ₁-factor of the two-stage method is related to the spectral radius of the iteration matrix of the outer splitting. Convergence is further studied for splittings ofH-matrices. These matrices are not necessarily monotone. Conditions on the splittings are given so that the two-stage method is convergent for any number of inner iterations.This work was supported in part by a Temple University Summer Research Fellowship.     

Block Two-stage Methods for Singular Systems and Markov Chains

The use of block two-stage methods for the iterative solution of consistent singular linear systems is studied. In these methods, suitable for parallel computations, different blocks, i.e., smaller linear systems, can be solved concurrently by different processors. Each of these smaller systems are solved by an (inner) iterative method. Hypotheses are provided for the convergence of non-stationary methods, i.e., when the number of inner iterations may vary from block to block and from one outer iteration to another. It is shown that the iteration matrix corresponding to one step of the block method is convergent, i.e., that its powers converge to a limit matrix. A theorem on the convergence of the infinite product of matrices with the same eigenspace corresponding to the eigenvalue 1 is proved, and later used as a tool in the convergence analysis of the block method. The methods studied can be used to solve any consistent singular system, including discretizations of certain differential equations. They can also be used to find stationary probability distribution of Markov chains. This last application is considered in detail.     

Asynchronous gradient algorithms for a class of convex separable network flow problems

We consider the single commodity strictly convex network flow problem. The dual of this problem is unconstrained, differentiable, and well suited for solution via distributed or parallel iterative methods. We present and prove convergence of gradient and asynchronous gradient algorithms for solving the dual problem. Computational results are given and analysed.     

On a new family of high‐order iterative methods for the matrix pth root

The main goal of this paper is to approximate the principal pth root of a matrix by using a family of high‐order iterative methods. We analyse the semi‐local convergence and the speed of convergence of these methods. Concerning stability, it is well known that even the simplified Newton method is unstable. Despite it, we present stable versions of our family of algorithms. We test numerically the methods: we check the numerical robustness and stability by considering matrices that are close to be singular and badly conditioned. We find algorithms of the family with better numerical behavior than the Newton and the Halley methods. These two algorithms are basically the iterative methods proposed in the literature to solve this problem. Copyright © 2015 John Wiley & Sons, Ltd.     

Operator trigonometry of iterative methods

A new and general approach to the understanding and analysis of widely used iterative methods for the numerical solution of the equation Ax = b is presented. This class of algorithms, which includes CGN, GMRES. ORTHOMIN, BCG, CGS, and others of current importance, utilizes residual norm minimizing procedures, such as those often found under the general names Galerkin method, Arnoldi method, Lanczos method, and so on. The view here is different: the needed error minimizations are seen trigonometrically. © 1997 John Wiley & Sons, Ltd.     

Neumann Control of Unstable Parabolic Systems: Numerical Approach

The present article is concerned with the Neumann control of systems modeled by scalar or vector parabolic equations of reaction-advection-diffusion type with a particular emphasis on systems which are unstable if uncontrolled. To solve these problems, we use a combination of finite-difference methods for the time discretization, finite-element methods for the space discretization, and conjugate gradient algorithms for the iterative solution of the discrete control problems. We apply then the above methodology to the solution of test problems in two dimensions, including problems related to nonlinear models.     

一类Riccati方程组对称自反解的两种迭代算法

针对源于Markov跳变线性二次控制问题中的一类对偶代数Riccati方程组,分别采用修正共轭梯度算法和正交投影算法作为非精确Newton算法的内迭代方法,建立求其对称自反解的非精确Newton-MCG算法和非精确Newton-OGP算法.两种迭代算法仅要求Riccati方程组存在对称自反解,对系数矩阵等没有附加限定.数值算例表明,两种迭代算法是有效的.     

Preconditioning Indefinite Systems in Interior Point Methods for Optimization

Every Newton step in an interior-point method for optimization requires a solution of a symmetric indefinite system of linear equations. Most of today's codes apply direct solution methods to perform this task. The use of logarithmic barriers in interior point methods causes unavoidable ill-conditioning of linear systems and, hence, iterative methods fail to provide sufficient accuracy unless appropriately preconditioned. Two types of preconditioners which use some form of incomplete Cholesky factorization for indefinite systems are proposed in this paper. Although they involve significantly sparser factorizations than those used in direct approaches they still capture most of the numerical properties of the preconditioned system. The spectral analysis of the preconditioned matrix is performed: for convex optimization problems all the eigenvalues of this matrix are strictly positive. Numerical results are given for a set of public domain large linearly constrained convex quadratic programming problems with sizes reaching tens of thousands of variables. The analysis of these results reveals that the solution times for such problems on a modern PC are measured in minutes when direct methods are used and drop to seconds when iterative methods with appropriate preconditioners are used.     

Asynchronous two-stage iterative methods

Summary. Parallel block two-stage iterative methods for the solution of linear systems of algebraic equations are studied. Convergence is shown for monotone matrices and for -matrices. Two different asynchronous versions of these methods are considered and their convergence investigated. Received September 7, 1993 / Revised version received April 21, 1994     

Asynchronous multisplitting methods for nonlinear fixed point problems

Our aim is to present for nonlinear problems asynchronous multisplitting algorithms including both the basic situation of O'Leary and White and the discrete analogue of Schwarz's alternating method and its multisubdomain extensions and moreover their two-stage counterparts. The analysis of these methods is based on El Tarazi’s convergence theorem for asynchronous iterations and leads to a good level of asynchronism in each of the considered situations. This revised version was published online in August 2006 with corrections to the Cover Date.     

An approach to the Gummel map by vector extrapolation methods

The numerical approximation of nonlinear partial differential equations requires the computation of large nonlinear systems, that are typically solved by iterative schemes. At each step of the iterative process, a large and sparse linear system has to be solved, and the amount of time elapsed per step grows with the dimensions of the problem. As a consequence, the convergence rate may become very slow, requiring massive cpu-time to compute the solution. In all such cases, it is important to improve the rate of convergence of the iterative scheme. This can be achieved, for instance, by vector extrapolation methods. In this work, we apply some vector extrapolation methods to the electronic device simulation to improve the rate of convergence of the family of Gummel decoupling algorithms. Furthermore, a different approach to the topological ε-algorithm is proposed and preliminary results are presented.     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

Generalized Jacobi and Gauss-Seidel Methods for Solving Linear System of Equations

The Jacobi and Gauss-Seidel algorithms are among the stationary iterative methods for solving linear system of equations. They are now mostly used as precondition-ers for the popular iterative solvers. In this paper a generalization of these methods are proposed and their convergence properties are studied. Some numerical experiments are given to show the efficiency of the new methods.     

Superlinear convergence of infeasible-interior-point methods for linear programming

At present the interior-point methods of choice are primal—dual infeasible-interior-point methods, where the iterates are kept positive, but allowed to be infeasible. In practice, these methods have demonstrated superior computational performance. From a theoretical point of view, however, they have not been as thoroughly studied as their counterparts — feasible-interior-point methods, where the iterates are required to be strictly feasible. Recently, Kojima et al., Zhang, Mizuno and Potra studied the global convergence of algorithms in the primal—dual infeasible-interior-point framework. In this paper, we continue to study this framework, and in particular we study the local convergence properties of algorithms in this framework. We construct parameter selections that lead toQ-superlinear convergence for a merit function andR-superlinear convergence for the iteration sequence, both at rate 1 + where can be arbitrarily close to one.Research supported in part by NSF DMS-9102761 and DOE DE-FG05-91ER25100.Corresponding author.     

Penalty-Factor-Free Stabilized Nonconforming Finite Elements for Solving Stationary Navier-Stokes Equations

Two nonconforming penalty methods for the two-dimensional stationary Navier-Stokes equations are studied in this paper. These methods are based on the weakly continuous $P_1$ vector fields and the locally divergence-free (LDF) finite elements, which respectively penalize local divergence and are discontinuous across edges. These methods have no penalty factors and avoid solving the saddle-point problems. The existence and uniqueness of the velocity solution are proved, and the optimal error estimates of the energy norms and $L^2$-norms are obtained. Moreover, we propose unified pressure recovery algorithms and prove the optimal error estimates of $L^2$-norm for pressure. We design a unified iterative method for numerical experiments to verify the correctness of the theoretical analysis.     

Block truncated-Newton methods for parallel optimization

Truncated-Newton methods are a class of optimization methods suitable for large scale problems. At each iteration, a search direction is obtained by approximately solving the Newton equations using an iterative method. In this way, matrix costs and second-derivative calculations are avoided, hence removing the major drawbacks of Newton's method. In this form, the algorithms are well-suited for vectorization. Further improvements in performance are sought by using block iterative methods for computing the search direction. In particular, conjugate-gradient-type methods are considered. Computational experience on a hypercube computer is reported, indicating that on some problems the improvements in performance can be better than that attributable to parallelism alone.Partially supported by Air Force Office of Scientific Research grant AFOSR-85-0222.Partially supported by National Science Foundation grant ECS-8709795, co-funded by the U.S. Air Force Office of Scientific Research.     

Projection methods: an annotated bibliography of books and reviews

Projections onto sets are used in a wide variety of methods in optimization theory but not every method that uses projections really belongs to the class of projection methods as we mean it here. Here, projection methods are iterative algorithms that use projections onto sets while relying on the general principle that when a family of (usually closed and convex) sets is present, then projections (or approximate projections) onto the given individual sets are easier to perform than projections onto other sets (intersections, image sets under some transformation, etc.) that are derived from the given family of individual sets. Projection methods employ projections (or approximate projections) onto convex sets in various ways. They may use different kinds of projections and, sometimes, even use different projections within the same algorithm. They serve to solve a variety of problems which are either of the feasibility or the optimization types. They have different algorithmic structures, of which some are particularly suitable for parallel computing, and they demonstrate nice convergence properties and/or good initial behavioural patterns. This class of algorithms has witnessed great progress in recent years and its member algorithms have been applied with success to many scientific, technological and mathematical problems. This annotated bibliography includes books and review papers on, or related to, projection methods that we know about, use and like. If you know of books or review papers that should be added to this list please contact us.