Skew-symmetric methods for nonsymmetric linear systems with multiple right-hand sides

By transforming nonsymmetric linear systems to the extended skew-symmetric ones, we present the skew-symmetric methods for solving nonsymmetric linear systems with multiple right-hand sides. These methods are based on the block and global Arnoldi algorithm which is formed by implementing orthogonal projections of the initial matrix residual onto a matrix Krylov subspace. The algorithms avoid the tediously long Arnoldi process and highly reduce expensive storage. Numerical experiments show that these algorithms are effective and give better practical performances than global GMRES for solving nonsymmetric linear systems with multiple right-hand sides.     

TWO ALGORITHMS FOR SYMMETRIC LINEAR SYSTEMS WITH MULTIPLE RIGHT-HAND SIDES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓｗｅｎｅｅｄｔｏｓｏｌｖｅｍｕｌｔｉｐｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓＡｘ(ｉ) =ｂ(ｉ) ,ｉ=1,… ,ｓ (1)ｗｉｔｈｔｈｅｓａｍｅｎ×ｎｒｅａｌｓｙｍｍｅｔｒｉｃｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘＡ ,ｂｕｔｓｄｉｆｆｅｒｅｎｔｒｉｇｈｔ ｈａｎｄｓｉｄｅｓｂ(ｉ) (ｉ=1,… ,ｓ) .Ｉｆａｌｌｏｆｔｈｅｒｉｇｈｔ ｈａｎｄｓｉｄｅｓａｒｅａｖａｉｌａｂｌｅｓｉｍｕｌｔａｎｅｏｕｓｌｙ ,ｔｈｅｎｔｈｅｓｅｓｌｉｎｅａｒｓｙｓｔｅ…     

A deflated conjugate gradient method for multiple right hand sides and multiple shifts

We consider the task of computing solutions of linear systems that only differ by a shift with the identity matrix as well as linear systems with several different right-hand sides. In the past, Krylov subspace methods have been developed which exploit either the need for solutions to multiple right-hand sides (e.g. deflation type methods and block methods) or multiple shifts (e.g. shifted CG) with some success. In this paper we present a block Krylov subspace method which, based on a block Lanczos process, exploits both features—shifts and multiple right-hand sides—at once. Such situations arise, for example, in lattice quantum chromodynamics (QCD) simulations within the Rational Hybrid Monte Carlo (RHMC) algorithm. We present numerical evidence that our method is superior compared to applying other iterative methods to each of the systems individually as well as, in typical situations, to shifted or block Krylov subspace methods.     

Splitting iterative methods for fuzzy system of linear equations

A class of splitting iterative methods is considered for solving fuzzy system of linear equations, which cover Jacobi, Gauss–Seidel, SOR, SSOR, and their block variants proposed by others before. We give a convergence theorem for a regular splitting, where the corresponding iterative methods converge to the strong fuzzy solution for any initial vector and fuzzy right-hand vector. Two schemes of splitting are given to illustrate the theorem. Numerical experiments further show the efficiency of the splitting iterative methods.     

Dynamical System Method for Solving Ill-Posed Operator Equations

Two dynamical system methods are studied for solving linear ill-posed problems with both operator and right-hand nonexact. The methods solve a Cauchy problem for a linear operator equation which possesses a global solution. The limit of the global solution at infinity solves the original linear equation. Moreover, we also present a convergent iterative process for solving the Cauchy problem.     

Optimum Modified Extrapolated Jacobi Method for Consistently Ordered Matrices

1.IlltroductionandPreliminariesWeconsiderthelineaxsystemAx=b,(1.1)wheteAERn,",bERnanddet(A)/O.WeaJ8oassumethatAhasthef0rmwhereA11,A22axesquarenonsingular(usuallydiagonal)matrices-Asisknow[61,AisaconSisentlyordered2-cyclicmatris.Forsolving(1.1)weintendtousethef0lfowngsimpleiterativemethod:In(1.4)and(1.6),w1,w2arenonzeroparameters(extraP0lati0nparameters)andI1,I2areidelltitymatricesofthesamesizesasA11anA22respectively.Theconstructionofmeth0d(1.3)isbasedonthesplittingA=M-N,whereM=Dfl-1…     

约束Fractional Tikhonov正则化的模迭代方法

反问题是现在数学物理研究中的一个热点问题,而反问题求解面临的一个本质性困难是不适定性。求解不适定问题的普遍方法是:用与原不适定问题相“邻近”的适定问题的解去逼近原问题的解,这种方法称为正则化方法.如何建立有效的正则化方法是反问题领域中不适定问题研究的重要内容.当前,最为流行的正则化方法有基于变分原理的Tikhonov正则化及其改进方法,此类方法是求解不适定问题的较为有效的方法,在各类反问题的研究中被广泛采用,并得到深入研究.     

Circulant preconditioners for discrete ill-posed Toeplitz systems

Circulant preconditioners are commonly used to accelerate the rate of convergence of iterative methods when solving linear systems of equations with a Toeplitz matrix. Block extensions that can be applied when the system has a block Toeplitz matrix with Toeplitz blocks also have been developed. This paper is concerned with preconditioning of linear systems of equations with a symmetric block Toeplitz matrix with symmetric Toeplitz blocks that stem from the discretization of a linear ill-posed problem. The right-hand side of the linear systems represents available data and is assumed to be contaminated by error. These kinds of linear systems arise, e.g., in image deblurring problems. It is important that the preconditioner does not affect the invariant subspace associated with the smallest eigenvalues of the block Toeplitz matrix to avoid severe propagation of the error in the right-hand side. A perturbation result indicates how the dimension of the subspace associated with the smallest eigenvalues should be chosen and allows the determination of a suitable preconditioner when an estimate of the error in the right-hand side is available. This estimate also is used to decide how many iterations to carry out by a minimum residual iterative method. Applications to image restoration are presented.     

计算广义逆A_（T，S）~（1，2）和A_（T，S）~（2）的投影法及其应用

本文讨论投影法计算广义逆和，同时利用该方法解线性方程组得到了一些常用的迭代公式．     

Differential equations and solution of linear systems

Many iterative processes can be interpreted as discrete dynamical systems and, in certain cases, they correspond to a time discretization of differential systems. In this paper, we propose to derive iterative schemes for solving linear systems of equations by modeling the problem to solve as a stable state of a proper differential system; the solution of the original linear problem is then computed numerically by applying a time marching scheme. We discuss some aspects of this approach, which allows to recover some known methods but also to introduce new ones. We give convergence results and numerical illustrations. AMS subject classification 65F10, 65F35, 65L05, 65L12, 65L20, 65N06     

Matrix Krylov subspace methods for linear systems with multiple right-hand sides

In this paper, we first give a result which links any global Krylov method for solving linear systems with several right-hand sides to the corresponding classical Krylov method. Then, we propose a general framework for matrix Krylov subspace methods for linear systems with multiple right-hand sides. Our approach use global projection techniques, it is based on the Global Generalized Hessenberg Process (GGHP) – which use the Frobenius scalar product and construct a basis of a matrix Krylov subspace – and on the use of a Galerkin or a minimizing norm condition. To accelerate the convergence of global methods, we will introduce weighted global methods. In these methods, the GGHP uses a different scalar product at each restart. Experimental results are presented to show the good performances of the weighted global methods. AMS subject classification 65F10     

Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

The effect of block red-black ordering on blockILU preconditioner for sparse matrices

It is well known that the ordering of the unknowns can have a significant effect on the convergence of a preconditioned iterative method and on its implementation on a parallel computer. To do so, we introduce a block red-black coloring to increase the degree of parallelism in the application of the blockILU preconditioner for solving sparse matrices, arising from convection-diffusion equations discretized using the finite difference scheme (five-point operator). We study the preconditioned PGMRES iterative method for solving these linear systems.     

块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

并行多分裂AOR迭代法的收敛定理

对解非奇异线性方程组的并行多分裂ＡＯＲ方法,本文给出了该方法的收敛性定理,同时也给出了该方法的迭代矩阵的谱半径的上界估计式。     

Block s‐step Krylov iterative methods

Block (including s‐step) iterative methods for (non)symmetric linear systems have been studied and implemented in the past. In this article we present a (combined) block s‐step Krylov iterative method for nonsymmetric linear systems. We then consider the problem of applying any block iterative method to solve a linear system with one right‐hand side using many linearly independent initial residual vectors. We present a new algorithm which combines the many solutions obtained (by any block iterative method) into a single solution to the linear system. This approach of using block methods in order to increase the parallelism of Krylov methods is very useful in parallel systems. We implemented the new method on a parallel computer and we ran tests to validate the accuracy and the performance of the proposed methods. It is expected that the block s‐step methods performance will scale well on other parallel systems because of their efficient use of memory hierarchies and their reduction of the number of global communication operations over the standard methods. Copyright © 2009 John Wiley & Sons, Ltd.     

A general projection algorithm for solving systems of linear equations

In this paper, we give a general projection algorithm for implementing some known extrapolation methods such as the MPE, the RRE, the MMPE and others. We apply this algorithm to vectors generated linearly and derive new algorithms for solving systems of linear equations. We will show that these algorithms allow us to obtain known projection methods such as the Orthodir or the GCR.     

Complex Jacobi matrices

Complex Jacobi matrices play an important role in the study of asymptotics and zero distribution of formal orthogonal polynomials (FOPs). The latter are essential tools in several fields of numerical analysis, for instance in the context of iterative methods for solving large systems of linear equations, or in the study of Padé approximation and Jacobi continued fractions. In this paper we present some known and some new results on FOPs in terms of spectral properties of the underlying (infinite) Jacobi matrix, with a special emphasis to unbounded recurrence coefficients. Here we recover several classical results for real Jacobi matrices. The inverse problem of characterizing properties of the Jacobi operator in terms of FOPs and other solutions of a given three-term recurrence is also investigated. This enables us to give results on the approximation of the resolvent by inverses of finite sections, with applications to the convergence of Padé approximants.     

Shadow block iteration for solving linear systems obtained from wavelet transforms

Matrices resulting from wavelet transforms have a special “shadow” block structure, that is, their small upper left blocks contain their lower frequency information. Numerical solutions of linear systems with such matrices require special care. We propose shadow block iterative methods for solving linear systems of this type. Convergence analysis for these algorithms are presented. We apply the algorithms to three applications: linear systems arising in the classical regularization with a single parameter for the signal de-blurring problem, multilevel regularization with multiple parameters for the same problem and the Galerkin method of solving differential equations. We also demonstrate the efficiency of these algorithms by numerical examples in these applications.