A stable Richardson iteration method for complex linear systems

Summary The Richardson iteration method is conceptually simple, as well as easy to program and parallelize. This makes the method attractive for the solution of large linear systems of algebraic equations with matrices with complex eigenvalues. We change the ordering of the relaxation parameters of a Richardson iteration method proposed by Eiermann, Niethammer and Varga for the solution of such problems. The new method obtained is shown to be stable and to have better convergence properties.Research supported by the National Science Foundation under Grant DMS-8704196     

Optimization of the Runge-Kutta iteration with residual smoothing

Iterative solvers in combination with multi-grid have been used extensively to solve large algebraic systems. One of the best known is the Runge-Kutta iteration. Previously (Haelterman et al. (2009) [3]) we reformulated the Runge-Kutta scheme and established a model of a complete V-cycle which was used to optimize the coefficients of the multi-stage scheme and resulted in a better overall performance. We now look into aspects of central and upwind residual smoothing within the same optimization framework. We consider explicit and implicit residual smoothing and either apply it within the Runge-Kutta time-steps, as a filter for restriction or as a preconditioner for the discretized equations. We also shed a different light on the very high CFL numbers obtained by upwind residual smoothing and point out that damping the high frequencies by residual smoothing is not necessarily a good idea.     

Solution of finite systems of equations by interval iteration

In actual practice, iteration methods applied to the solution of finite systems of equations yield inconclusive results as to the existence or nonexistence of solutions and the accuracy of any approximate solutions obtained. On the other hand, construction of interval extensions of ordinary iteration operators permits one to carry out interval iteration computationally, with results which can give rigorous guarantees of existence or nonexistence of solutions, and error bounds for approximate solutions. Examples are given of the solution of a nonlinear system of equations and the calculation of eigenvalues and eigenvectors of a matrix by interval iteration. Several ways to obtain lower and upper bounds for eigenvalues are given.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041.     

Remarks on Picard-Lindelöf iteration

The paper discusses Picard-Lindelöf iteration for systems of autonomous linear equations on finite intervals, as well as its numerical variants. Most of the discussion is under a model assumption which roughly says that the coupling terms are of moderate size compared with the slow time scales in the problem. It is shown that the speed of convergence is quite independent of the step sizes already for very large time steps. This makes it possible to design strategies in which the mesh gets gradually refined during the iteration in such a way that the iteration error stays essentially on the level of discretization error.This research was supported by the Academy of Finland and by the Institute for Mathematics and its Applications (IMA, Minneapolis with funds provided by NSF). Ulla Miekkala visited IMA with a grant from Tekniikan edisstämissäätiö and carried out the numerical tests.     

On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems

Two iteration methods are proposed to solve real nonsymmetric positive definite Toeplitz systems of linear equations. These methods are based on Hermitian and skew-Hermitian splitting (HSS) and accelerated Hermitian and skew-Hermitian splitting (AHSS). By constructing an orthogonal matrix and using a similarity transformation, the real Toeplitz linear system is transformed into a generalized saddle point problem. Then the structured HSS and the structured AHSS iteration methods are established by applying the HSS and the AHSS iteration methods to the generalized saddle point problem. We discuss efficient implementations and demonstrate that the structured HSS and the structured AHSS iteration methods have better behavior than the HSS iteration method in terms of both computational complexity and convergence speed. Moreover, the structured AHSS iteration method outperforms the HSS and the structured HSS iteration methods. The structured AHSS iteration method also converges unconditionally to the unique solution of the Toeplitz linear system. In addition, an upper bound for the contraction factor of the structured AHSS iteration method is derived. Numerical experiments are used to illustrate the effectiveness of the structured AHSS iteration method.     

On convergence of the inexact Rayleigh quotient iteration with MINRES

For the Hermitian inexact Rayleigh quotient iteration (RQI), we present a new general theory, independent of iterative solvers for shifted inner linear systems. The theory shows that the method converges at least quadratically under a new condition, called the uniform positiveness condition, that may allow the residual norm _ξk≥1${\xi }_k\ge 1$ of the inner linear system at outer iteration k+1$k+1$ and can be considerably weaker than the condition _ξk≤ξ<1${\xi }_k\le \xi <1$ with ξ$\xi$ a constant not near one commonly used in the literature. We consider the convergence of the inexact RQI with the unpreconditioned and tuned preconditioned MINRES methods for the linear systems. Some attractive properties are derived for the residuals obtained by MINRES. Based on them and the new general theory, we make a refined analysis and establish a number of new convergence results. Let ‖_rk‖$\Vert r_k\Vert$ be the residual norm of approximating eigenpair at outer iteration k$k$. Then all the available cubic and quadratic convergence results require _ξk=O(‖_rk‖)${\xi }_k=O\left(\Vert r_k\Vert \right)$ and _ξk≤ξ${\xi }_k\le \xi$ with a fixed ξ$\xi$ not near one, respectively. Fundamentally different from these, we prove that the inexact RQI with MINRES generally converges cubically, quadratically and linearly provided that _ξk≤ξ${\xi }_k\le \xi$ with a constant ξ<1$\xi <1$ not near one, _ξk=1−O(‖_rk‖)${\xi }_k=1-O\left(\Vert r_k\Vert \right)$ and _ξk=1−O(‖_rk‖²)${\xi }_k=1-O\left({\Vert r_k\Vert }^2\right)$, respectively. The new convergence conditions are much more relaxed than ever before. The theory can be used to design practical stopping criteria to implement the method more effectively. Numerical experiments confirm our results.     

Multi-grid dynamic iteration for parabolic equations

We study the method which is obtained when a multi-grid method (in space) is first applied directly to a parabolic intitial-boundary value problem, and discretization in time is done only afterwards. This approach is expected to be well-suited to parallel computation. Further, time marching can be done using different time step-sizes in different parts of the spatial domain.     

Preconditioning Landweber iteration in Hilbert scales

In this paper we investigate convergence of Landweber iteration in Hilbert scales for linear and nonlinear inverse problems. As opposed to the usual application of Hilbert scales in the framework of regularization methods, we focus here on the case s≤0, which (for Tikhonov regularization) corresponds to regularization in a weaker norm. In this case, the Hilbert scale operator L^−2s appearing in the iteration acts as a preconditioner, which significantly reduces the number of iterations needed to match an appropriate stopping criterion. Additionally, we carry out our analysis under significantly relaxed conditions, i.e., we only require instead of which is the usual condition for regularization in Hilbert scales. The assumptions needed for our analysis are verified for several examples and numerical results are presented illustrating the theoretical ones. supported by the Austrian Science Foundation (FWF) under grant SFB/F013     

On CSCS-based iteration methods for Toeplitz system of weakly nonlinear equations

For Toeplitz system of weakly nonlinear equations, by using the separability and strong dominance between the linear and the nonlinear terms and using the circulant and skew-circulant splitting (CSCS) iteration technique, we establish two nonlinear composite iteration schemes, called Picard-CSCS and nonlinear CSCS-like iteration methods, respectively. The advantage of these methods is that they do not require accurate computation and storage of Jacobian matrix, and only need to solve linear sub-systems of constant coefficient matrices. Therefore, computational workloads and computer storage may be saved in actual implementations. Theoretical analysis shows that these new iteration methods are local convergent under suitable conditions. Numerical results show that both Picard-CSCS and nonlinear CSCS-like iteration methods are feasible and effective for some cases.     

Numerical experiments with two approximate inverse preconditioners

We present the results of numerical experiments aimed at comparing two recently proposed sparse approximate inverse preconditioners from the point of view of robustness, cost, and effectiveness. Results for a standard ILU preconditioner are also included. The numerical experiments were carried out on a Cray C98 vector processor. This work was partially supported by the GA AS CR under grant 2030706 and by the grant GA CR 205/96/0921.     

Numerical study on incomplete orthogonal factorization preconditioners

We design, analyse and test a class of incomplete orthogonal factorization preconditioners constructed from Givens rotations, incorporating some dropping strategies and updating tricks, for the solution of large sparse systems of linear equations. Comprehensive accounts about how the preconditioners are coded, what storage is required and how the computation is executed for a given accuracy are presented. A number of numerical experiments show that these preconditioners are competitive with standard incomplete triangular factorization preconditioners when they are applied to accelerate Krylov subspace iteration methods such as GMRES and BiCGSTAB.     

Numerical stability of descent methods for solving linear equations

Summary In this paper we perform a round-off error analysis of descent methods for solving a liner systemAx=b, whereA is supposed to be symmetric and positive definite. This leads to a general result on the attainable accuracy of the computed sequence {x _i } when the method is performed in floating point arithmetic. The general theory is applied to the Gauss-Southwell method and the gradient method. Both methods appear to be well-behaved which means that these methods compute an approximationx _i to the exact solutionA ^–1 b which is the exact solution of a slightly perturbed linear system, i.e. (A+A)x _i =b, A of order A, where is the relative machine precision and · denotes the spectral norm.     

Sets of convergence and stability regions

This paper continues the authors' study of the convergence of dynamic iteration methods for large systems of linear initial value problems. We ask for convergence on [0, ) and show how the convergence can be reduced to a graphical test relating the splitting of the matrix to the stability properties of the discretization method.     

Interval iteration for zeros of systems of equations

Easily verifiable existence and convergence conditions are given for a class of interval iteration algorithms for the enclosure of a zero of a system of nonlinear equations. In particular, a quadratically convergent method is obtained which throughout the iteration uses the same interval enclosure of the derivative.     

Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration

Summary An iteration based upon the Tchebychev polynomials in the complex plane can be used to solve large sparse nonsymmetric linear systems whose eigenvalues lie in the right half plane. The iteration depends upon two parameters which can be chosen from knowledge of the convex hull of the spectrum of the linear operator. This paper deals with a procedure based upon the power method for dynamically estimating the convex hull of the spectrum. The stability of the procedure is discussed in terms of the field of values of the operator. Results show the adaptive procedure to be an effective method of determining parameters. The Tchebychev iteration compares favorably with several competing iterative methods.This work was supported in part by the National Science Foundation under grants NSF GJ-36393 and DCR 74-23679 (NSF)     

The strength of nonstationary iteration

This is the second of three papers in which we study global convergence of iterations using linear information for the solution of nonlinear equations. In Wasilkowski [6] we proved that for the class of all analytic scalar complex functions having only simple zeros there exists no globally convergentstationary iteration using linear information. Here we exhibit anonstationary iteration using linear information which is globally convergent even for the multivariate and abstract cases. This demonstrates the strength of nonstationary iteration. In Wasilkowski [7] we shall prove that any globally convergent iteration using linear information hasinfinite complexity even for the class of scalar complex polynomials having only simple zeros.     

Current inverse iteration software can fail

Inverse iteration is widley used to compute the eigenvectors of a matrix once accurate eigenvalues are known. We discuss various issues involved in any implementation of inverse iteration for real, symmetric matrices. Current implementations resort to reorthogonalization when eigenvalues agree to more than three digits relative to the norm. Such reorthogonalization can have unexpected consequences. Indeed, as we show in this paper, the implementations in EISPACK and LAPACK may fail. We illustrate with both theoretical and empirical failures. This research was supported, while the author was at the University of California, Berkeley, in part by DARPA Contract No. DAAL03-91-C-0047 through a subcontract with the University of Tennessee, DOE Contract No. DOE-W-31-109-Eng-38 through a subcontract with Argonne National Laboratory, by DOE Grant No. DE-FG03-94ER25219, NSF Grant Nos. ASC-9313958 and CDA-9401156, and DOE Contract DE-AC06-76RLO 1830 through the Environmental Molecular Sciences construction project at Pacific Northwest National Laboraotry (PNNL).     

Accelerated Landweber iterations for the solution of ill-posed equations

Summary In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept.If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy.To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage.Numerical examples are given including a comparison to the method of conjugate gradients.This research was sponsored by the Deutsche Forschungsgemeinschaft (DFG).     

On the convergence of splittings for semidefinite linear systems

Recently, Lee et al. [Young-ju Lee, Jinbiao Wu, Jinchao Xu, Ludmil Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl. 28 (2006) 634-641] introduce new criteria for the semi-convergence of general iterative methods for semidefinite linear systems based on matrix splitting. The new conditions generalize the classical notion of P-regularity introduced by Keller [H.B. Keller, On the solution of singular and semidefinite linear systems by iterations, SIAM J. Numer. Anal. 2 (1965) 281-290]. In view of their results, we consider here stipulations on a splitting A=M-N, which lead to fixed point systems such that, the iterative scheme converges to a weighted Moore-Penrose solution to the system Ax=b. Our results extend the result of Lee et al. to a more general case and we also show that it requires less restrictions on the splittings than Keller’s P-regularity condition to ensure the convergence of iterative scheme.     

Application of modified homotopy perturbation method for solving the augmented systems

In this paper, a new approach is proposed for solving the augmented systems. Based on the modified homotopy perturbation method, we construct the new iterative methods and derive the sufficient and necessary conditions for guaranteeing its convergence. Some numerical experiments show that this method is more simple and effective.