GSOR Method for the Equality Constrained Least Squares Problems and the Generalized Least Squares Problems

In a recent paper [4], Li et al . gave a generalized successive overrelaxation (GSOR) method for the least squares problems. In this paper, we show that the GSOR method can be applied to the equality constrained least squares (LSE) problems and the generalized least squares (GLS) problems.     

An Adaptive Weighted Bisection Method For Finding Roots Of Non-Linear Equations

In this paper, an algorithm for finding the roots of non-linear equations is developed by introducing a weight in the formula of the Bisection Method (BM). Initially, we use a fixed weight to solve an equation in the least possible number of iterations. In a second stage, we develop a method termed as the Adaptive Weighted Bisection Method (AWBM) in order to update the weight at each iteration. The adaptation is achieved by minimizing the function values of the iterates with respect to the weight. Our numerical experiments show that, the AWBM, based on minimizing a function value with respect to the weight, achieves quadratic convergence. However, the method differs from the classic second order Newton-Raphson by guaranteeing convergence through bracketing.     

Preconditioning technique for symmetric M-matrices

Abstract Linear systems with M-matrices occur in a wide variety of areas including numerical partial differential equations, input-output production and growth models in economics, linear complementarity problems in operations research and Markov chains in stochastic analysis.In this paper, we propose a new preconditioner for solving a system with symmetric positive definite M-matrix by the preconditioned conjugate gradient (PCG) method. We show that our preconditioner increases the convergence rate of the PCG method and reduces the operation cost. Numerical results are given.     

Variants of the Uzawa method for saddle point problem

In this paper, we first propose three variants of the Uzawa method for solving the saddle point problem, and then we provide convergence results for the three proposed methods. Numerical experiments show that our proposed methods with three parameters perform about twice as fast as the GSOR (Generalized SOR) method with two parameters since the proposed methods have less workload per iteration than the GSOR.     

Alternating Group Explicit Method For The Numerical Solution Of Non-Linear Singular Two-Point Boundary Value Problems Using A Fourth Order Finite Difference Method

In this paper, we report on the AGE and Newton-AGE iteration methods for the fourth order numerical solution of two point non-linear boundary value problems. Both methods are applicable to problems both in cartesian and polar coordinates and are suitable for use on parallel computers. The convergence analysis of the new method is briefly discussed and the results of numerical experiments presented.     

A Two-Stage Iterative Method For Solving A Weakly Nonlinear Parametrized System

In this paper we consider a parametrized system of weakly nonlinear equations which corresponds to a nonlinear elliptic boundary-value problem with zero source, homogeneous boundary conditions and a positive parameter in the linear term. Positive solutions of this system are of interest to us. A characterization of this positive solution is given. Such a solution is determined by the Modified Newton-Arithmetic Mean method. This method is well suited for implementation on parallel computers. A theorem about the monotone convergence of the method is proved. An application of the method for solving a real practical problem related to the study of interacting populations is described.     

Generalized successive overrelaxation iterative method for a class of complex symmetric linear system of equations

In this paper, to solve a broad class of complex symmetric linear systems, we recast the complex system in a real formulation and apply the generalized successive overrelaxation (GSOR) iterative method to the equivalent real system. We then investigate its convergence properties and determine its optimal iteration parameter as well as its corresponding optimal convergence factor. In addition, the resulting GSOR preconditioner is used to precondition Krylov subspace methods such as the generalized minimal residual method for solving the real equivalent formulation of the system. Finally, we give some numerical experiments to validate the theoretical results and compare the performance of the GSOR method with the modified Hermitian and skew-Hermitian splitting iteration.     

Note To The Mixed-Type Splitting Iterative Method For The Positive Real Linear System

In [5] a new iterative method is given for the linear system of equations Au=b , where A is large, sparse and nonsymmetrical and A^{\rm T}+A is symmetric and positive definite (SPD) or equivalently A is positive real. The new iterative method is based on a mixed-type splitting of the matrix A and is called the mixed-type splitting iterative method. The iterative method contains an auxiliary matrix D_1 that is restricted to be symmetric. In this note, the auxiliary matrix is allowed to be more general and it is shown that by proper choice of D 1 , the new iterative method is still convergent. It is also shown that by special choice of D_{1} , the new iterative method becomes the well-known (point) accelerated overrelaxation (AOR) [1] method. Hence, it is shown that the (point) AOR method applied to the positive real system is convergent under the proper choice of the overrelaxation parameters y and .     

Approximate Inverse Preconditioners for the Conjugate Gradient Method

The method of Conjugate Gradients is known to converge for symmetric positive definite systems of equations. This paper applies it to non-symmetric and ill-conditioned matrices. In order to facilitate convergence, an approximate inverse is used to precondition the Conjugate Gradient method. This is achieved by applying Newton's method. Three versions of Newton's method are introduced to compute the approximate inverse. Convergence of each version is compared. Numerical experimentation is done for some known "ill-conditioned" problems.     

基于预条件共轭梯度法的混凝土层析成像

根据常规图像重建的共轭梯度迭代算法,提出一种预条件共轭梯度法。用一种新的预条件子M来改善系数矩阵的条件数,结合一般的共轭梯度法,导出预条件共轭梯度法。实验结果表明,预条件共轭梯度算法比共轭梯度算法具有更好的CT重建效果和消噪能力,可提高计算的精度和图像的重建质量。     

New PCG based algorithms for the solution of Hermitian Toeplitz systems

In order to solve Toeplitz linear systems A_n(f)x=b generated by a nonnegative integrable function f, through use of the preconditioned conjugate gradient (PCG) method, several authors have proposed A_n(g) as preconditioner in the case where g is a trigonometric polynomial [10, 14, 27, 12, 28]. In preceding works, we studied the distribution and the extremal properties of the spectrum of the preconditioned matrix G=A _n ⁻¹ (g) A_n(f). In this paper we prove that the union of the spectra of all the G_n is dense on the essential range of f/g, i.e.,ER(f/g) and we obtain asymptotic information about the rate of convergence of the smallest eigenvalue λ _l ⁿ of G_n to r (and of λ _n ⁿ to R). As a consequence of this second order result, it is possible to handle the case where f has zeros of any order θ, through the PCG methods proposed in [10, 14]. This is a noteworthy extension since the techniques developed in [10, 14, 27, 12, 28] are shown to be effective only when f has zeros of even orders. The cost of this procedure is O(n^1+c(θ) log n) arithmetic operations (ops) where the quantity c(θ) belongs to interval [0,2⁻¹] and takes the maximum value 2⁻¹ when f has a zero of odd order. Finally, for the special case of zeros of odd orders, we propose a further algorithm which makes use of the PCG techniques proposed in [10, 14, 27, 12, 28] for theeven order case, reducing the cost to O(n long n) ops.     

A Multigrid Method of the Second Kind for Solving Linear Systems of Odes Discretized by Continuous Runge-Kutta Methods

A Waveform Relaxation method as applied to a linear system of ODEs is the Picard iteration for a linear Volterra integral equation of the second kind ({\cal I} - {\cal K})y = b \eqno (1) called Waveform Relaxation second kind equation. A corresponding Waveform Relaxation Runge-Kutta method is the Picard iteration for a discretized version ({\cal I} - {\cal K}_l )y_l = b_l \eqno (2) of the integral equation (1), where y l is the continuous solution of the original linear system of ODE provided by the so called limit method. We consider a W-cycle multigrid method, with Picard iteration as smoothing step, for iteratively computing y l . This multigrid method belongs to the class of multigrid methods of the second kind as described in Hackbusch [3, chapter 16]. In the paper we prove that the truncation error after one iteration is of the same order of the discretization error y l @ y of the limit method and the truncation error after two iterations has order larger than the discretization error. Thus we can see the multigrid method as a new numerical method for solving the original linear system of ODE which provides, after one iteration, a continuous solution of the same order of the solution of the limit method, and after two iterations, a solution with asymptotically the same error of the solution of the limit method. On the other hand the computational cost of the multigrid method is considerably smaller than the limit method.     

Parallel scheduling of the PCG method for banded matrices rising from FDM/FEM

An implicit time-linearized finite difference discretization of partial differential equations on regular/structured meshes results in an n-diagonal block system of algebraic equations, which is usually solved by means of the Preconditioned Conjugate Gradient (PCG) method. In this paper, an analysis of the parallel implementation of this method on several computer architectures and for several programming paradigms is presented. For three-dimensional regular/structured meshes, a new implementation of the PCG method with Jacobi preconditioner is proposed. For the computer architectures and number of processors employed in this study, it has been found that this implementation is more efficient than the standard one, and can be applied to narrow-band matrices and other preconditioners, such as, for example, polynomial ones.     

A coarse preconditioner for multi-domain boundary element equations

This paper is concerned with the application of a coarse preconditioner, the generalised minimal residual (GMRES) method and a generalised successive over-relaxation (GSOR) method to linear systems of equations that are derived from boundary integral equations. Attention is restricted to systems of the form ∑^N_j=1H_ijx_j=c_i, i=1,2,…,N, where H_ij are matrices, x_j and c_i are column vectors. The integer N denotes the number of domains and these systems are solved by adapting techniques initially devised for solving single-domain problems. These techniques include parameter matrix accelerated GMRES and GSOR in combination with a multiplicative Schwarz method for non-overlapping domains. The multiplicative Schwarz method is a generalised form of the block Gauss–Seidel method and is called the generalised multi-domain iterative procedure. A new form of coarse grid preconditioning is applied to limit the convergence dependence on block numbers. The coarse preconditioner is obtained from a crude representation of the global system of equations. Attention is restricted to thermal problems with domains connected through resistive thermal barriers. The effect of lowering and increasing the thermal resistance between domains is investigated. The coarse preconditioner requires a more accurate representation on interfaces with lower thermal resistance. Computation times are determined for the iterative procedures and for elimination techniques indicating the relative benefits for problems of this nature.     

Comparison Of Interpolations Used In Solving Delay Differential Equations By Runge-Kutta Method

Delay differential equations are solved using embedded Singly Diagonally Implicit Runge-Kutta (SDIRK) method (3,4) in (4,5). The approximation of the delay term is obtained by Newton divided difference interpolation and interpolation developed by In't Hout. Numerical results based on these two types of interpolation are compared. The stability polynomial and the stability regions of SDIRK method (2,2) using In't Hout interpolation for the delay term are presented.     

Basic Lul Factorization And Improved Iterative Method With Orderings

Consider the 'basic LUL factorization' of the matrices as the generalization of the LU factorization and the UL factorization, and using this LUL factorization of the matrices, we propose an "improved iterative method" such that the spectral radius of this iterative matrix is equal to zero, and this method converges at most n iterations. Our main concern is the necessary and sufficient conditions that the improved iterative matrix is equal to the iterative matrix of the improved SOR method with orderings. Concerning the tridiagonal matrices and the upper Hessenberg matrices, this method becomes the improved SOR method with orderings, and we give n selections of the multiple relaxation parameters such that the spectral radii of the corresponding improved SOR matrices are 0. We extend these results to a class of $n \times n$ matrices. We also consider the basic LUL factorization and improved iterated method 'corresponding to permutation matrices'.     

Parallel R-Point Explicit Block Method for Solving Second Order Ordinary Differential Equations Directly

A new parallel R-point explicit block method for solving second order ordinary differential equations (ODEs) directly is developed. The method computes the numerical solution of the equations at three points simultaneously. Each problem was tested on the shared memory parallel computer Sequent S27 using both the sequential and parallel implementations of the new method and the conventional 1-point method. Numerical results are presented comparing the two methods in terms of the number of steps taken, accuracy and execution times. The results indicate the advantages of using the parallel implementation of the new method for solving second order ODEs directly particularly when the step size becomes finer.     

An analysis of deictic signs in computer interfaces: contributions to the Semiotic Inspection Method

In this paper we discuss the concept of deictic sign as a component of the conceptual framework of Linguistics and Semiotics that can be added to Semiotic Inspection Method (SIM) in case the method is adapted to better approach digital games. Deictic signs should be here understood as signs that stablish an indexical relation with the objects they refer to, thus placing them in terms of space, time and person with a reference to the moment of communication though the interface. This paper analyzes such kind of signs in digital games; to do so, it discusses in detail the deictic aspects that SIM could not inspect when it was applied to the interfaces of the games Ingress, Kinectimals and Just Dance Now. As a result, we show that the category of deictic signs can be added to SIM when this method is adapted to systems that make explicit indexical references.     

The QIF Singular Value Decomposition Method

In this paper, the well known singular value decomposition (SDV) method is extended to explicit (2 2 2) block form, by using the Quadrant Interlocking Factorisation (QIF) method. Numerical results are presented to portray the validity of the proposed method.     

A New Approach to the Gas Dynamics Equation: An Application of the Decomposition Method

The Adomian decomposition method is used to implement the homogeneous gas dynamics equations. The analytic solution of the equation is calculated in the form of a series with easily computable components. The homogeneous problem is quickly solved by observing the self-canceling "noise" terms whose sum vanishes in the limit. Comparing the methodology with some other known techniques shows that the present approach is effective and powerful. Many test modeling problems from mathematical physics, both linear and nonlinear are discussed to illustrate the effectiveness and the performance of the decomposition method.