Efficient orthogonal spline collocation methods for solving linear second order hyperbolic problems on rectangles

Summary. Piecewise Hermite bicubic orthogonal spline collocation Laplace-modified and alternating-direction schemes for the approximate solution of linear second order hyperbolic problems on rectangles are analyzed. The schemes are shown to be unconditionally stable and of optimal order accuracy in the and discrete maximum norms for space and time, respectively. Implementations of the schemes are discussed and numerical results presented which demonstrate the accuracy and rate of convergence using various norms. Received November 7, 1994 / Revised version received April 29, 1996     

A postprocessed Galerkin method with Chebyshev or Legendre polynomials

Summary. We present an approximate-inertial-manifold-based postprocess to enhance Chebyshev or Legendre spectral Galerkin methods. We prove that the postprocess improves the order of convergence of the Galerkin solution, yielding the same accuracy as the nonlinear Galerkin method. Numerical experiments show that the new method is computationally more efficient than Galerkin and nonlinear Galerkin methods. New approximation results for Chebyshev polynomials are presented. Received January 5, 1998 / Revised version received September 7, 1999 / Published online June 8, 2000     

The NGP-stability of Runge-Kutta methods for systems of neutral delay differential equations

Summary. This paper deals with the stability analysis of implicit Runge-Kutta methods for the numerical solutions of the systems of neutral delay differential equations. We focus on the behavior of such methods with respect to the linear test equations where ,L, M and N are complex matrices. We show that an implicit Runge-Kutta method is NGP-stable if and only if it is A-stable. Received February 10, 1997 / Revised version received January 5, 1998     

On the asymptotic stability properties of Runge-Kutta methods for delay differential equations

Summary. In this paper asymptotic stability properties of Runge-Kutta (R-K) methods for delay differential equations (DDEs) are considered with respect to the following test equation: where and is a continuous real-valued function. In the last few years, stability properties of R-K methods applied to DDEs have been studied by numerous authors who have considered regions of asymptotic stability for “any positive delay” (and thus independent of the specific value of ). In this work we direct attention at the dependence of stability regions on a fixed delay . In particular, natural Runge-Kutta methods for DDEs are extensively examined. Received April 15, 1996 / Revised version received August 8, 1996     

Integration methods based on canonical coordinates of the second kind

Summary.   We present a new class of integration methods for differential equations on manifolds, in the framework of Lie group actions. Canonical coordinates of the second kind is used for representing the Lie group locally by means of its corresponding Lie algebra. The coordinate map itself can, in many cases, be computed inexpensively, but the approach also involves the inversion of its differential, a task that can be challenging. To succeed, it is necessary to consider carefully how to choose a basis for the Lie algebra, and the ordering of the basis is important as well. For semisimple Lie algebras, one may take advantage of the root space decomposition to provide a basis with desirable properties. The problem of ordering leads us to introduce the concept of an admissible ordered basis (AOB). The existence of an AOB is established for some of the most important Lie algebras. The computational cost analysis shows that the approach may lead to more efficient solvers for ODEs on manifolds than those based on canonical coordinates of the first kind presented by Munthe-Kaas. Numerical experiments verify the derived properties of the new methods. Received April 2, 1999 / Revised version received January 18, 2000 / Published online August 2, 2000     

Galerkin proper orthogonal decomposition methods for parabolic problems

Summary. In this work error estimates for Galerkin proper orthogonal decomposition (POD) methods for linear and certain non-linear parabolic systems are proved. The resulting error bounds depend on the number of POD basis functions and on the time discretization. Numerical examples are included. Received September 29, 1999 / Revised version received August 21, 2000 / Published online May 4, 2001     

Runge-Kutta methods without order reduction for linear initial boundary value problems

Summary. It is well-known the loss of accuracy when a Runge–Kutta method is used together with the method of lines for the full discretization of an initial boundary value problem. We show that this phenomenon, called order reduction, is caused by wrong boundary values in intermediate stages. With a right choice, the order reduction can be avoided and the optimal order of convergence in time is achieved. We prove this fact for time discretizations of abstract initial boundary value problems based on implicit Runge–Kutta methods. Moreover, we apply these results to the full discretization of parabolic problems by means of Galerkin finite element techniques. We present some numerical examples in order to confirm that the optimal order is actually achieved. Received July 10, 2000 / Revised version received March 13, 2001 / Published online October 17, 2001     

On higher-order semi-explicit symplectic partitioned Runge-Kutta methods for constrained Hamiltonian systems

Summary. In this paper we generalize the class of explicit partitioned Runge-Kutta (PRK) methods for separable Hamiltonian systems to systems with holonomic constraints. For a convenient analysis of such schemes, we first generalize the backward error analysis for systems in to systems on manifolds embedded in . By applying this analysis to constrained PRK methods, we prove that such methods will, in general, suffer from order reduction as well-known for higher-index differential-algebraic equations. However, this order reduction can be avoided by a proper modification of the standard PRK methods. This modification increases the number of projection steps onto the constraint manifold but leaves the number of force evaluations constant. We also give a numerical comparison of several second, fourth, and sixth order methods. Received May 5, 1995 / Revised version received February 7, 1996     

Computing orthogonal polynomials in Sobolev spaces

Summary. Numerical methods are considered for generating polynomials orthogonal with respect to an inner product of Sobolev type, i.e., one that involves derivatives up to some given order, each having its own (positive) measure associated with it. The principal objective is to compute the coefficients in the increasing-order recurrence relation that these polynomials satisfy by virtue of them forming a sequence of monic polynomials with degrees increasing by 1 from one member to the next. As a by-product of this computation, one gains access to the zeros of these polynomials via eigenvalues of an upper Hessenberg matrix formed by the coefficients generated. Two methods are developed: One is based on the modified moments of the constitutive measures and generalizes what for ordinary orthogonal polynomials is known as "modified Chebyshev algorithm". The other - a generalization of "Stieltjes's procedure" - expresses the desired coefficients in terms of a Sobolev inner product involving the orthogonal polynomials in question, whereby the inner product is evaluated by numerical quadrature and the polynomials involved are computed by means of the recurrence relation already generated up to that point. The numerical characteristics of these methods are illustrated in the case of Sobolev orthogonal polynomials of old as well as new types. Based on extensive numerical experimentation, a number of conjectures are formulated with regard to the location and interlacing properties of the respective zeros. Received July 13, 1994 / Revised version received September 26, 1994     

Stability of the Radau IA and Lobatto IIIC methods for delay differential equations

Recently, we have proved that the Radau IA and Lobatto IIIC methods are P-stable, i.e., they have an analogous stability property to A-stability with respect to scalar delay differential equations (DDEs). In this paper, we study stability of those methods applied to multidimensional DDEs. We show that they have a similar property to P-stability with respect to multidimensional equations which satisfy certain conditions for asymptotic stability of the zero solutions. The conditions are closely related to stability criteria for DDEs considered in systems theory. Received October 8, 1996 / Revised version received February 21, 1997     

Spline qualocation methods for variable-coefficient elliptic equations on curves

Summary. Here the stability and convergence results of oqualocation methods providing additional orders of convergence are extended from the special class of pseudodifferential equations with constant coefficient symbols to general classical pseudodifferential equations of strongly and of oddly elliptic type. The analysis exploits localization in the form of frozen coefficients, pseudohomogeneous asymptotic symbol representation of classical pseudodifferential operators, a decisive commutator property of the qualocation projection and requires qualocation rules which provide sufficiently many additional degrees of precision for the numerical integration of smooth remainders. Numerical examples show the predicted high orders of convergence. Received January 29, 1998 / Published online: June 29, 1999     

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     

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     

Multigrid methods with web-splines

Summary. We describe and analyze a multigrid algorithm for finite element approximations of second order elliptic boundary value problems with weightedextended b-splines (web-splines). This new technique provides high accuracy with relatively low-dimensional subspaces, does not require any grid generation, and is ideally suited for hierarchical solution techniques. In particular, we show that the standard W-cycle yields uniform convergence, i.e., the required number of iterations is bounded independent of the grid width. Received August 17, 2000 / Published online August 17, 2001     

Qualocation methods for elliptic boundary integral equations

Summary. The qualocation methods developed in this paper, with spline trial and test spaces, are suitable for classes of boundary integral equations with convolutional principal part, on smooth closed curves in the plane. Some of the methods are suitable for all strongly elliptic equations; that is, for equations in which the even symbol part of the operator dominates. Other methods are suitable when the odd part dominates. Received December 27, 1996 / Revised version received April 14, 1997     

Nonconforming finite element methods without numerical locking

We analyze the numerical approximation of a class of elliptic problems which depend on a small parameter . We give a generalization to the nonconforming case of a recent result established by Chenais and Paumier for a conforming discretization. For both the situations where numerical integration is used or not, a uniform convergence in and h is proved, numerical locking being thus avoided. Important tools in the proof of such a result are compactness properties for nonconforming spaces as well as the passage to the limit problem. Received October 7, 1997     

Extrapolation methods in Lie groups

Summary. The numerical solution of differential equations on Lie groups by extrapolation methods is investigated. The main principles of extrapolation for ordinary differential equations are extended on the general case of differential equations in noncommutative Lie groups. An asymptotic expansion of the global error is given. A symmetric method is given and quadratic asymptotic expansion of the global error is proved. The theoretical results are verified by numerical experiments. Received September 27, 1999 / Revised version received February 14, 2000 / Published online April 5, 2001     

Numerical solution by LMMs of stiff delay differential systems modelling an immune response

Summary. We consider the application of linear multistep methods (LMMs) for the numerical solution of initial value problem for stiff delay differential equations (DDEs) with several constant delays, which are used in mathematical modelling of immune response. For the approximation of delayed variables the Nordsieck's interpolation technique, providing an interpolation procedure consistent with the underlying linear multistep formula, is used. An analysis of the convergence for a variable-stepsize and structure of the asymptotic expansion of global error for a fixed-stepsize is presented. Some absolute stability characteristics of the method are examined. Implementation details of the code DIFSUB-DDE, being a modification of the Gear's DIFSUB, are given. Finally, an efficiency of the code developed for solution of stiff DDEs over a wide range of tolerances is illustrated on biomedical application model. Received March 23, 1994 / Revised version received March 13, 1995     

Stabilization of DAEs and invariant manifolds

Summary. Many methods have been proposed for the stabilization of higher index differential-algebraic equations (DAEs). Such methods often involve constraint differentiation and problem stabilization, thus obtaining a stabilized index reduction. A popular method is Baumgarte stabilization, but the choice of parameters to make it robust is unclear in practice. Here we explain why the Baumgarte method may run into trouble. We then show how to improve it. We further develop a unifying theory for stabilization methods which includes many of the various techniques proposed in the literature. Our approach is to (i) consider stabilization of ODEs with invariants, (ii) discretize the stabilizing term in a simple way, generally different from the ODE discretization, and (iii) use orthogonal projections whenever possible. The best methods thus obtained are related to methods of coordinate projection. We discuss them and make concrete algorithmic suggestions. Received September 1992/Revised version received May 13, 1993     

The index of general nonlinear DAEs

Summary. In the last few years there has been considerable research on differential algebraic equations (DAEs) where is identically singular. Much of the mathematical effort has focused on computing a solution that is assumed to exist. More recently there has been some discussion of solvability of DAEs. There has historically been some imprecision in the use of the two key concepts of solvability and index for DAEs. The index is also important in control and systems theory but with different terminology. The consideration of increasingly complex nonlinear DAEs makes a clear and correct development necessary. This paper will try to clarify several points concerning the index. After establishing some new and more precise terminology that we need, some inaccuracies in the literature will be corrected. The two types of indices most frequently used, the differentiation index and the perturbation index, are defined with respect to solutions of unperturbed problems. Examples are given to show that these indices can be very different for the same problem. We define new "maximum indices," which are the maxima of earlier indices in a neighborhood of the solution over a set of perturbations and show that these indices are simply related to each other. These indices are also related to an index defined in terms of Jacobians. Received November 15, 1993 / Revised version received December 23, 1994