On the regularizing properties of the GMRES method

Summary. The GMRES method is a popular iterative method for the solution of large linear systems of equations with a nonsymmetric nonsingular matrix. However, little is known about the behavior of this method when it is applied to the solution of nonsymmetric linear ill-posed problems with a right-hand side that is contaminated by errors. We show that when the associated error-free right-hand side lies in a finite-dimensional Krylov subspace, the GMRES method is a regularization method. The iterations are terminated by a stopping rule based on the discrepancy principle. Received November 10, 2000 / Revised version received April 11, 2001 / Published online October 17, 2001     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

Iterative accelerating algorithms with Krylov subspaces for the solution to large-scale nonlinear problems

Discrete solution to nonlinear systems problems that leads to a series of linear problems associated with non-invariant large-scale sparse symmetric positive matrices is herein considered. Each linear problem is solved iteratively by a conjugate gradient method. We introduce in this paper new solvers (IRKS, GIRKS and D-GIRKS) that rely on an iterative reuse of Krylov subspaces associated with previously solved linear problems. Numerical assessments are provided on large-scale engineering applications. Considerations related to parallel supercomputing are also addressed. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the efficient solution of nonlinear finite element equations I

Summary On the efficient solution of nonlinear finite element equations. A fast numerical method is presented for the solution of nonlinear algebraic systems which arise from discretizations of elliptic boundary value problems. A simplified relaxation algorithm which needs no information about the Jacobian of the system is combined with a correspondingly modified conjugate gradient method. A global convergence proof is given and the number of operations required is compared with that of other algorithms which are equally applicable to a large class of problems. Numerical results verify the efficiency for some typical examples.     

一个拟极小化左共轭梯度算法及其数值表现

左共轭梯度法是求解大型稀疏线性方程组的一种新兴的Krylov子空间方法.为克服该算法数值表现不稳定、迭代中断的缺点,本文对原方法进行等价变形,得到左共轭梯度方向的另一迭代格式,给出一个拟极小化左共轭梯度算法.数值结果证实了该变形算法与原算法的相关性.     

On nonsymmetric saddle point matrices that allow conjugate gradient iterations

Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix ${{\mathcal A}}Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix whose spectrum is entirely contained in the right half plane. In this paper we study conditions so that is diagonalizable with a real and positive spectrum. These conditions are based on necessary and sufficient conditions for positive definiteness of a certain bilinear form,with respect to which is symmetric. In case the latter conditions are satisfied, there exists a well defined conjugate gradient (CG) method for solving linear systems with . We give an efficient implementation of this method, discuss practical issues such as error bounds, and present numerical experiments. In memory of Gene Golub (1932–2007), our wonderful friend and colleague, who had a great interest in the conjugate gradient method and the numerical solution of saddle point problems. The work of J?rg Liesen was supported by the Emmy Noether-Program and the Heisenberg-Program of the Deutsche Forschungsgemeinschaft.     

A total least squares method for Toeplitz systems of equations

A Newton method to solve total least squares problems for Toeplitz systems of equations is considered. When coupled with a bisection scheme, which is based on an efficient algorithm for factoring Toeplitz matrices, global convergence can be guaranteed. Circulant and approximate factorization preconditioners are proposed to speed convergence when a conjugate gradient method is used to solve linear systems arising during the Newton iterations. The work of the second author was partially supported by a National Science Foundation Postdoctoral Research Fellowship.     

Superlinearly convergent PCG algorithms for some nonsymmetric elliptic systems

A preconditioned conjugate gradient method is applied to finite element discretizations of some nonsymmetric elliptic systems. Mesh independent superlinear convergence is proved, which is an extension of a similar earlier result from a single equation to systems. The proposed preconditioning method involves decoupled preconditioners, which yields small and parallelizable auxiliary problems.     

An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.     

Subspace-restricted singular value decompositions for linear discrete ill-posed problems

The truncated singular value decomposition is a popular solution method for linear discrete ill-posed problems. These problems are numerically underdetermined. Therefore, it can be beneficial to incorporate information about the desired solution into the solution process. This paper describes a modification of the singular value decomposition that permits a specified linear subspace to be contained in the solution subspace for all truncations. Modifications that allow the range to contain a specified subspace, or that allow both the solution subspace and the range to contain specified subspaces also are described.     

Preconditioning techniques for the iterative solution of scattering problems

We consider a time-harmonic electromagnetic scattering problem for an inhomogeneous medium. Some symmetry hypotheses on the refractive index of the medium and on the electromagnetic fields allow to reduce this problem to a two-dimensional scattering problem. This boundary value problem is defined on an unbounded domain, so its numerical solution cannot be obtained by a straightforward application of usual methods, such as for example finite difference methods, and finite element methods. A possible way to overcome this difficulty is given by an equivalent integral formulation of this problem, where the scattered field can be computed from the solution of a Fredholm integral equation of second kind. The numerical approximation of this problem usually produces large dense linear systems. We consider usual iterative methods for the solution of such linear systems, and we study some preconditioning techniques to improve the efficiency of these methods. We show some numerical results obtained with two well known Krylov subspace methods, i.e., Bi-CGSTAB and GMRES.     

An iterative two-step algorithm for linear complementarity problems

Summary. We propose an algorithm for the numerical solution of large-scale symmetric positive-definite linear complementarity problems. Each step of the algorithm combines an application of the successive overrelaxation method with projection (to determine an approximation of the optimal active set) with the preconditioned conjugate gradient method (to solve the reduced residual systems of linear equations). Convergence of the iterates to the solution is proved. In the experimental part we compare the efficiency of the algorithm with several other methods. As test example we consider the obstacle problem with different obstacles. For problems of dimension up to 24\,000 variables, the algorithm finds the solution in less then 7 iterations, where each iteration requires about 10 matrix-vector multiplications. Received July 14, 1993 / Revised version received February 1994     

A stationary iterative pseudoinverse algorithm

Iterative methods applied to the normal equationsA ^T Ax=A ^T b are sometimes used for solving large sparse linear least squares problems. However, when the matrix is rank-deficient many methods, although convergent, fail to produce the unique solution of minimal Euclidean norm. Examples of such methods are the Jacobi and SOR methods as well as the preconditioned conjugate gradient algorithm. We analyze here an iterative scheme that overcomes this difficulty for the case of stationary iterative methods. The scheme combines two stationary iterative methods. The first method produces any least squares solution whereas the second produces the minimum norm solution to a consistent system. This work was supported by the Swedish Research Council for Engineering Sciences, TFR.     

A preconditioned domain decomposition algorithm for the solution of the elliptic Neumann problem

A new preconditioned conjugate gradient (PCG)-based domain decomposition method is given for the solution of linear equations arising in the finite element method applied to the elliptic Neumann problem. The novelty of the proposed method is in the recommended preconditioner which is constructed by using cyclic matrix. The resulting preconditioned algorithms are well suited to parallel computation.     

Substructuring preconditioners for the Q_1 mortar element method

Summary. The mortar element method is a non conforming finite element method with elements based on domain decomposition. For the Laplace equation, it yields an ill conditioned linear system. For solving the linear system, the so called preconditioned conjugate gradient method in a subspace is used. Preconditioners are proposed, and estimates on condition numbers and arithmetical complexity are given. Finally, numerical experiments are presented. Received June 22, 1994 / Revised version received February 6, 1995     

Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods

We devise a hybrid approach for solving linear systems arising from interior point methods applied to linear programming problems. These systems are solved by preconditioned conjugate gradient method that works in two phases. During phase I it uses a kind of incomplete Cholesky preconditioner such that fill-in can be controlled in terms of available memory. As the optimal solution of the problem is approached, the linear systems becomes highly ill-conditioned and the method changes to phase II. In this phase a preconditioner based on the LU factorization is found to work better near a solution of the LP problem. The numerical experiments reveal that the iterative hybrid approach works better than Cholesky factorization on some classes of large-scale problems.     

双变量LMEs一种异类约束最小二乘解的MCG算法

借鉴求线性矩阵方程组(LMEs)同类约束最小二乘解的修正共轭梯度法,建立了求双变量LMEs的一种异类约束最小二乘解的修正共轭梯度法,并证明了该算法的收敛性.在不考虑舍入误差的情况下,利用该算法不仅可在有限步计算后得到LMEs的一组异类约束最小二乘解,而且选取特殊初始矩阵时,可求得LMEs的极小范数异类约束最小二乘解.另外,还可求得指定矩阵在该LMEs的异类约束最小二乘解集合中的最佳逼近.算例表明,该算法是有效的.     

Time-harmonic solution for acousto-elastic interaction with controllability and spectral elements

The classical way of solving the time-harmonic linear acousto-elastic wave problem is to discretize the equations with finite elements or finite differences. This approach leads to large-scale indefinite complex-valued linear systems. For these kinds of systems, it is difficult to construct efficient iterative solution methods. That is why we use an alternative approach and solve the time-harmonic problem by controlling the solution of the corresponding time dependent wave equation.In this paper, we use an unsymmetric formulation, where fluid-structure interaction is modeled as a coupling between pressure and displacement. The coupled problem is discretized in space domain with spectral elements and in time domain with central finite differences. After discretization, exact controllability problem is reformulated as a least-squares problem, which is solved by the conjugate gradient method.     

Two new variants of nonlinear inexact Uzawa algorithms for saddle-point problems

Summary. In this paper, we consider some nonlinear inexact Uzawa methods for iteratively solving linear saddle-point problems. By means of a new technique, we first give an essential improvement on the convergence results of Bramble-Paschiak-Vassilev for a known nonlinear inexact Uzawa algorithm. Then we propose two new algorithms, which can be viewed as a combination of the known nonlinear inexact Uzawa method with the classical steepest descent method and conjugate gradient method respectively. The two new algorithms converge under very practical conditions and do not require any apriori estimates on the minimal and maximal eigenvalues of the preconditioned systems involved, including the preconditioned Schur complement. Numerical results of the algorithms applied for the Stokes problem and a purely linear system of algebraic equations are presented to show the efficiency of the algorithms. Received December 8, 1999 / Revised version received September 8, 2001 / Published online March 8, 2002 RID="*" ID="*" The work of this author was partially supported by a grant from The Institute of Mathematical Sciences, CUHK RID="**" ID="**" The work of this author was partially supported by Hong Kong RGC Grants CUHK 4292/00P and CUHK 4244/01P     

Multisplitting for regularized least squares with Krylov subspace recycling

The method of multisplitting (MS), implemented as a restricted additive Schwarz type algorithm, is extended for the solution of regularized least squares problems. The presented non‐stationary version of the algorithm uses dynamic updating of the weights applied to the subdomains in reconstituting the global solution. Standard convergence results follow from extensive prior literature on linear MS schemes. Additional convergence results on nonstationary iterations yield convergence conditions for the presented nonstationary MS algorithm. The global iteration uses repeated solves of local problems with changing right hand sides but a fixed system matrix. These problems are solved inexactly using a conjugate gradient least squares algorithm which provides a seed Krylov subspace. Recycling of the seed system Krylov subspace to obtain the solutions of subsequent nearby systems of equations improves the overall efficiency of the MS algorithm, and is apparently novel in this context. The obtained projected solution is not always of sufficient accuracy to satisfy a reasonable inner convergence condition on the local solution. Improvements to accuracy may be achieved by reseeding the solution space either every few steps, or when the successive right hand sides are sufficiently close as measured by a provided tolerance. Restarting and augmenting the solution space are also discussed. Any time a new space is generated it is used for subsequent steps. Numerical simulations validate the use of the recycling algorithm. These numerical experiments use the standard reconstruction of the two dimensional Shepp–Logan phantom, as well as a two dimensional problem from seismic tomography. Copyright © 2011 John Wiley & Sons, Ltd.