On convergence of splitting iteration methods for non-Hermitian positive-definite linear systems

A new splitting iteration method is presented for the system of linear equations when the coefficient matrix is a non-Hermitian positive-definite matrix. The spectral radius, the optimal parameter, and some norm properties of the iteration matrix for the new method are discussed in detail. Based on these results, the new method is convergent under reasonable conditions for any non-Hermitian positive-definite linear system. Finally, the numerical examples show that the new method is more effective than the Hermitian and skew-Hermitian splitting iterative (or positive-definite and skew-Hermitian splitting iterative) method in central processing unit time.     

Quotient convergence and multi-splitting methods for solving singular linear equations

Abstract   In this paper, we use the group inverse to characterize the quotient convergence of an iterative method for solving consistent singular linear systems, when the matrix index equals one. Next, we show that for stationary splitting iterative methods, the convergence and the quotient convergence are equivalent, which was first proved in [7]. Lastly, we propose a (multi-)splitting iterative method A=F–G, where the splitting matrix F may be singular, endowed with group inverse, by using F ^# as a solution tool for any iteration. In this direction, sufficient conditions for the quotient convergence of these methods are given. Then, by using the equivalence between convergence and quotient convergence, the classical convergence of these methods is proved. These latter results generalize Cao’s result, which was given for nonsingular splitting matrices F. Keywords: Group inverse, singular linear equations, iterative method, P-regular splitting, Hermitian positive definite matrix, multi-splitting, quotient convergence AMS Classification: 15A09, 65F35     

On convergence of double splitting methods for non-Hermitian positive semidefinite linear systems

Some convergence results for double splitting iterations for (possibly non-Hermitian) positive semidefinite linear systems are established. Furthermore, the convergence of double splitting methods for generalized saddle point systems is studied, and a convergence condition for double splitting methods applied to this type of system is given.     

On the convergence of spectral multigrid methods for solving periodic problems

The spectral multigrid method combines the efficiencies of the spectral method and the multigrid method. In this paper, we show that various spectral multigrid methods have constant convergence rates (independent of the number of unknowns in the linear system, to be solved) in their multilevel iterations for solving periodic problems.     

The preconditioned variational methods for solving large linear systems

The implementation of the Preconditioned Conjugate Gradient method for the solution of large linear systems arising from the discretization of differential operators, requires the predetermination of only one iteration parameter. The numerical determination of the optimal value of this constant parameter, involve the spectral bounds of some matrices and can be obtained in O(N²) sine function evaluations, where 1/N is the discretization mesh size. It is shown that this parameter can be chosen in a stable manner in O(1) operations per iteration, if it is allowed to vary with the iteration index from information derived from the gradient parameters.     

Explicit isomorphic iterative methods for solving arrow-type linear systems

A new class of approximate inverse arrow-type matrix techniques based on the concept of sparse approximate LU-type factorization procedures is introduced for computing explicitly approximate inverses without inverting the decomposition factors. Isomorphic methods in conjunction with explicit preconditioned schemes based on approximate inverse matrix techniques are presented for the efficient solution of arrow-type linear systems. Applications of the proposed method on linear systems is discussed and numerical results are given     

On the preconditioned Jacobi method for solving large linear systems

This paper is concerned with the application of preconditioning techniques to the well known Jacobi iterative method for solving the finite difference equations derived from the discretization of self-adjoint elliptic partial differential equations. The convergence properties of this one parameter preconditioned method are analyzed and the value of the optimum preconditioning parameter and the performance of the method determined for a variety of standard problems.     

Efficient preconditioned NHSS iteration methods for solving complex symmetric linear systems

Based on the new HSS (NHSS) iteration method introduced by Pour and Goughery (2015), we propose a preconditioned variant of NHSS (P*NHSS) and an efficient parameterized P*NHSS (PPNHSS) iteration methods for solving a class of complex symmetric linear systems. The convergence properties of the P*NHSS and the PPNHSS iteration methods show that the iterative sequences are convergent to the unique solution of the linear system for any initial guess when the parameters are properly chosen. Moreover, we discuss the quasi-optimal parameters which minimize the upper bounds for the spectral radius of the iteration matrices. Numerical results show that the PPNHSS iteration method is superior to several iteration methods whether the experimental optimal parameters are used or not.     

On maximizing the convergence rate for linear systems with input saturation

In this note, we consider a few important issues related to the maximization of the convergence rate inside a given ellipsoid for linear systems with input saturation. For continuous-time systems, the control that maximizes the convergence rate is simply a bang-bang control. Through studying the system under the maximal convergence control, we reveal several fundamental results on set invariance. An important consequence of maximizing the convergence rate is that the maximal invariant ellipsoid is produced. We provide a simple method for finding the maximal invariant ellipsoid, and we also study the dependence of the maximal convergence rate on the Lyapunov function.     

On a class of row preconditioners for solving linear systems

The purpose of this paper is to give comparison results for a class of row preconditioners. Convergence and monotone properties for the classical iterative methods associated with these preconditioners are analysed. In the final section, numerical results are presented.     

The use of iterative methods for solving large sparse PDE-related linear systems

A preliminary report is given on the ITPACK project for developing adaptive iterative algorithms and software for solving large sparse PDE-related linear systems of equations. These iterative procedures are implemented in a collection of Fortran subroutines.     

On the performance of transputer networks for solving linear systems of equations

In this paper, we consider the solution of large linear systems of equations on transputer networks. We analyze various aspects of an efficient implementation of parallel Gaussian elimination and the solution of triangular systems. In particular, we show the importance of asynchronous communication and of coarse granularity of the resulting tasks. We also demonstrate the scalability of the algorithms for a large number of processors and report on some tests for problems of various size.     

On solving systems of linear inequalities with artificial neuralnetworks

The implementation of the relaxation-projection algorithm by artificial neural networks to solve sets of linear inequalities is examined. The different versions of this algorithm are described, and theoretical convergence results are given. The best known analog optimization solvers are shown to use the simultaneous projection version of it. Neural networks that implement each version are described. The results of tests, made with simulated realizations of these networks, are reported. These tests consisted in having all networks solve some sample problems. The results obtained help determine good values for the step size parameters, and point out the relative merits of the different networks.     

Generalized tridiagonal preconditioners for solving linear systems

The paper presents a type of tridiagonal preconditioners for solving linear system Ax=b with nonsingular M-matrix A, and obtains some important convergent theorems about preconditioned Jacobi and Gauss–Seidel type iterative methods. The main results theoretically prove that the tridiagonal preconditioners cannot only accelerate the convergence of iterations, but also generalize some known results.     

Pivot tightening for direct methods for solving symmetric positive definite systems of linear interval equations

The paper considers systems of linear interval equations, i.e., linear systems where the coefficients of the matrix and the right hand side vary between given bounds. We focus on symmetric matrices and consider direct methods for the enclosure of the solution set of such a system. One of these methods is the interval Cholesky method, which is obtained from the ordinary Cholesky decomposition by replacing the real numbers by the related intervals and the real operations by the respective interval operations. We present a method by which the diagonal entries of the interval Cholesky factor can be tightened for positive definite interval matrices, such that a breakdown of the algorithm can be prevented. In the case of positive definite symmetric Toeplitz matrices, a further tightening of the diagonal entries and also of other entries of the Cholesky factor is possible. Finally, we numerically compare the interval Cholesky method with interval variants of two methods which exploit the Toeplitz structure with respect to the computing time and the quality of the enclosure of the solution set.     

A direct method for solving linear systems

In this work we propose a direct method for solving systems of linear equations which is based on a successive LU-decomposition of matrices of the form l + uv ^T . Simultaneously, the factors of an LU-decomposition of the coefficient matrix are obtained. A specific choice of the “rank-one decomposition” of the given matrix leads to a variant of the Gauss elimination process.     

求解块三对角方程组的一种并行策略

提出了一种在MIMD分布式存储环境下求解块三对角线性方程组的并行算法。基于Galerkin原理适当取基构造算法,使整个计算过程只在相邻处理机间通信两次,并给出了系数矩阵为对称正定矩阵时算法收敛的条件。在HP rx2600集群系统上进行的数值计算结果表明该算法与多分裂方法相比具有较高的加速比和并行效率。     

Finite termination and global monotonicity of Newton-type methods for solving hybrid piecewise linear systems

In the present paper, we give a detailed theoretical analysis for some Newton-type procedures for certain piecewise linear systems. Under rather general assumptions, the iterates are well defined and monotonically converge to the exact solution of the given systems. This procedure is shown to have a finite termination property, i.e. it converges to the exact solution in a finite number of steps.     

Gradient-based maximal convergence rate iterative method for solving linear matrix equations

This paper is concerned with numerical solutions to general linear matrix equations including the well-known Lyapunov matrix equation and Sylvester matrix equation as special cases. Gradient based iterative algorithm is proposed to approximate the exact solution. A necessary and sufficient condition guaranteeing the convergence of the algorithm is presented. A sufficient condition that is easy to compute is also given. The optimal convergence factor such that the convergence rate of the algorithm is maximized is established. The proposed approach not only gives a complete understanding on gradient based iterative algorithm for solving linear matrix equations, but can also be served as a bridge between linear system theory and numerical computing. Numerical example shows the effectiveness of the proposed approach.