Efficient implementation of symplectic implicit Runge-Kutta schemes with simplified Newton iterations

We are concerned with the efficient implementation of symplectic implicit Runge-Kutta (IRK) methods applied to systems of Hamiltonian ordinary differential equations by means of Newton-like iterations. We pay particular attention to time-symmetric symplectic IRK schemes (such as collocation methods with Gaussian nodes). For an s-stage IRK scheme used to integrate a \(\dim \)-dimensional system of ordinary differential equations, the application of simplified versions of Newton iterations requires solving at each step several linear systems (one per iteration) with the same \(s\dim \times s\dim \) real coefficient matrix. We propose a technique that takes advantage of the symplecticity of the IRK scheme to reduce the cost of methods based on diagonalization of the IRK coefficient matrix. This is achieved by rewriting one step of the method centered at the midpoint on the integration subinterval and observing that the resulting coefficient matrix becomes similar to a skew-symmetric matrix. In addition, we propose a C implementation (based on Newton-like iterations) of Runge-Kutta collocation methods with Gaussian nodes that make use of such a rewriting of the linear system and that takes special care in reducing the effect of round-off errors. We report some numerical experiments that demonstrate the reduced round-off error propagation of our implementation.     

Half-explicit Runge-Kutta methods with explicit stages for differential-algebraic systems of index 2

Usually the straightforward generalization of explicit Runge-Kutta methods for ordinary differential equations to half-explicit methods for differential-algebraic systems of index 2 results in methods of orderq≤2. The construction of higher order methods is simplified substantially by a slight modification of the method combined with an improved strategy for the computation of the algebraic solution components. We give order conditions up to orderq=5 and study the convergence of these methods. Based on the fifth order method of Dormand and Prince the fifth order half-explicit Runge-Kutta method HEDOP5 is constructed that requires the solution of 6 systems of nonlinear equations per step of integration.     

Block Two-stage Methods for Singular Systems and Markov Chains

The use of block two-stage methods for the iterative solution of consistent singular linear systems is studied. In these methods, suitable for parallel computations, different blocks, i.e., smaller linear systems, can be solved concurrently by different processors. Each of these smaller systems are solved by an (inner) iterative method. Hypotheses are provided for the convergence of non-stationary methods, i.e., when the number of inner iterations may vary from block to block and from one outer iteration to another. It is shown that the iteration matrix corresponding to one step of the block method is convergent, i.e., that its powers converge to a limit matrix. A theorem on the convergence of the infinite product of matrices with the same eigenspace corresponding to the eigenvalue 1 is proved, and later used as a tool in the convergence analysis of the block method. The methods studied can be used to solve any consistent singular system, including discretizations of certain differential equations. They can also be used to find stationary probability distribution of Markov chains. This last application is considered in detail.     

Runge-Kutta Methods for the Numerical Solution of Stiff Semilinear Systems

This paper studies the stability and convergence properties of general Runge-Kutta methods when they are applied to stiff semilinear systems y(t) = J(t)y(t) + g(t, y(t)) with the stiffness contained in the variable coefficient linear part.We consider two assumptions on the relative variation of the matrix J(t) and show that for each of them there is a family of implicit Runge-Kutta methods that is suitable for the numerical integration of the corresponding stiff semilinear systems, i.e. the methods of the family are stable, convergent and the stage equations possess a unique solution. The conditions on the coefficients of a method to belong to these families turn out to be essentially weaker than the usual algebraic stability condition which appears in connection with the B-stability and convergence for stiff nonlinear systems. Thus there are important RK methods which are not algebraically stable but, according to our theory, they are suitable for the numerical integration of semilinear problems.This paper also extends previous results of Burrage, Hundsdorfer and Verwer on the optimal convergence of implicit Runge-Kutta methods for stiff semilinear systems with a constant coefficients linear part.     

Numerical Solution of a Fluid Filtration Problem in a Fractured Medium by Using the Domain Decomposition Method

Under consideration are the numerical methods for simulation of a fluid flow in fractured porous media. The fractures are taken into account explicitly by using a discrete fracture model. The formulated single-phase filtering problem is approximated by an implicit finite element method on unstructured grids that resolve fractures at the grid level. The systems of linear algebraic equations (SLAE) are solved by the iterative methods of domain decomposition in the Krylov subspaces using the KRYLOVlibrary of parallel algorithms. The results of solving some model problem are presented. A study is conducted of the efficiency of the computational implementation for various values of contrast coefficients which significantly affect the condition number and the number of iterations required for convergence of the method.     

A unified approach to global convergence of trust region methods for nonsmooth optimization

This paper investigates the global convergence of trust region (TR) methods for solving nonsmooth minimization problems. For a class of nonsmooth objective functions called regular functions, conditions are found on the TR local models that imply three fundamental convergence properties. These conditions are shown to be satisfied by appropriate forms of Fletcher's TR method for solving constrained optimization problems, Powell and Yuan's TR method for solving nonlinear fitting problems, Zhang, Kim and Lasdon's successive linear programming method for solving constrained problems, Duff, Nocedal and Reid's TR method for solving systems of nonlinear equations, and El Hallabi and Tapia's TR method for solving systems of nonlinear equations. Thus our results can be viewed as a unified convergence theory for TR methods for nonsmooth problems.Research supported by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Corresponding author.     

The Monte-Carlo algorithm for the solving of systems of linear algebraic equations by the Seidel method

The iteration algorithm is used to solve systems of linear algebraic equations by the Monte-Carlo method. Each next iteration is simulated as a random vector such that its expectation coincides with the Seidel approximation of the iteration process. We deduce a system of linear equations such that mutual correlations of components of the limit vector and correlations of two iterations satisfy them. We prove that limit dispersions of the random vector of solutions of the system exist and are finite.     

On the order of iterated defect correction

Summary In a recent article [2] Frank and Überhuber define and motivate the method of iterated defect correction for Runge-Kutta methods. They prove a theorem on the order of that method using the theory of asymptotic expansions.In this paper we give similar results using the theory of Butcher series (see [4]). Our proofs are purely algebraic. We don't restrict our considerations to Runge-Kutta methods, but we admit arbitrary linear one-step methods. At the same time we consider more general defect functions as in [2].     

Convergence of nested classical iterative methods for linear systems

Summary Classical iterative methods for the solution of algebraic linear systems of equations proceed by solving at each step a simpler system of equations. When this system is itself solved by an (inner) iterative method, the global method is called a two-stage iterative method. If this process is repeated, then the resulting method is called a nested iterative method. We study the convergence of such methods and present conditions on the splittings corresponding to the iterative methods to guarantee convergence forany number of inner iterations. We also show that under the conditions presented, the spectral radii of the global iteration matrices decrease when the number of inner iterations increases. The proof uses a new comparison theorem for weak regular splittings. We extend our results to larger classes of iterative methods, which include iterative block Gauss-Seidel. We develop a theory for the concatenation of such iterative methods. This concatenation appears when different numbers of inner interations are performed at each outer step. We also analyze block methods, where different numbers of inner iterations are performed for different diagonal blocks.Dedicated to Richard S. Varga on the occasion of his sixtieth birthdayP.J. Lanzkron was supported by Exxon Foundation Educational grant 12663 and the UNISYS Corporation; D.J. Rose was supported by AT&T Bell Laboratories, the Microelectronic Center of North Carolina and the Office of Naval Research under contract number N00014-85-K-0487; D.B. Szyld was supported by the National Science Foundation grant DMS-8807338.     

Waveform relaxation methods for implicit differential equations

We apply a Runge-Kutta-based waveform relaxation method to initial-value problems for implicit differential equations. In the implementation of such methods, a sequence of nonlinear systems has to be solved iteratively in each step of the integration process. The size of these systems increases linearly with the number of stages of the underlying Runge-Kutta method, resulting in high linear algebra costs in the iterative process for high-order Runge-Kutta methods. In our earlier investigations of iterative solvers for implicit initial-value problems, we designed an iteration method in which the linear algebra costs are almost independent of the number of stages when implemented on a parallel computer system. In this paper, we use this parallel iteration process in the Runge-Kutta waveform relaxation method. In particular, we analyse the convergence of the method. The theoretical results are illustrated by a few numerical examples.     

Solutions for the Linear-Quadratic Control Problem of Markov Jump Linear Systems

The paper is concerned with recursive methods for obtaining the stabilizing solution of coupled algebraic Riccati equations arising in the linear-quadratic control of Markovian jump linear systems by solving at each iteration uncoupled algebraic Riccati equations. It is shown that the new updates carried out at each iteration represent approximations of the original control problem by control problems with receding horizon, for which some sequences of stopping times define the terminal time. Under this approach, unlike previous results, no initialization conditions are required to guarantee the convergence of the algorithms. The methods can be ordered in terms of number of iterations to reach convergence, and comparisons with existing methods in the current literature are also presented. Also, we extend and generalize current results in the literature for the existence of the mean-square stabilizing solution of coupled algebraic Riccati equations.     

Time integration of index 1 DAEs with Rosenbrock methods using Krylovsubspace techniques

The derivation of Rosenbrock‐Krylov methods for index 1 DAEs involves two well known techniques: a limit process which transforms a singular perturbed ODE to an index 1 DAE and the use of Krylov iterations instead of direct linear solvers for the stage equations. We show that our derived class of Rosenbrock‐Krylov schemes is independent of the order in which we apply these techniques. We also conclude that for convergence a rather accurate solution of the algebraic part is always needed.     

Reversible methods of Runge-Kutta type for Index-2 DAEs

Summary. A new interpretation of Runge-Kutta methods for differential algebraic equations (DAEs) of index 2 is presented, where a step of the method is described in terms of a smooth map (smooth also with respect to the stepsize). This leads to a better understanding of the convergence behavior of Runge-Kutta methods that are not stiffly accurate. In particular, our new framework allows for the unified study of two order-improving techniques for symmetric Runge-Kutta methods (namely post-projection and symmetric projection) specially suited for solving reversible index-2 DAEs.Mathematics Subject Classification (1991): 65L05, 65L06     

Parallel iterative linear solvers for multistep Runge-Kutta methods

This paper deals with solving stiff systems of differential equations by implicit Multistep Runge-Kutta (MRK) methods. For this type of methods, nonlinear systems of dimension sd arise, where s is the number of Runge-Kutta stages and d the dimension of the problem. Applying a Newton process leads to linear systems of the same dimension, which can be very expensive to solve in practice. With a parallel iterative linear system solver, especially designed for MRK methods, we approximate these linear systems by s systems of dimension d, which can be solved in parallel on a computer with s processors. In terms of Jacobian evaluations and LU-decompositions, the k-steps-stage MRK applied with this technique is on s processors equally expensive as the widely used k-step Backward Differentiation Formula on 1 processor, whereas the stability properties are better than that of BDF. A simple implementation of both methods shows that, for the same number of Newton iterations, the accuracy delivered by the new method is higher than that of BDF.     

Preconditioning waveform relaxation iterations for differential systems

We discuss preconditioning and overlapping of waveform relaxation methods for sparse linear differential systems. It is demonstrated that these techniques significantly improve the speed of convergence of the waveform relaxation iterations resulting from application of various modes of block Gauss-Jacobi and block Gauss-Seidel methods to differential systems. Numerical results are presented for linear systems resulting from semi-discretization of the heat equation in one and two space variables. It turns out that overlapping is very effective for the system corresponding to the one-dimensional heat equation and preconditioning is very effective for the system corresponding to the two-dimensional case.The work of the second author was supported by the National Science Foundation under grant NSF DMS 92-08048.     

A specialized primal-dual interior point method for the plastic truss layout optimization

We are concerned with solving linear programming problems arising in the plastic truss layout optimization. We follow the ground structure approach with all possible connections between the nodal points. For very dense ground structures, the solutions of such problems converge to the so-called generalized Michell trusses. Clearly, solving the problems for large nodal densities can be computationally prohibitive due to the resulting huge size of the optimization problems. A technique called member adding that has correspondence to column generation is used to produce a sequence of smaller sub-problems that ultimately approximate the original problem. Although these sub-problems are significantly smaller than the full formulation, they still remain large and require computationally efficient solution techniques. In this article, we present a special purpose primal-dual interior point method tuned to such problems. It exploits the algebraic structure of the problems to reduce the normal equations originating from the algorithm to much smaller linear equation systems. Moreover, these systems are solved using iterative methods. Finally, due to high degree of similarity among the sub-problems after preforming few member adding iterations, the method uses a warm-start strategy and achieves convergence within fewer interior point iterations. The efficiency and robustness of the method are demonstrated with several numerical experiments.     

Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers

Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples.     

An algebraic preconditioning method for M‐matrices: linear versus non‐linear multilevel iteration

In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non‐linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W‐cycles only need diagonal solvers on all levels and additionally evaluate a second‐degree matrix polynomial (linear case), or, perform ν inner GCG‐type iterations (non‐linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non‐linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non‐linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured‐grid problems. Copyright © 2002 John Wiley & Sons, Ltd.     

Inner iterations in the shift-invert residual Arnoldi method and the Jacobi-Davidson method

We establish a general convergence theory of the Shift-Invert Residual Arnoldi(SIRA)method for computing a simple eigenvalue nearest to a given targetσand the associated eigenvector.In SIRA,a subspace expansion vector at each step is obtained by solving a certain inner linear system.We prove that the inexact SIRA method mimics the exact SIRA well,i.e.,the former uses almost the same outer iterations to achieve the convergence as the latter does if all the inner linear systems are iteratively solved with low or modest accuracy during outer iterations.Based on the theory,we design practical stopping criteria for inner solves.Our analysis is on one step expansion of subspace and the approach applies to the Jacobi-Davidson(JD)method with the fixed targetσas well,and a similar general convergence theory is obtained for it.Numerical experiments confirm our theory and demonstrate that the inexact SIRA and JD are similarly effective and are considerably superior to the inexact SIA.     

A unified approach to parallel space decomposition methods

We consider (relaxed) additive and multiplicative iterative space decomposition methods for the minimization of sufficiently smooth functionals without constraints. We develop a general framework which unites existing approaches from both parallel optimization and finite elements. Specifically this work unifies earlier research on the parallel variable distribution method in minimization, space decomposition methods for convex functionals, algebraic Schwarz methods for linear systems and splitting methods for linear least squares. We develop a general convergence theory within this framework, which provides several new results as well as including known convergence results.