Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems

Summary. In previous works [21–23] we proposed the use of [5] and band Toeplitz based preconditioners for the solution of 1D and 2D boundary value problems (BVP) by means of the preconditioned conjugate gradient (PCG) methods. As and band Toeplitz linear systems can be solved [4] by using fast sine transforms [8], these methods become especially attractive in a parallel environment of computation. In this paper we extend this technique to the nonlinear, nonsymmetric case and, in addition, we prove some clustering properties for the spectra of the preconditioned matrices showing why these methods exhibit a convergence speed which results to be more than linear. Therefore these methods work much finer than those based on separable preconditioners [18,45], on incomplete LU factorizations [36,13,27], and on circulant preconditioners [9,30,35] since the latter two techniques do not assure a linear rate of convergence. On the other hand, the proposed technique has a wider range of application since it can be naturally used for nonlinear, nonsymmetric problems and for BVP in which the coefficients of the differential operator are not strictly positive and only piecewise smooth. Finally the several numerical experiments performed here and in [22,23] confirm the effectiveness of the theoretical analysis. Received December 19, 1995 / Revised version received September 15, 1997     

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.     

Semi-Conjugate Direction Methods for Real Positive Definite Systems

In this preliminary work, left and right conjugate direction vectors are defined for nonsymmetric, nonsingular matrices A and some properties of these vectors are studied. A left conjugate direction (LCD) method for solving nonsymmetric systems of linear equations is proposed. The method has no breakdown for real positive definite systems. The method reduces to the usual conjugate gradient method when A is symmetric positive definite. A finite termination property of the semi-conjugate direction method is shown, providing a new simple proof of the finite termination property of conjugate gradient methods. The new method is well defined for all nonsingular M-matrices. Some techniques for overcoming breakdown are suggested for general nonsymmetric A. The connection between the semi-conjugate direction method and LU decomposition is established. The semi-conjugate direction method is successfully applied to solve some sample linear systems arising from linear partial differential equations, with attractive convergence rates. Some numerical experiments show the benefits of this method in comparison to well-known methods. This revised version was published online in July 2006 with corrections to the Cover Date.     

预处理CG算法解油藏模拟问题的有效性比较

1引言 在大型科学和工程计算问题的实际应用中，经常会遇到求解除椭圆型或抛物线型偏微分方程问题。经差分法或有限元方法离散化后得到一个大型稀疏线性方程组。本文比较了几     

Circulant preconditioners for second order hyperbolic equations

Linear systems arising from implicit time discretizations and finite difference space discretizations of second-order hyperbolic equations in two dimensions are considered. We propose and analyze the use of circulant preconditioners for the solution of linear systems via preconditioned iterative methods such as the conjugate gradient method. Our motivation is to exploit the fast inversion of circulant systems with the Fast Fourier Transform (FFT). For second-order hyperbolic equations with initial and Dirichlet boundary conditions, we prove that the condition number of the preconditioned system is ofO() orO(m), where is the quotient between the time and space steps andm is the number of interior gridpoints in each direction. The results are extended to parabolic equations. Numerical experiments also indicate that the preconditioned systems exhibit favorable clustering of eigenvalues that leads to a fast convergence rate.     

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     

Numerical study in stochastic homogenization for elliptic partial differential equations: Convergence rate in the size of representative volume elements

We describe the numerical scheme for the discretization and solution of 2D elliptic equations with strongly varying piecewise constant coefficients arising in the stochastic homogenization of multiscale composite materials. An efficient stiffness matrix generation scheme based on assembling the local Kronecker product matrices is introduced. The resulting large linear systems of equations are solved by the preconditioned conjugate gradient iteration with a convergence rate that is independent of the grid size and the variation in jumping coefficients (contrast). Using this solver, we numerically investigate the convergence of the representative volume element (RVE) method in stochastic homogenization that extracts the effective behavior of the random coefficient field. Our numerical experiments confirm the asymptotic convergence rate of systematic error and standard deviation in the size of RVE rigorously established in Gloria et al. The asymptotic behavior of covariances of the homogenized matrix in the form of a quartic tensor is also studied numerically. Our approach allows laptop computation of sufficiently large number of stochastic realizations even for large sizes of the RVE.     

Multiple right-hand side techniques for the numerical simulation of quasistatic electric and magnetic fields

The simulation of slowly varying transient electric high-voltage fields and magnetic fields requires the repeated and successive solution of high-dimensional linear algebraic systems of equations with identical or near-identical system matrices and different right-hand side vectors. For these solution processes which are required within implicit time integration schemes and nonlinear (quasi-)Newton–Raphson methods an iterative multiple right-hand side (mrhs) scheme is used which recycles vector subspaces resulting from previous preconditioned conjugate gradient iteration runs. The combination of this scheme with a subspace projection extrapolation start value generation scheme is discussed. Numerical results for three-dimensional electric and magnetic field simulations are presented and the efficiency of the new schemes re-using eigenvector information from previous iteration processes with different tolerance criteria are compared to those of standard conjugate gradient iterations.     

Interior dual proximal point algorithm using preconditioned conjugate gradient †

Serial and parallel implementations of the interior dual proximal point algorithm for the solution of large linear programs are described. A preconditioned conjugate gradient method is used to solve the linear system of equations that arises at each interior point interation. Numerical results for a set of multicommodity network flow problems are given. For larger problem preconditioned conjugate gradient method outperforms direct methods of solution. In fact it is impossible to handle very large problems by direct methods     

Augmented conjugate gradient. Application in an iterative process for the solution of scattering problems

We discuss the application of an augmented conjugate gradient to the solution of a sequence of linear systems of the same matrix appearing in an iterative process for the solution of scattering problems. The conjugate gradient method applied to the first system generates a Krylov subspace, then for the following systems, a modified conjugate gradient is applied using orthogonal projections on this subspace to compute an initial guess and modified descent directions leading to a better convergence. The scattering problem is treated via an Exact Controllability formulation and a preconditioned conjugate gradient algorithm is introduced. The set of linear systems to be solved are associated to this preconditioning. The efficiency of the method is tested on different 3D acoustic problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

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     

Preconditioned Barzilai-Borwein method for the numerical solution of partial differential equations

The preconditioned Barzilai-Borwein method is derived and applied to the numerical solution of large, sparse, symmetric and positive definite linear systems that arise in the discretization of partial differential equations. A set of well-known preconditioning techniques are combined with this new method to take advantage of the special features of the Barzilai-Borwein method. Numerical results on some elliptic test problems are presented. These results indicate that the preconditioned Barzilai-Borwein method is competitive and sometimes preferable to the preconditioned conjugate gradient method.This author was partially supported by the Parallel and Distributed Computing Center at UCV.This author was partially supported by BID-CONICIT, project M-51940.     

Projection methods for the numerical solution of non-self-adjoint elliptic partial differential equations

We compare the relative performances of two iterative schemes based on projection techniques for the solution of large sparse nonsymmetric systems of linear equations, encountered in the numerical solution of partial differential equations. The Block–Symmetric Successive Over-Relaxation (Block-SSOR) method and the Symmetric–Kaczmarz method are derived from the simplest of projection methods, that is, the Kaczmarz method. These methods are then accelerated using the conjugate gradient method, in order to improve their convergence. We study their behavior on various test problems and comment on the conditions under which one method would be better than the other. We show that while the conjugate-gradient-accelerated Block-SSOR method is more amenable to implementation on vector and parallel computers, the conjugate-gradient accelerated Symmetric–Kaczmarz method provides a viable alternative for use on a scalar machine.     

Duality in conjugate gradient methods

In this paper we show that if the step (displacement) vectors generated by the preconditioned conjugate gradient algorithm are scaled appropriately they may be used to solve equations whose coefficient matrices are the preconditioning matrices of the original equations. The dual algorithms thus obtained are shown to be equivalent to the reverse algorithms of Hegedüs and are subsequently generalised to their block forms. It is finally shown how these may be used to construct dual (or reverse) algorithms for solving equations involving nonsymmetric matrices using only short recurrences, and reasons are suggested why some of these algorithms may be more numerically stable than their primal counterparts. This revised version was published online in June 2006 with corrections to the Cover Date.     

Circulant preconditioners for stochastic automata networks

Summary. Stochastic Automata Networks (SANs) are widely used in modeling communication systems, manufacturing systems and computer systems. The SAN approach gives a more compact and efficient representation of the network when compared to the stochastic Petri nets approach. To find the steady state distribution of SANs, it requires solutions of linear systems involving the generator matrices of the SANs. Very often, direct methods such as the LU decomposition are inefficient because of the huge size of the generator matrices. An efficient algorithm should make use of the structure of the matrices. Iterative methods such as the conjugate gradient methods are possible choices. However, their convergence rates are slow in general and preconditioning is required. We note that the MILU and MINV based preconditioners are not appropriate because of their expensive construction cost. In this paper, we consider preconditioners obtained by circulant approximations of SANs. They have low construction cost and can be inverted efficiently. We prove that if only one of the automata is large in size compared to the others, then the preconditioned system of the normal equations will converge very fast. Numerical results for three different SANs solved by CGS are given to illustrate the fast convergence of our method. Received March 17, 1998 / Revised version received August 16, 1999 / Published online July 12, 2000     

Equivalent operator preconditioning for elliptic problems

The numerical solution of linear elliptic partial differential equations most often involves a finite element or finite difference discretization. To preserve sparsity, the arising system is normally solved using an iterative solution method, commonly a preconditioned conjugate gradient method. Preconditioning is a crucial part of such a solution process. In order to enable the solution of very large-scale systems, it is desirable that the total computational cost will be of optimal order, i.e. proportional to the degrees of freedom of the approximation used, which also induces mesh independent convergence of the iteration. This paper surveys the equivalent operator approach, which has proven to provide an efficient general framework to construct such preconditioners. Hereby one first approximates the given differential operator by some simpler differential operator, and then chooses as preconditioner the discretization of this operator for the same mesh. In this survey we give a uniform presentation of this approach, including theoretical foundation and several practically important applications for both symmetric and nonsymmetric equations and systems, and some nonlinear examples in the context of Newton linearization. Dedicated to the memory of Gene Golub for his friendly manner and for his broad interest and significant impact on numerical analysis.     

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.     

Two-level hierarchically preconditioned conjugate gradient methods for solving linear elasticity finite element equations

In this paper we study and compare some preconditioned conjugate gradient methods for solving large-scale higher-order finite element schemes approximating two- and three-dimensional linear elasticity boundary value problems. The preconditioners discussed in this paper are derived from hierarchical splitting of the finite element space first proposed by O. Axelsson and I. Gustafsson. We especially focus our attention to the implicit construction of preconditioning operators by means of some fixpoint iteration process including multigrid techniques. Many numerical experiments confirm the efficiency of these preconditioners in comparison with classical direct methods most frequently used in practice up to now.