Optimal block iterative schemes for certain large,sparse, and nonsymmetric linear systems

The problem of determining fast iterative solutions of certain large, sparse, and nonsymmetric linear systems, arising in applications, is addressed here. Several iterative schemes, from the accelerated overrelaxation family, are considered. Different geometrical algorithms are used for the explicit determination of the optimal factors. Direct comparisons of the spectral radii of the resulting optimal schemes reveal that the optimal extrapolated accelerated Gauss-Seidel (EAGS) is always asymptotically faster than the optimal successive overrelaxation, while the optimal EAGS and extrapolated Gauss-Seidel strongly compete. Application of the collocation method on simple boundary-value problems is used to demonstrate our results numerically.     

解线性方程组的预条件Gauss-Seidel型迭代法

给出了解线性方程组的预条件Gauss-Seidel型方法,提出了选取合适的预条件因子．并讨论了对Z-矩阵应用这种方法的收敛性,给出了收敛最快时的系数取值．最后给出数值例子,说明选取合适的预条件因子应用Gauss-Seidel方法求解线性方程组是有效的．     

A MODIFIED GAUSS-SEIDEL ITERATION FOR LINEAR INTERVAL EQUATIONS

In order to solve linear interval equations Ax=b. the interval Gauss-Seidel iteration is applied to a modified equations A'x = b', where A' is obtained by eliminating all elements in the first upper codiagonal part of A. It is shown that this modified Gauss-Seidel iteration converges when the usual Gauss-Seidel iteration converges, and the modified Gauss-Seidel iteration always has a smaller convergence factor. The converse is not true. It is also pointed out that the modified Gauss-Seidel iteration can obtain a belter result comparing with the usual Gauss-Seidel iteration in some cases. Several examples confirmed these conclusions.     

ASYNCHRONOUS MULTISPLITTING NONLINEAR GAUSS-SEIDEL TYPE METHOD

ＡＳＹＮＣＨＲＯＮＯＵＳＭＵＬＴＩＳＰＬＩＴＴＩＮＧＮＯＮＬＩＮＥＡＲＧＡＵＳＳ－ＳＥＩＤＥＬＴＹＰＥＭＥＴＨＯＤ￥ＢＡＩＺＨＯＮＧＺＨＩＡＮＤＷＡＮＧＤＥＲＥＮＡｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｐｒｏｐｏｓｅａｐａｒａｌｌｅｌＧａｕｓｓ...     

Relaxation methods for problems with strictly convex separable costs and linear constraints

We consider the minimization problem with strictly convex, possibly nondifferentiable, separable cost and linear constraints. The dual of this problem is an unconstrained minimization problem with differentiable cost which is well suited for solution by parallel methods based on Gauss-Seidel relaxation. We show that these methods yield the optimal primal solution and, under additional assumptions, an optimal dual solution. To do this it is necessary to extend the classical Gauss-Seidel convergence results because the dual cost may not be strictly convex, and may have unbounded level sets. Work supported by the National Science Foundation under grant NSF-ECS-3217668.     

Cascadic Multigrid Method for Isoparametric Finite Element with Numerical Integration

The purpose of this paper is to study the cascadic multigrid method for the secondorder elliptic problems with curved boundary in two-dimension which are discretized by the isoparametric finite element method with numerical integration. We show that the CCG method is accurate with optimal complexity and traditional multigrid smoother (likesymmetric Gauss-Seidel, SSOR or damped Jacobi iteration) is accurate with suboptimal complexity.     

An interval branch and bound algorithm for bound constrained optimization problems

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.     

Variant of Greedy Randomized Gauss-Seidel Method for Ridge Regression

The variants of randomized Kaczmarz and randomized Gauss-Seidel algorithms are two effective stochastic iterative methods for solving ridge regression problems. For solving ordinary least squares regression problems, the greedy randomized Gauss-Seidel (GRGS) algorithm always performs better than the randomized Gauss-Seidel algorithm (RGS) when the system is overdetermined. In this paper, inspired by the greedy modification technique of the GRGS algorithm, we extend the variant of the randomized Gauss-Seidel algorithm, obtaining a variant of greedy randomized Gauss-Seidel (VGRGS) algorithm for solving ridge regression problems. In addition, we propose a relaxed VGRGS algorithm and the corresponding convergence theorem is established. Numerical experiments show that our algorithms outperform the VRK-type and the VRGS algorithms when $m > n$.     

THE MONOTONICITY OF CONVERGENCE RATE FOR MGS METHODS

In this paper we prove that the convergence rate of the modified Gauss-Seidel method is a monotonic function for some precondition parameters.     

关于ρ(L_(r,w))、ρ(J_w)的最小值

本文证明了当线性方程组系数矩阵 A之 Jacobi迭代矩阵 B=L+ U≥ 0 ,ρ( B) <1时 Gauss-Seidel法之迭代矩阵 G=L1,1的谱半径 ρ( G) =ρ( L1,1)是 ρ( Lr,w) ( 0≤ r≤w≤ 1 ,w>0 )中的最小值 ,即此时 Gauss-Seidel迭代是 AOR法中收敛最快的迭代法 .并且对 JOR法 (谱半径为 ρ( Jw) )和 SAOR法也作了相应的论述 .     

Numerical Methods for the Maxnear Criterion of Multiple-Sets Canonical Analysis

This paper deals with numerical methods for the Maxnear criterion of multiple-sets canonical analysis. Optimality conditions are derived. Upper and lower bounds of the optimal objective function value are presented. Two iterative methods are proposed. One is an alternating variable method, and the other called Gauss-Seidel method is an inexact version of the alternating variable method. Convergence of these methods are analyzed. A starting point strategy is suggested for both methods. Numerical results are presented to demonstrate the efficiency of these methods and the starting point strategy.     

Local Multilevel Method on Adaptively Refined Meshes for Elliptic Problems with Smooth Complex Coefficients

In this paper, a local multilevel algorithm is investigated for solving linear systems arising from adaptive finite element approximations of second order elliptic problems with smooth complex coefficients. It is shown that the abstract theory for local multilevel algorithm can also be applied to elliptic problems whose dominant coefficient is complex valued. Assuming that the coarsest mesh size is sufficiently small, we prove that this algorithm with Gauss-Seidel smoother is convergent and optimal on the adaptively refined meshes generated by the newest vertex bisection algorithm. Numerical experiments are reported to confirm the theoretical analysis.     

Parallel iterative solvers for boundary value methods

A parallel variant of the block Gauss-Seidel iteration for the solution of block-banded linear systems is presented. The coefficient matrix is partitioned among the processors as in the domain decomposition methods and then it is split so that the resulting iterative method has the same spectral properties of the block Gauss-Seidel iteration.The parallel algorithm is applied to the solution of block-banded linear systems arising from the numerical discretization of initial value problems by means of Boundary Value Methods (BVMs). BVMs define a new approach for the solution of ordinary differential equations and seem to be attractive for their interesting stability properties and a possible parallel implementation. In this paper, we refer to BVMs based on the extended trapezoidal rules.     

The “Gauss-Seidelization” of iterative methods for solving nonlinear equations in the complex plane

In this paper we introduce a process we have called “Gauss-Seidelization” for solving nonlinear equations. We have used this name because the process is inspired by the well-known Gauss-Seidel method to numerically solve a system of linear equations. Together with some convergence results, we present several numerical experiments in order to emphasize how the Gauss-Seidelization process influences on the dynamical behavior of an iterative method for solving nonlinear equations.     

Adaptive computation for boundary control of radiative heat transfer in glass

This paper is concerned with an optimal boundary control of the cooling down process of glass, an important step in glass manufacturing. Since the computation of the complete radiative heat transfer equations is too complex for optimization purposes, we use simplified approximations of spherical harmonics including a practically relevant frequency bands model. The optimal control problem is considered as a constrained optimization problem. A first-order optimality system is derived and decoupled with the help of a gradient method based on the solution to the adjoint equations. The arising partial differential–algebraic equations of mixed parabolic–elliptic type are numerically solved by a self-adaptive method of lines approach of Rothe type. Adaptive finite elements in space and one-step methods of Rosenbrock-type with variable step sizes in time are applied. We present numerical results for a two-dimensional glass cooling problem.     

A finite element method for a single phase quasilinear free boundary problem in one space dimension

In this paper, we apply finite element Galerkin method to a singlephase quasilinear Stefan problem with a forcing term. To construct the fully discrete approximation we apply the extrapolated Crank-Nicolson method and we derive the optimal order of convergence 2 in the temporal direction inL ²,H ¹ normed spaces.     

解线性方程组的松弛方法及其应用

线性方程组在科学和工程领域中有着重要的应用,松弛方法是求解线性方程组的有效算法之一.本文在著名的Gauss-Seidel迭代法的基础上,研究了一种有效的松弛方法.理论分析表明,该方法能收敛到线性方程组的唯一解.此外,我们还将该方法应用在鞍点问题和PageRank问题的求解上,并得出了相应的数值结果.结果表明该方法比现有的松弛方法更有效.     

一个锥模型的自适应信赖域算法及其收敛性

本文研究了无约束最优化问题的基于锥模型的自适应信赖域算法.利用理论分析得到一个新的自适应信赖域半径.算法在每步迭代中以变化的速率、当前迭代点的信息以及水平向量信息调节信赖域半径的大小.从理论上证明了新算法的全局收敛性和Q-二阶收敛性.用数值试验验证了新算法的有效性.推广了已有的自适应信赖域算法的可行性和有效性.     

Z-矩阵的预条件方法

通过对方程组Ax=b的系数矩阵施行初等行变换，该文提出了解线性方程组Ax=b的一种新的预条件Gauss Seidel迭代方法，理论上证明了新的预条件Gauss Seidel迭代方法较经典的Gauss Seidel迭代法收敛速度快. 该文提出的新预条件方法推广了文［1-2］中提出的预条件方法，具体的数值例子说明了新预条件方法的有效性.