Successive column correction algorithms for solving sparse nonlinear systems of equations

This paper presents two algorithms for solving sparse nonlinear systems of equations: the CM-successive column correction algorithm and a modified CM-successive column correction algorithm. Aq-superlinear convergence theorem and anr-convergence order estimate are given for both algorithms. Some numerical results and the detailed comparisons with some previously established algorithms show that the new algorithms have some promise of being very effective in practice.This research was partially supported by contracts and grants: DOE DE-AS05-82ER1-13016, AFOSR 85-0243 at Rice University, Houston, U.S.A. and Natural Sciences and Engineering Research Council of Canada grant A-8639.     

A Comparative Study on Dynamic and Static Sparsity Patterns in Parallel Sparse Approximate Inverse Preconditioning

Sparse approximate inverse (SAI) techniques have recently emerged as a new class of parallel preconditioning techniques for solving large sparse linear systems on high performance computers. The choice of the sparsity pattern of the SAI matrix is probably the most important step in constructing an SAI preconditioner. Both dynamic and static sparsity pattern selection approaches have been proposed by researchers. Through a few numerical experiments, we conduct a comparable study on the properties and performance of the SAI preconditioners using the different sparsity patterns for solving some sparse linear systems. This revised version was published online in July 2006 with corrections to the Cover Date.     

Numerical experience with the truncated Newton method for unconstrained optimization

The truncated Newton algorithm was devised by Dembo and Steihaug (Ref. 1) for solving large sparse unconstrained optimization problems. When far from a minimum, an accurate solution to the Newton equations may not be justified. Dembo's method solves these equations by the conjugate direction method, but truncates the iteration when a required degree of accuracy has been obtained. We present favorable numerical results obtained with the algorithm and compare them with existing codes for large-scale optimization.     

On the generation of updates for quasi-Newton methods

We present a unified technique for updating approximations to Jacobian or Hessian matrices when any linear structure can be imposed. The updates are derived by variational means, where an operator-weighted Frobenius norm is used, and are finally expressed as solutions of linear equations and/or unconstrained extrema. A certain behavior of the solutions is discussed for certain perturbations of the operator and the constraints. Multiple secant relations are then considered. For the nonsparse case, an explicit family of updates is obtained including Broyden, DFP, and BFGS. For the case where some of the matrix elements are prescribed, explicit solutions are obtained if certain conditions are satisfied. When symmetry is assumed, we show, in addition, the connection with the DFP and BFGS updates.This work was partially supported by a grant from Control Data     

Exploiting special structure in semidefinite programming: A survey of theory and applications

Semidefinite programming (SDP) may be seen as a generalization of linear programming (LP). In particular, one may extend interior point algorithms for LP to SDP, but it has proven much more difficult to exploit structure in the SDP data during computation.     

Correlative Sparsity in Primal-Dual Interior-Point Methods for LP,SDP, and SOCP

Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in. S. Kim’s research was supported by Kosef R01-2005-000-10271-0 and KRF-2006-312-C00062.     

Compactly supported shearlets are optimally sparse

Cartoon-like images, i.e., C² functions which are smooth apart from a C² discontinuity curve, have by now become a standard model for measuring sparse (nonlinear) approximation properties of directional representation systems. It was already shown that curvelets, contourlets, as well as shearlets do exhibit sparse approximations within this model, which are optimal up to a log-factor. However, all those results are only applicable to band-limited generators, whereas, in particular, spatially compactly supported generators are of uttermost importance for applications.In this paper, we present the first complete proof of optimally sparse approximations of cartoon-like images by using a particular class of directional representation systems, which indeed consists of compactly supported elements. This class will be chosen as a subset of (non-tight) shearlet frames with shearlet generators having compact support and satisfying some weak directional vanishing moment conditions.     

分块平方和分解

本文定义了分块平方和可分解多项式的概念.粗略地说,它是这样一类多项式,只考虑其支撑集(不考虑系数)就可以把它的平方和分解问题等价地转换为较小规模的同类问题(换句话说,相应的半正定规划问题的矩阵可以分块对角化).本文证明了近年文献中提出的两类方法—分离多项式(split polynomial)和最小坐标投影(minimal coordinate projection)—都可以用分块平方和可分解多项式来描述,证明了分块平方和可分解多项式集在平方和多项式集中为零测集.     

大型稀疏无约束最优化的列分划校正Cholesky因子算法

我们考虑求解无约束优化问题1引言(?)f(x),(1)其中f：D(?)R~n→R为R~n上的二次连续可微函数,且f(x)的二阶Hesse阵H(x)稀疏、正定．为了求解问题(1),我们考虑下列Newton型方法x~(k 1)=x~k-(B~k)~(-1)▽f(x~k),k=0,1,…,(2)其中B~k是和Hesse阵H(x~k)具有相同稀疏性的近似．由于Hesse阵对称,我们假定B~k对称．为了具体说明给定矩阵B的稀疏性,我们使用M来定义指标对(i,j)的集合,其