Optimization Online


An inexact parallel splitting augmented Lagrangian method for large system of linear equations

Zheng Peng (pzheng008***at***yahoo.com)
Donghua Wu (dhwu***at***shu.edu.cn)

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 )

Citation:: In-psalmtolq-v1-pzheng

Download: [PDF]

Entry Submitted: 06/05/2009
Entry Accepted: 06/08/2009
Entry Last Modified: 07/08/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society