On some improvements of square root iteration for polynomial complex zeros

Using Newton's and Halley's corrections, some modifications of the simultaneous method for finding polynomial complex zeros, based on square root iteration, are obtained. The convergence order of the proposed methods is five and six respectively. Further improvements of these methods are performed by applying the Gauss—Seidel approach. The lower bounds of the R-order of convergence and the convergence conditions for the accelerated (single-step) methods are given. Faster convergence is attained without additional calculations. The considered iterative procedures are illustrated numerically in the example of an algebraic equation.     

Modulus‐based synchronous multisplitting iteration methods for linear complementarity problems

By an equivalent reformulation of the linear complementarity problem into a system of fixed‐point equations, we construct modulus‐based synchronous multisplitting iteration methods based on multiple splittings of the system matrix. These iteration methods are suitable to high‐speed parallel multiprocessor systems and include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, successive overrelaxation, and accelerated overrelaxation of the modulus type as special cases. We establish the convergence theory of these modulus‐based synchronous multisplitting iteration methods and their relaxed variants when the system matrix is an H ₊ ‐matrix. Numerical results show that these new iteration methods can achieve high parallel computational efficiency in actual implementations. Copyright © 2012 John Wiley & Sons, Ltd.     

The Monte-Carlo algorithm for the solving of systems of linear algebraic equations by the Seidel method

The iteration algorithm is used to solve systems of linear algebraic equations by the Monte-Carlo method. Each next iteration is simulated as a random vector such that its expectation coincides with the Seidel approximation of the iteration process. We deduce a system of linear equations such that mutual correlations of components of the limit vector and correlations of two iterations satisfy them. We prove that limit dispersions of the random vector of solutions of the system exist and are finite.     

On an Uzawa smoother in multigrid for poroelasticity equations

A poroelastic saturated medium can be modeled by means of Biot's theory of consolidation. It describes the time‐dependent interaction between the deformation of porous material and the fluid flow inside of it. Here, for the efficient solution of the poroelastic equations, a multigrid method is employed with an Uzawa‐type iteration as the smoother. The Uzawa smoother is an equation‐wise procedure. It shall be interpreted as a combination of the symmetric Gauss‐Seidel smoothing for displacements, together with a Richardson iteration for the Schur complement in the pressure field. The Richardson iteration involves a relaxation parameter which affects the convergence speed, and has to be carefully determined. The analysis of the smoother is based on the framework of local Fourier analysis (LFA) and it allows us to provide an analytic bound of the smoothing factor of the Uzawa smoother as well as an optimal value of the relaxation parameter. Numerical experiments show that our upper bound provides a satisfactory estimate of the exact smoothing factor, and the selected relaxation parameter is optimal. In order to improve the convergence performance, the acceleration of multigrid by iterant recombination is taken into account. Numerical results confirm the efficiency and robustness of the acceleration scheme.     

Comparison theorems for splittings of M-matrices in (block) Hessenberg form

BIT Numerical Mathematics - Some variants of the (block) Gauss–Seidel iteration for the solution of linear systems with M-matrices in (block) Hessenberg form are discussed. Comparison results...     

Pipeline implementation of cellular automata for structural design on message-passing multiprocessors

The inherent structure of cellular automata is trivially parallelizable and can directly benefit from massively parallel machines in computationally intensive problems. This paper presents both block synchronous and block pipeline (with asynchronous message passing) parallel implementations of cellular automata on distributed memory (message-passing) architectures. A structural design problem is considered to study the performance of the various cellular automata implementations. The synchronous parallel implementation is a mixture of Jacobi and Gauss–Seidel style iteration, where it becomes more Jacobi like as the number of processors increases. Therefore, it exhibits divergence because of the mathematical characteristics of Jacobi iteration matrix for the structural problem as the number of processors increases. The proposed pipeline implementation preserves convergence by simulating a pure Gauss–Seidel style row-wise iteration. Numerical results for analysis and design of a cantilever plate made of composite material show that the pipeline update scheme is convergent and successfully generates optimal designs.     

Gauss–Seidel Estimation of Generalized Linear Mixed Models With Application to Poisson Modeling of Spatially Varying Disease Rates

Generalized linear mixed models (GLMMs) are often fit by computational procedures such as penalized quasi-likelihood (PQL). Special cases of GLMMs are generalized linear models (GLMs), which are often fit using algorithms like iterative weighted least squares (IWLS). High computational costs and memory space constraints make it difficult to apply these iterative procedures to datasets having a very large number of records.

We propose a computationally efficient strategy based on the Gauss–Seidel algorithm that iteratively fits submodels of the GLMM to collapsed versions of the data. The strategy is applied to investigate the relationship between ischemic heart disease, socioeconomic status, and age/gender category in New South Wales, Australia, based on outcome data consisting of approximately 33 million records. For Poisson and binomial regression models, the Gauss–Seidel approach is found to substantially outperform existing methods in terms of maximum analyzable sample size. Remarkably, for both models, the average time per iteration and the total time until convergence of the Gauss–Seidel procedure are less than 0.3% of the corresponding times for the IWLS algorithm. Platform-independent pseudo-code for fitting GLMS, as well as the source code used to generate and analyze the datasets in the simulation studies, are available online as supplemental materials.     

An efficient algebraic multigrid method for quadratic discretizations of linear elasticity problems on some typical anisotropic meshes in three dimensions

The quality of the mesh used in the finite element discretizations will affect the efficiency of solving the discreted linear systems. The usual algebraic solvers except multigrid method do not consider the effect of the grid geometry and the mesh quality on their convergence rates. In this paper, we consider the hierarchical quadratic discretizations of three‐dimensional linear elasticity problems on some anisotropic hexahedral meshes and present a new two‐level method, which is weakly independent of the size of the resulting problems by using a special local block Gauss–Seidel smoother, that is LBGS_v iteration when used for vertex nodes or LBGS_m iteration for midside nodes. Moreover, we obtain the efficient algebraic multigrid (AMG) methods by applying DAMG (AMG based on distance matrix) or DAMG‐PCG (PCG with DAMG as a preconditioner) to the solution of the coarse level equation. The resulting AMG methods are then applied to a practical example as a long beam. The numerical results verify the efficiency and robustness of the proposed AMG algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

On the Convergence of Decoupled Optimal Power Flow Methods

This paper investigates the convergence of decoupled optimal power flow (DOPF) methods used in power systems. In order to make the analysis tractable, a rigorous mathematical reformation of DOPF is presented first to capture the essence of conventional heuristic decompositions. By using a nonlinear complementary problem (NCP) function, the Karush–Kuhn–Tucker (KKT) systems of OPF and its subproblems of DOPF are reformulated as a set of semismooth equations, respectively. The equivalent systems show that the sequence generated by DOPF methods is identical to the sequence generated by Gauss–Seidel methods with respect to nonsmooth equations. This observation motivates us to extend the classical Gauss–Seidel method to semismooth equations. Consequently, a so-called semismooth Gauss–Seidel method is presented, and its related topics such as algorithm and convergence are studied. Based on the new theory, a sufficient convergence condition for DOPF methods is derived. Numerical examples of well-known IEEE test systems are also presented to test and verify the convergence theorem.     

A variable fixing version of the two-block nonlinear constrained Gauss–Seidel algorithm for \ell _1-regularized least-squares

The problem of finding sparse solutions to underdetermined systems of linear equations is very common in many fields as e.g. signal/image processing and statistics. A standard tool for dealing with sparse recovery is the \(\ell _1\) -regularized least-squares approach that has recently attracted the attention of many researchers. In this paper, we describe a new version of the two-block nonlinear constrained Gauss–Seidel algorithm for solving \(\ell _1\) -regularized least-squares that at each step of the iteration process fixes some variables to zero according to a simple active-set strategy. We prove the global convergence of the new algorithm and we show its efficiency reporting the results of some preliminary numerical experiments.     

On the convergence of basic iterative methods for convection–diffusion equations

In this paper we analyze convergence of basic iterative Jacobi and Gauss–Seidel type methods for solving linear systems which result from finite element or finite volume discretization of convection–diffusion equations on unstructured meshes. In general the resulting stiffness matrices are neither M‐matrices nor satisfy a diagonal dominance criterion. We introduce two newmatrix classes and analyse the convergence of the Jacobi and Gauss–Seidel methods for matrices from these classes. A new convergence result for the Jacobi method is proved and negative results for the Gauss–Seidel method are obtained. For a few well‐known discretization methods it is shown that the resulting stiffness matrices fall into the new matrix classes. Copyright © 1999 John Wiley & Sons, Ltd.     

Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems

In order to solve large sparse linear complementarity problems on parallel multiprocessor systems, we construct modulus-based synchronous two-stage multisplitting iteration methods based on two-stage multisplittings of the system matrices. These iteration methods include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, SOR and AOR of the modulus type as special cases. We establish the convergence theory of these modulus-based synchronous two-stage multisplitting iteration methods and their relaxed variants when the system matrix is an H _?+?-matrix. Numerical results show that in terms of computing time the modulus-based synchronous two-stage multisplitting relaxation methods are more efficient than the modulus-based synchronous multisplitting relaxation methods in actual implementations.     

Performance Optimization for the Parallel Gauss–Seidel Smoother

Simulation, e.g., in the field of computational fluid dynamics, accounts for a major part of the computing time on highperformance systems. Many simulation packages still rely on Gauss–Seidel iteration, either as the main linear solver or as a smoother for multigrid schemes. Straight-forward implementations of this solver have efficiency problems on today's most common high-performance computers, i.e., multiprocessor clusters with pronounced memory hierarchies. In this work we present two simple techniques for improving the performance of the parallel Gauss–Seidel method for the 3D Poisson equation by optimizing cache usage as well as reducing the number of communication steps. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An order optimal solver for the discretized bidomain equations

The electrical activity in the heart is governed by the bidomain equations. In this paper, we analyse an order optimal method for the algebraic equations arising from the discretization of this model. Our scheme is defined in terms of block Jacobi or block symmetric Gauss–Seidel preconditioners. Furthermore, each block in these methods is based on standard preconditioners for scalar elliptic or parabolic partial differential equations (PDEs). Such preconditioners can be realized in terms of multigrid or domain decomposition schemes, and are thus readily available by applying ‘off‐the‐shelves’ software. Finally, our theoretical findings are illuminated by a series of numerical experiments. Copyright © 2006 John Wiley & Sons, Ltd.     

Modified Block SSOR Preconditioners for Symmetric Positive Definite Linear Systems

A class of modified block SSOR preconditioners is presented for the symmetric positive definite systems of linear equations, whose coefficient matrices come from the hierarchical-basis finite-element discretizations of the second-order self-adjoint elliptic boundary value problems. These preconditioners include a block SSOR iteration preconditioner, and two inexact block SSOR iteration preconditioners whose diagonal matrices except for the (1,1)-block are approximated by either point symmetric Gauss–Seidel iterations or incomplete Cholesky factorizations, respectively. The optimal relaxation factors involved in these preconditioners and the corresponding optimal condition numbers are estimated in details through two different approaches used by Bank, Dupont and Yserentant (Numer. Math. 52 (1988) 427–458) and Axelsson (Iterative Solution Methods (Cambridge University Press, 1994)). Theoretical analyses show that these modified block SSOR preconditioners are very robust, have nearly optimal convergence rates, and especially, are well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

Existence,uniqueness, and numerical simulations of Föppl‐von Kármán equations for simply supported plate

In this paper, we consider the Föppl‐von Kàrmàn equations in the case of a simply supported thin plate. We introduce a nonlinear Gauss‐Seidel fixed point scheme which allows to obtain a constructive proof of the existence and the uniqueness, when a small nonzero source term is considered. Numerical simulations are given using finite elements approximation. We point out the important role of a parameter which allows to select situations in which a buckling phenomena is observed numerically.     

求解带非线性边界条件的反应扩散方程数值解的组合迭代方法

1　引　　言我们首先考虑如下抛物型方程ｕｔ-ＤΔｕ =ｆ(ｘ ,ｔ ,ｕ) (ｔ∈ ( 0 ,Ｔ],ｘ∈Ω ) ｕ/ ν+ βｕ =ｇ(ｘ ,ｔ ,ｕ) (ｔ∈ ( 0 ,Ｔ],ｘ∈ Ω )ｕ(ｘ ,0 ) =ψ(ｘ) (ｘ∈Ω )( 1 .1 )其中Ｔ为正常数 ,Ω 是ＲＰ 空间的有界区域 记ＱＴ=Ω × ( 0 ,Ｔ],ＳＴ= Ω × ( 0 ,Ｔ],假设在ＱＴ上Ｄ≡ｄ(ｘ ,ｔ) >0 ,在ＳＴ 上β≡β(ｘ ,ｔ)≥ 0 又设 ｆ(ｘ ,ｔ,ｕ) ,ｇ(ｘ ,ｔ,ｕ)为关于ｕ的非线性函数 ,且对ｘ ,ｔ各参数满足Ｈ¨ｏｌｄｅｒ连续条件 将 ( 1 .1 )离散化之后我们得到相应的有限差分系统 ,当 ｇ(ｘ ,ｔ,ｕ)为ｕ的线性…     

A stable numerical method for space fractional Landau–Lifshitz equations

In this paper, we proposed a simple and unconditional stable time-split Gauss–Seidel projection (GSP) method for the space fractional Landau–Lifshitz (FLL) equations. Numerical results are presented to demonstrate the effectiveness and stability of this method.     

Greedy and randomized versions of the multiplicative Schwarz method

We consider sequential, i.e., Gauss–Seidel type, subspace correction methods for the iterative solution of symmetric positive definite variational problems, where the order of subspace correction steps is not deterministically fixed as in standard multiplicative Schwarz methods. Here, we greedily choose the subspace with the largest (or at least a relatively large) residual norm for the next update step, which is also known as the Gauss–Southwell method. We prove exponential convergence in the energy norm, with a reduction factor per iteration step directly related to the spectral properties, e.g., the condition number, of the underlying space splitting. To avoid the additional computational cost associated with the greedy pick, we alternatively consider choosing the next subspace randomly, and show similar estimates for the expected error reduction. We give some numerical examples, in particular applications to a Toeplitz system and to multilevel discretizations of an elliptic boundary value problem, which illustrate the theoretical estimates.     

Gauss–Seidel method for multi-valued inclusions with Z mappings

We consider a problem of solution of a multi-valued inclusion on a cone segment. In the case where the underlying mapping possesses Z type properties we suggest an extension of Gauss–Seidel algorithms from nonlinear equations. We prove convergence of a modified double iteration process under rather mild additional assumptions. Some results of numerical experiments are also presented.