On hybrid iterative methods for nonsymmetric systems of linear equations

Summary. Hybrid methods for the solution of systems of linear equations consist of a first phase where some information about the associated coefficient matrix is acquired, and a second phase in which a polynomial iteration designed with respect to this information is used. Most of the hybrid algorithms proposed recently for the solution of nonsymmetric systems rely on the direct use of eigenvalue estimates constructed by the Arnoldi process in Phase I. We will show the limitations of this approach and propose an alternative, also based on the Arnoldi process, which approximates the field of values of the coefficient matrix and of its inverse in the Krylov subspace. We also report on numerical experiments comparing the resulting new method with other hybrid algorithms. Received May 27, 1993 / Revised version received November 14, 1994     

An adaptive Chebyshev iterative method\newline for nonsymmetric linear systems based on modified moments

Summary. Large, sparse nonsymmetric systems of linear equations with a matrix whose eigenvalues lie in the right half plane may be solved by an iterative method based on Chebyshev polynomials for an interval in the complex plane. Knowledge of the convex hull of the spectrum of the matrix is required in order to choose parameters upon which the iteration depends. Adaptive Chebyshev algorithms, in which these parameters are determined by using eigenvalue estimates computed by the power method or modifications thereof, have been described by Manteuffel [18]. This paper presents an adaptive Chebyshev iterative method, in which eigenvalue estimates are computed from modified moments determined during the iterations. The computation of eigenvalue estimates from modified moments requires less computer storage than when eigenvalue estimates are computed by a power method and yields faster convergence for many problems. Received May 13, 1992/Revised version received May 13, 1993     

Necessary and sufficient conditions for the convergence of Orthomin(k) on singular and inconsistent linear systems

Summary. We consider the convergence of Orthomin(k) on singular and inconsistent linear systems. Criteria for the breakdown of Orthomin(k) are discussed and analyzed. Moreover, necessary and sufficient conditions for the convergence of Orthomin(k) for any right hand side are given, and a rate of convergence is provided as well. Finally, numerical experiments are shown to confirm the convergence theorem. Received April 1, 1995 / Revised version received October 1, 1997 / Published online July 12, 2000     

Convergence of block two-stage iterative methods for symmetric positive definite systems

Summary. We study the convergence of two-stage iterative methods for solving symmetric positive definite (spd) systems. The main tool we used to derive the iterative methods and to analyze their convergence is the diagonally compensated reduction (cf. [1]). Received December 11, 1997 / Revised version received March 25, 1999 / Published online May 30, 2001     

Asynchronous two-stage iterative methods

Summary. Parallel block two-stage iterative methods for the solution of linear systems of algebraic equations are studied. Convergence is shown for monotone matrices and for -matrices. Two different asynchronous versions of these methods are considered and their convergence investigated. Received September 7, 1993 / Revised version received April 21, 1994     

On multisplitting methods for band matrices

Summary. We present new theoretical results on two classes of multisplitting methods for solving linear systems iteratively. These classes are based on overlapping blocks of the underlying coefficient matrix which is assumed to be a band matrix. We show that under suitable conditions the spectral radius of the iteration matrix does not depend on the weights of the method even if these weights are allowed to be negative. For a certain class of splittings we prove an optimality result for with respect to the weights provided that is an M–matrix. This result is based on the fact that the multisplitting method can be represented by a single splitting which in our situation surprisingly turns out to be a regular splitting. Furthermore we show by numerical examples that weighting factors may considerably improve the convergence. Received July 18, 1994 / Revised version received November 20, 1995     

New look-ahead Lanczos-type algorithms for linear systems

Summary. A breakdown (due to a division by zero) can arise in the algorithms for implementing Lanczos' method because of the non-existence of some formal orthogonal polynomials or because the recurrence relationship used is not appropriate. Such a breakdown can be avoided by jumping over the polynomials involved. This strategy was already used in some algorithms such as the MRZ and its variants. In this paper, we propose new implementations of the recurrence relations of these algorithms which only need the storage of a fixed number of vectors, independent of the length of the jump. These new algorithms are based on Horner's rule and on a different way for computing the coefficients of the recurrence relationships. Moreover, these new algorithms seem to be more stable than the old ones and they provide better numerical results. Numerical examples and comparisons with other algorithms will be given. Received September 2, 1997 / Revised version received July 24, 1998     

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     

Accelerated monotone iterative methods for finite difference equations of reaction-diffusion

This paper is concerned with numerical methods for a finite difference system of reaction-diffusion-convection equation under nonlinear boundary condition. Various monotone iterative methods are presented, and each of these methods leads to an existence-comparison theorem as well as a computational algorithm for numerical solutions. The monotone property of the iterations gives improved upper and lower bounds of the solution in each iteration, and the rate of convergence of the iterations is either quadratic or nearly quadratic depending on the property of the nonlinear function. Application is given to a model problem from chemical engineering, and some numerical results, including a test problem with known analytical solution, are presented to illustrate the various rates of convergence of the iterations. Received November 2, 1995 / Revised version received February 10, 1997     

Block and asynchronous two-stage methods for mildly nonlinear systems

Block parallel iterative methods for the solution of mildly nonlinear systems of equations of the form are studied. Two-stage methods, where the solution of each block is approximated by an inner iteration, are treated. Both synchronous and asynchronous versions are analyzed, and both pointwise and blockwise convergence theorems provided. The case where there are overlapping blocks is also considered. The analysis of the asynchronous method when applied to linear systems includes cases not treated before in the literature. Received June 5, 1997 / Revised version received December 29, 1997     

Finite element methods and their convergence for elliptic and parabolic interface problems

In this paper, we consider the finite element methods for solving second order elliptic and parabolic interface problems in two-dimensional convex polygonal domains. Nearly the same optimal -norm and energy-norm error estimates as for regular problems are obtained when the interfaces are of arbitrary shape but are smooth, though the regularities of the solutions are low on the whole domain. The assumptions on the finite element triangulation are reasonable and practical. Received July 7, 1996 / Revised version received March 3, 1997     

Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods

Summary. Given a nonsingular matrix , and a matrix of the same order, under certain very mild conditions, there is a unique splitting , such that . Moreover, all properties of the splitting are derived directly from the iteration matrix . These results do not hold when the matrix is singular. In this case, given a matrix and a splitting such that , there are infinitely many other splittings corresponding to the same matrices and , and different splittings can have different properties. For instance, when is nonnegative, some of these splittings can be regular splittings, while others can be only weak splittings. Analogous results hold in the symmetric positive semidefinite case. Given a singular matrix , not for all iteration matrices there is a splitting corresponding to them. Necessary and sufficient conditions for the existence of such splittings are examined. As an illustration of the theory developed, the convergence of certain alternating iterations is analyzed. Different cases where the matrix is monotone, singular, and positive (semi)definite are studied. Received September 5, 1995 / Revised version received April 3, 1996     

Collocation methods for solving linear differential-algebraic boundary value problems

Summary. We consider boundary value problems for linear differential-algebraic equations with variable coefficients with no restriction on the index. A well-known regularisation procedure yields an equivalent index one problem with d differential and a=n-d algebraic equations. Collocation methods based on the regularised BVP approximate the solution x by a continuous piecewise polynomial of degree k and deliver, in particular, consistent approximations at mesh points by using the Radau schemes. Under weak assumptions, the collocation problems are uniquely and stably solvable and, if the unique solution x is sufficiently smooth, convergence of order min {k+1,2k-1} and superconvergence at mesh points of order 2k-1 is shown. Finally, some numerical experiments illustrating these results are presented. Received October 1, 1999 / Revised version received April 25, 2000 / Published online December 19, 2000     

Symmetric collocation methods for linear differential-algebraic boundary value problems

Summary. We present symmetric collocation methods for linear differential-algebraic boundary value problems without restrictions on the index or the structure of the differential-algebraic equation. In particular, we do not require a separation into differential and algebraic solution components. Instead, we use the splitting into differential and algebraic equations (which arises naturally by index reduction techniques) and apply Gau?-type (for the differential part) and Lobatto-type (for the algebraic part) collocation schemes to obtain a symmetric method which guarantees consistent approximations at the mesh points. Under standard assumptions, we show solvability and stability of the discrete problem and determine its order of convergence. Moreover, we show superconvergence when using the combination of Gau? and Lobatto schemes and discuss the application of interpolation to reduce the number of function evaluations. Finally, we present some numerical comparisons to show the reliability and efficiency of the new methods. Received September 22, 2000 / Revised version received February 7, 2001 / Published online August 17, 2001     

A class of ABS algorithms for Diophantine linear systems

Summary. Systems of integer linear (Diophantine) equations arise from various applications. In this paper we present an approach, based upon the ABS methods, to solve a general system of linear Diophantine equations. This approach determines if the system has a solution, generalizing the classical fundamental theorem of the single linear Diophantine equation. If so, a solution is found along with an integer Abaffian (rank deficient) matrix such that the integer combinations of its rows span the integer null space of the cofficient matrix, implying that every integer solution is obtained by the sum of a single solution and an integer combination of the rows of the Abaffian. We show by a counterexample that, in general, it is not true that any set of linearly independent rows of the Abaffian forms an integer basis for the null space, contrary to a statement by Egervary. Finally we show how to compute the Hermite normal form for an integer matrix in the ABS framework. Received July 9, 1999 / Revised version received May 8, 2000 / Published online May 4, 2001     

Regions of exact convergence of the USSOR method applied on generalized consistently ordered matrices

Summary. Using the theory of nonnegative matrices and regular splittings, exact convergence and divergence domains of the Unsymmetric Successive Overrelaxation (USSOR) method, as it pertains to the class of Generalized Consistently Ordered (GCO) matrices, are determined. Our recently derived upper bounds, for the convergence of the USSOR method, re also used as effective tools. Received October 17, 1993 / Revised version received December 19, 1994     

On the discrepancy principle for iterative and parametric methods to solve linear ill-posed equations

Summary. For the numerical solution of (non-necessarily well-posed) linear equations in Banach spaces we consider a class of iterative methods which contains well-known methods like the Richardson iteration, if the associated resolvent operator fulfils a condition with respect to a sector. It is the purpose of this paper to show that for given noisy right-hand side the discrepancy principle (being a stopping rule for the iteration methods belonging to the mentioned class) defines a regularization method, and convergence rates are proved under additional smoothness conditions on the initial error. This extends similar results obtained for positive semidefinite problems in Hilbert spaces. Then we consider a class of parametric methods which under the same resolvent condition contains the method of the abstract Cauchy problem, and (under a weaker resolvent condition) the iterated method of Lavrentiev. A modified discrepancy principle is formulated for them, and finally numerical illustrations are presented. Received August 29, 1994 / Revised version received September 19, 1995     

On the convergence of Runge–Kutta methods for stiff non linear differential equations

Summary. This paper studies the convergence properties of general Runge–Kutta methods when applied to the numerical solution of a special class of stiff non linear initial value problems. It is proved that under weaker assumptions on the coefficients of a Runge–Kutta method than in the standard theory of B-convergence, it is possible to ensure the convergence of the method for stiff non linear systems belonging to the above mentioned class. Thus, it is shown that some methods which are not algebraically stable, like the Lobatto IIIA or A-stable SIRK methods, are convergent for the class of stiff problems under consideration. Finally, some results on the existence and uniqueness of the Runge–Kutta solution are also presented. Received November 18, 1996 / Revised version received October 6, 1997     

On nonlinear generalized conjugate gradient methods

Summary. The Generalized Conjugate Gradient method (see [1]) is an iterative method for nonsymmetric linear systems. We obtain generalizations of this method for nonlinear systems with nonsymmetric Jacobians. We prove global convergence results. Received April 29, 1992 / Revised version received November 18, 1993     

Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors

Summary. An adaptive Richardson iteration method is described for the solution of large sparse symmetric positive definite linear systems of equations with multiple right-hand side vectors. This scheme ``learns' about the linear system to be solved by computing inner products of residual matrices during the iterations. These inner products are interpreted as block modified moments. A block version of the modified Chebyshev algorithm is presented which yields a block tridiagonal matrix from the block modified moments and the recursion coefficients of the residual polynomials. The eigenvalues of this block tridiagonal matrix define an interval, which determines the choice of relaxation parameters for Richardson iteration. Only minor modifications are necessary in order to obtain a scheme for the solution of symmetric indefinite linear systems with multiple right-hand side vectors. We outline the changes required. Received April 22, 1993