Inexact Methods in the Numerical Solution of Stiff Initial Value Problems

Inexact Newton methods can be effectively used in codes for large stiff initial value problems for ordinary differential equations. In this paper we give a new convergence result for Inexact Newton methods. Further, we indicate how this general result can be used and actually implemented to obtain an efficient code for solving stiff initial value problems. Received: March 12, 1998; revised March 31, 1999     

Error of Partitioned Runge-Kutta Methods for Multiple Stiff Singular Perturbation Problems

The main purpose of this paper is to deal with error behaviour of partitioned Runge-Kutta methods for one-parameter multiple stiff singular perturbation problems whose stiffness is caused by a small parameter ε and some other factors and to present some quantitative convergence results. Received November 30, 1998; revised August 10, 1999     

Convergence Results of One-Leg and Linear Multistep Methods for Multiply Stiff Singular Perturbation Problems

One-leg methods and linear multistep methods are two class of important numerical methods applied to stiff initial value problems of ordinary differential equations. The purpose of this paper is to present some convergence results of A-stable one-leg and linear multistep methods for one-parameter multiply stiff singular perturbation problems and their corresponding reduced problems which are a class of stiff differential-algebraic equations. Received April 14, 2000; revised June 30, 2000     

On the Attainable Order of Collocation Methods for the Neutral Functional-Differential Equations with Proportional Delays

In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫₀ ^t by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE): and the delay Volterra integro-differential equation (DVIDE) : with proportional delays p _i t and q _i t, 0<p _i ,q _i ≤1 and complex numbers a,b _i and c _i . We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u _it (t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M _m (t) of v(th) or M^ _m (t) of u _it (th), t∈[0,1] such that the rational approximant v(h) or u _it (h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h ^{2 m +1}). If they exist, then we actually give the conditions of M _m (t) and M^ _m (t), respectively. Received September 17, 1998; revised September 30, 1999     

Solving Third Order Differential Equations with Maximal Symmetry Group

The largest group of Lie symmetries that a third-order ordinary differential equation (ode) may allow has seven parameters. Equations sharing this property belong to a single equivalence class with a canonical representative v ^′′′(u)=0. Due to this simple canonical form, any equation belonging to this equivalence class may be identified in terms of certain constraints for its coefficients. Furthermore a set of equations for the transformation functions to canonical form may be set up for which large classes of solutions may be determined algorithmically. Based on these steps a solution algorithm is described for any equation with this symmetry type which resembles a similar scheme for second order equations with projective symmetry group. Received March 9, 2000; revised June 8, 2000     

A New Multisection Technique in Interval Methods for Global Optimization

A new multisection technique in interval methods for global optimization is investigated, and numerical tests demonstrate that the efficiency of the underlying global optimization method can be improved substantially. The heuristic rule is based on experiences that suggest the subdivision of the current subinterval into a larger number of pieces only if it is located in the neighbourhood of a minimizer point. An estimator of the proximity of a subinterval to the region of attraction to a minimizer point is utilized. According to the numerical study made, the new multisection strategies seem to be indispensable, and can improve both the computational and the memory complexity substantially. Received May 31, 1999; revised January 20, 2000     

Equivalence Classes,Symmetries and Solutions of Linear Third-order Differential Equations

 The subject of this article are third-order differential equations that may be linearized by a variable change. To this end, at first the equivalence classes of linear equations are completely described. Thereafter it is shown how they combine into symmetry classes that are determined by the various symmetry types. An algorithm is presented allowing it to transform linearizable equations by hyperexponential transformations into linear form from which solutions may be obtained more easily. Several examples are worked out in detail. Received February 18, 2002; revised May 10, 2002 Published online: October 24, 2002     

Runge Kutta Type Methods for Isodynamical Matrix Flows: Applications to Balanced Realizations

Recently several numerical methods have been proposed for solving isospectral problems which are matrix differential systems whose solutions preserve the spectrum during the evolution. In this paper we consider matrix differential systems called isodynamical flows in which only a component of the matrix solution preserves the eigenvalues during the evolution and we propose procedures for their numerical solution. Applications of such numerical procedures may be found in systems theory, in particular in balancing realization problems. Several numerical tests will be reported. Received April 27, 2001; revised October 25, 2001 Published online February 18, 2002     

Uniformly Effective Numerical Methods for Hyperbolic Systems

A unified method to compute compressible and incompressible flows is presented. Accuracy and efficiency do not degrade as the Mach number tends to zero. A staggered scheme solved with a pressure correction method is used. The equation of state is arbitrary. A Riemann problem for the barotropic Euler equations with nonconvex equation of state is solved exactly and numericaly. A hydrodynamic flow with cavitation in which the Mach number varies between 10⁻³ and 20 is computed. Unified methods for compressible and incompressible flows are further discussed for the flow of a perfect gas. The staggered scheme with pressure correction is found to have Mach-uniform accuracy and efficiency, and for the fully compressible case the accuracy is comparable with that of established schemes for compressible flows. Received October 20, 1999; revised May 26, 2000     

Computation of Lagrange Multipliers for Linear Least Squares Problems with Equality Constraints

Received December 21, 2000; revised June 7, 2001     

On the Stability of the Direct Elimination Method for Equality Constrained Least Squares Problems

A backward error analysis of the direct elimination method for linear equality constrained least squares problems is presented. It is proved that the solution computed by the method is the exact solution of a perturbed problem and bounds for data perturbations are given. The numerical stability of the method is related to the way in which the constraints are used to eliminate variables and these theoretical conclusions are confirmed by a numerical example. Received February 15, 1999; revised December 10, 1999     

A Robust Smoother for Convection-Diffusion Problems with Closed Characteristics

In this paper we analyze a model problem for the convection-diffusion equation where the reduced problem has closed characteristics. A full upwinding finite difference scheme is used to discretize the problem. Additionally to the strength of the convection, an arbitrary amount of crosswind-diffusion can be added on the discrete level. We present a smoother which is robust w.r.t. the strength of convection and the amount of crosswind-diffusion. It is of Gauss–Seidel type using a downwind ordering. To handle the cyclic dependencies a frequency-filtering algorithm is used. The algorithm is of nearly optimal complexity ?(n log n). It is proved that it fulfills a robust smoothing property.     

hp-adaptive Two-Level Methods for Boundary Integral Equations on Curves

p - and hp-versions of the Galerkin boundary element method for hypersingular and weakly singular integral equations of the first kind on curves. We derive a-posteriori error estimates that are based on stable two-level decompositions of enriched ansatz spaces. The Galerkin errors are estimated by inverting local projection operators that are defined on small subspaces of the second level. A p-adaptive and two hp-adaptive algorithms are defined and numerical experiments confirm their efficiency. Received August 30, 2000; revised April 3, 2001     

On Solving Periodically Perturbed Nonconservative Systems with a One-Parameter Embedding

The paper is concerned with solving the periodically perturbed nonconservative systems, which will be differentiably imbedded into an one-parameter family of operators. The solution of the systems is then found by continuing the solution curve of operator homotopy. When the Newton-Kantorovich's procedure is applied to the corresponding operator equations, an efficient algorithm is derived. Furthermore, the suitable condition on the optimum step size of the parameter is provided for assuring that the approximation solution will converge to the unique solution of the nonlinear periodically boundary value problem. Finally, the theoretical results are in excellent agreement with the numerical examples. Received August 14, 2001; revised December 19, 2001 Published online: November 18, 2002     

Solution of Large Scale Algebraic Matrix Riccati Equations by Use of Hierarchical Matrices

In previous papers, a class of hierarchical matrices (ℋ-matrices) is introduced which are data-sparse and allow an approximate matrix arithmetic of almost optimal complexity. Here, we investigate a new approach to exploit the ℋ-matrix structure for the solution of large scale Lyapunov and Riccati equations as they typically arise for optimal control problems where the constraint is a partial differential equation of elliptic type. This approach leads to an algorithm of linear-logarithmic complexity in the size of the matrices. Received July 30, 2002; revised December 16, 2002 Published online: April 22, 2003     

Robust Multigrid Methods for Nearly Incompressible Elasticity

We consider multigrid methods for problems in linear elasticity which are robust with respect to the Poisson ratio. Therefore, we consider mixed approximations involving the displacement vector and the pressure, where the pressure is approximated by discontinuous functions. Then, the pressure can be eliminated by static condensation. The method is based on a saddle point smoother which was introduced for the Stokes problem and which is transferred to the elasticity system. The performance and the robustness of the multigrid method are demonstrated on several examples with different discretizations in 2D and 3D. Furthermore, we compare the multigrid method for the saddle point formulation and for the condensed positive definite system. Received February 5, 1999; revised October 5, 1999     

Sufficient Conditions for Uniform Convergence on Layer-Adapted Grids

We study convergence properties of the simple upwind difference scheme and a Galerkin finite element method on generalized Shishkin grids. We derive conditions on the mesh-characterizing function that are sufficient for the convergence of the method, uniformly with respect to the perturbation parameter. These conditions are easy to check and enable one to immediately deduce the rate of convergence. Numerical experiments support these theoretical results and indicate that the estimates are sharp. The analysis is set in one dimension, but can be easily generalized to tensor product meshes in 2D. Received: December 21, 1998; revised March 17, 1999     

A Higher-Order Scheme for Quasilinear Boundary Value Problems with Two Small Parameters

Received September 28, 2000; revised February 13, 2001     

Extension of the Thomas Algorithm to a Class of Algebraic Linear Equation Systems Involving Quasi-Block-Tridiagonal Matrices with Isolated Block-Pentadiagonal Rows, Assuming Variable Block Dimensions

Received July 17, 2000; revised January 31, 2001     

Analysis of Some Elementary Algorithms for Prime Factorization

For factoring a positive integer n into primes, four variants of the elementary algorithm are analysed. The worst-case time complexities vary from Θ() up to Θ(). The average time complexities vary from Θ() up to Θ(). Received August 21, 1998; revised September 14, 2000