An inexact parallel splitting augmented Lagrangian method for large system of linear equations
Zheng Peng (pzheng008yahoo.com)
Abstract: Parallel iterative methods are power tool for solving large system of linear equations (LQs). The existing parallel computing research results are all most concentred to sparse system or others particular structure, and all most based on parallel implementing the classical relaxation methods such as Gauss-Seidel, SOR, and AOR methods e±ciently on multiprcessor systems. In this paper, we proposed a novel parallel splitting operator method based on a new point of view. In this method, we part directly the coefficient matrix of this to solve system into two or three parts in row. Then we convert the original problem (LQs) into a monotone (linear) variational inequalities problem (VIs) with separable structure. Finally, we proposed an inexact parallel splitting augmented Lagrangian method to solve this variational inequalities problem (VIs). We steer clear of the matrix inverse operator by introducing proper inexact terms in subproblems, such that complexity of each step of this method is O(n2), which contradicts to a general iterative method with complexity O(n3) in theory. In addition, this method does not depend on any special structure of the problem which is to be solved. Convergence of the proposed methods (in dealing with two and three separable operators respectively) is proved. Numerical experiments are provided to show its applicability, especially its robustness with respect to the scale (dimensions) and condition (measured by condition number of coefficient matrix A) of this method.
Keywords: System of linear equations; synchronous parallel iteration; matrix decomposition; augmented Lagrangian method; inexact terms; convergence; robustness.
Category 1: Complementarity and Variational Inequalities
Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )
Category 3: Convex and Nonsmooth Optimization (Convex Optimization )
Entry Submitted: 06/05/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|