A note on Wilkinson's iterative refinement of solution with automatic step-size control

In a more recent paper [X. Wu and Y.L. Fang, Wilkinson's iterative refinement of solution with automatic step-size control for linear system of equations, Appl. Math. Comput. 193 (2007), pp. 506–513], the authors proposed an iterative improvement of solution with automatic step-size control for a linear system of algebraic equations. The convergence analysis of the iterative procedure is shown for both stationary and non-stationary iterative formulas, based on the accurate coefficient matrix A and its inverse. However, in each iteration, A is approximated by the LU decomposition in floating-point arithmetic, and then its inverse is also approximated by a matrix B, although the role of B is realized by solving something like Az=r from the LU factorization of A. This point should be addressed that usually BA is not equal to an identity matrix I, in particular, when A is ill-conditioned. Therefore, in this paper, a supplementary convergence analysis is presented based on the approximation.     

An iterative method for solving partitioned linear equations

A new iterative scheme, using two partitions of the coefficient matrix of a given linear and non-singular system of equationsAx=b, is shown to always converge to the solution. The concept of two vector spaces approaching orthogonality is quantified and used to show that the eigenvalues of the iteration matrix approach zero as the vector spaces defined by the two partitions ofA approach orthogonality.     

New gauss–seidel like block iterative methods to solve discrete boundary value problems

The concept of new Gauss–Seidel like iterative methods, which was introduced in [3], will be extended so as to obtain a class of convergent Gauss–Seidel like block iterative methods to solve linear matrix equations Ax=b with an M-Matrix A. New block iterative methods will be applied to finite difference approximations of the Laplace's equation on a square (“model problem” [8]) which surpass even the block successive overrelaxation iterative method with optimum relaxation factor in this example.     

Systolic networks for iterative methods for linear equations with cyclic reduction II

This paper presents systolic networks for the application of cyclic reduction to iterative methods for the solution of a linear system of equations A x=b where A is a p-cyclic matrix derived from multi-colouring ordered difference schemes on a regular mesh.     

Numerical solution of fuzzy linear system

The aim of this paper is to present a numerical method for solving a general n×n fuzzy system of linear equations of the form Ax=b, where A is a crisp matrix and b an arbitrary fuzzy vector. We obtain the solution of n×n fuzzy linear systems by using Jacobi and Gauss-Seidel iterative methods and also show that the order of system will not be increased and the computing time will be shorter than other numerical methods. Finally, we illustrate this method by offering some numerical examples.     

The convergence conditions of the psd iterative method for linear systems

In this paper, the PSD iterative method was proposed by Evans and Missirlis [4], for solving a large nonsingular system of linear equations Ax=b A general necessary condition for con-vergence of the PSD iterative method is obtained. The convergence theorems of the PSD iterative method are established under the condition that the coefficient matrix A is an H-matrix, our theorems improve and extend some known results.     

On the numerical solution of the Burgers's equation

In this paper, we consider the linear heat equation arisen from the Burgers's equation using the Hopf–Cole transformation. Discretization of this equation with respect to the space variable results in a linear system of ordinary differential equations. The solution of this system involves in computing exp(α A)y for some vector y, where A is a large special tridiagonal matrix and α is a positive real number. We give an explicit expression for computing exp(α A)y. Finally, some numerical experiments are given to show the efficiency of the method.     

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 the iterative refinement of the solution of ill-conditioned linear system of equations

Recently, Salkuyeh and Fahim [A new iterative refinement of the solution of ill-conditioned linear system of equations, Int. Comput. Math. 88(5) (2011), pp. 950–956] have proposed a two-step iterative refinement of the solution of an ill-conditioned linear system of equations. In this paper, we first present a generalized two-step iterative refinement procedure to solve ill-conditioned linear system of equations and study its convergence properties. Afterward, it is shown that the idea of an orthogonal projection technique together with a basic stationary iterative method can be utilized to construct a new efficient and neat hybrid algorithm for solving the mentioned problem. The convergence of the offered hybrid approach is also established. Numerical examples are examined to demonstrate the feasibility of proposed algorithms and their superiority to some of existing approaches for solving ill-conditioned linear system of equations.     

An accelerated randomized Kaczmarz method via low-rank approximation

The Kaczmarz method for finding the solution to an overdetermined consistent system of linear equation Ax=b(A∈R^m×n) is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Recently, Strohmer and Vershynin proposed randomized Kaczmarz, and proved its exponential convergence. In this paper, motivated by idea of precondition, we present a modified version of the randomized Kaczmarz method where an orthogonal matrix was multiplied to both sides of the equation Ax=b, and the orthogonal matrix is obtained by low-rank approximation. Our approach fits the problem when m is huge and m?n. Theoretically, we improve the convergence rate of the randomized Kaczmarz method. The numerical results show that our approach is faster than the standard randomized Kaczmarz.     

Approximating the inverse of a matrix for use in iterative algorithms on vector processors

Most iterative techniques for solving the symmetric positive-definite systemAx=b involve approximating the matrixA by another symmetric positive-definite matrixM and then solving a system of the formMz=d at each iteration. On a vector machine such as the CDC-STAR-100, the solution of this new system can be very time consuming. If, however, an approximationM ^?1 can be given toA ^?1, the solutionz=M ^?1 d can be computed rapidly by matrix multiplication, a fast operation on the STAR. Approximations using the Neumann expansion of the inverse ofA give reasonable forms forM ^?1 and are presented. Computational results using the conjugate gradient method for the “5-point” matrixA are given.     

A first principles solution to the non-singular H∞ control problem

This paper presents an elementary solution to the non-singular H^∞ control problem. In this control problem, the underlying linear system satisfies a set of assumptions which ensures that the solution can be obtained by solving just two algebraic Riccati equations of the game type. This leads to the central solution to the H^∞ control problem. The solution presented in this paper uses only elementary ideas beginning with the Bounded Real Lemma.     

Convergence of the interval and point TOR method

In this paper, we present the interval version of the two parameter overrelaxation iterative (TOR) method and we obtain some convergence conditions when the matrix A of the linear system Ax?=?b belongs to some classes of matrice. Similar conditions were obtained for the point TOR method.

Some results for the accelerated overrelaxation interval and point iterative (AOR) method were also obtained, which coincides with those given by Martins in Ref. [7].     

Further results on controllability and the linear equation Ax = b

The linear equation Ax = b, with A an n × n matrix and b an n × l matrix over a unique factorization domain R, is related to the controllability submodule U of the pair (A, b). It is shown that the above equation has a solution lying in V if, and only if, A is unimodular as an operator on U. An example is given of a matrix which is unimodular as an operator on the controllability submodule, but not as an operator on Rⁿ and sparseness of this occurrence is discussed.     

Enclosing Solutions of Singular Interval Systems Iteratively

Richardson splitting applied to a consistent system of linear equations Cx = b with a singular matrix C yields to an iterative method x^k+1 = Ax^k + b where A has the eigenvalue one. It is known that each sequence of iterates is convergent to a vector x^* = x^* (x⁰) if and only if A is semi-convergent. In order to enclose such vectors we consider the corresponding interval iteration with (|[A]|) = 1 where |[A]| denotes the absolute value of the interval matrix [A]. If |[A]| is irreducible we derive a necessary and sufficient criterion for the existence of a limit of each sequence of interval iterates. We describe the shape of and give a connection between the convergence of ( ) and the convergence of the powers of [A].Dedicated to Professor G. Mae on the occasion of his 65^th birthday     

Some investigation on Hermitian positive-definite solutions of a nonlinear matrix equation

In this paper, the Hermitian positive-definite solutions of the matrix equation X^s+A*X^?tA=Q are considered. New necessary and sufficient conditions for the equation to have a Hermitian positive-definite solution are derived. In particular, when A is singular, a new estimate of Hermitian positive-definite solutions is obtained. In the end, based on the fixed point theorem, an iterative algorithm for obtaining the positive-definite solutions of the equation with Q=I is discussed. The error estimations are found.     

Polynomial approximation of functions of matrices and applications

In solving a mathematical problem numerically, we frequently need to operate on a vector by an operator that can be expressed asf(A), whereA is anN ×N matrix [e.g., exp(A), sin(A), A^–-]. Except for very simple matrices, it is impractical to construct the matrixf (A) explicitly. Usually an approximation to it is used. This paper develops an algorithm based upon a polynomial approximation tof (A). First the problem is reduced to a problem of approximatingf (z) by a polynomial in z, where z belongs to a domainD in the complex plane that includes all the eigenvalues ofA. This approximation problem is treated by interpolatingf (z) in a certain set of points that is known to have some maximal properties. The approximation thus achieved is almost best. Implementing the algorithm to some practical problems is described. Since a solution to a linear systemAx=b isx=A ^–1 b, an iterative solution algorithm can be based upon a polynomial approximation tof (A)=A ^–1. We give special attention to this important problem.     

Accelerating scientific computations with mixed precision algorithms

On modern architectures, the performance of 32-bit operations is often at least twice as fast as the performance of 64-bit operations. By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many dense and sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution. The approach presented here can apply not only to conventional processors but also to other technologies such as Field Programmable Gate Arrays (FPGA), Graphical Processing Units (GPU), and the STI Cell BE processor. Results on modern processor architectures and the STI Cell BE are presented.

Program summary

Program title: ITER-REFCatalogue identifier: AECO_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AECO_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 7211No. of bytes in distributed program, including test data, etc.: 41 862Distribution format: tar.gzProgramming language: FORTRAN 77Computer: desktop, serverOperating system: Unix/LinuxRAM: 512 MbytesClassification: 4.8External routines: BLAS (optional)Nature of problem: On modern architectures, the performance of 32-bit operations is often at least twice as fast as the performance of 64-bit operations. By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many dense and sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution.Solution method: Mixed precision algorithms stem from the observation that, in many cases, a single precision solution of a problem can be refined to the point where double precision accuracy is achieved. A common approach to the solution of linear systems, either dense or sparse, is to perform the LU factorization of the coefficient matrix using Gaussian elimination. First, the coefficient matrix A is factored into the product of a lower triangular matrix L and an upper triangular matrix U. Partial row pivoting is in general used to improve numerical stability resulting in a factorization PA=LU, where P is a permutation matrix. The solution for the system is achieved by first solving Ly=Pb (forward substitution) and then solving Ux=y (backward substitution). Due to round-off errors, the computed solution, x, carries a numerical error magnified by the condition number of the coefficient matrix A. In order to improve the computed solution, an iterative process can be applied, which produces a correction to the computed solution at each iteration, which then yields the method that is commonly known as the iterative refinement algorithm. Provided that the system is not too ill-conditioned, the algorithm produces a solution correct to the working precision.Running time: seconds/minutes     

基于GaBP算法的快速潮流计算方法

研究在潮流迭代求解过程中雅可比矩阵方程组的迭代求解方法及其收敛性。首先利用PQ分解法进行潮流迭代求解,并针对求解过程中雅可比矩阵对称且对角占优的特性,对雅可比矩阵方程组采用高斯置信传播算法(GaBP)进行求解,再结合Steffensen加速迭代法以提高GaBP算法的收敛性。对IEEE118、IEEE300节点标准系统和两个波兰互联大规模电力系统进行仿真计算后结果表明：随着系统规模的增长,使用Steffensen加速迭代法进行加速的GaBP算法相对于基于不完全LU的预处理广义极小残余方法(GMRES)具有更好的收敛性,为大规模电力系统潮流计算的快速求解提供了一种新思路。