Local error estimation for singly-implicit formulas by two-step Runge-Kutta methods

In this paper it is shown that the local discretization error ofs-stage singly-implicit methods of orderp can be estimated by embedding these methods intos-stage two-step Runge-Kutta methods of orderp+1, wherep=s orp=s+1. These error estimates do not require any extra evaluations of the right hand side of the differential equations. This is in contrast with the error estimation schemes based on embedded pairs of two singly-implicit methods proposed by Burrage.The work of A. Bellen and M. Zennaro was supported by the CNR and MPI. The work of Z. Jackiewicz was supported by the CNR and by the NSF under grant DMS-8520900.     

Characterization of seminuclear sets in a finite projective plane

LetC be a set ofq + a points in the desarguesian projective plane of orderq, such that each point ofC is on exactly 1 tangent, and onea+ 1-secant (a>1). Then eitherq=a + 2 andC consists of the symmetric difference of two lines, with one further point removed from each line, orq=2a + 3 andC is projectively equivalent to the set of points {(0,1,s),(s, 0, 1),(1,s, 0): -s is not a square inGF(q)}.     

On factorizing meromorphic functions

Summary The paper determines all cases when a meromorphic functionF can be expressed both asf ⊗p andf ⊗q with the same meromorphicf and different polynomialsp andq. In all cases there are constantsk, β, a positive integerm, a root λ of unity of orderS and a polynomialr such thatp=(Lr) ^m+k,q=r ^m+k, whereLz=λz+β. We have eitherm=1,S arbitrary orm=2,S=2, which can occur even ifF andf are entire, or, in the remaining casesS=2, 3, 4 or 6,m dividesS andf(k+t ^m) is a doubly-periodic function.     

A stability result for general linear methods with characteristic function having real poles only

It is shown that there exist A-stable multistep formulae, with a characteristic function havings poles, all of which are real, with orderp satisfyingp>s+1. This contradicts the widely held belief thatp=s+1 is the maximum possible order of such a method.     

A class of pseudo Runge-Kutta methods

This paper develops a general theory for a class of Runge-Kutta methods which are based, in addition to the stages of the current step, also on the stages of the previous step. Such methods have been introduced previously for the case of one and two stages. We show that for any numbers of stages methods of orderp withs+1 p 2s can be constructed. The paper terminates with a study of step size change and stability.     

A note on pseudo-symplectic Runge-Kutta methods

Aubry and Chartier introduced (1998) the concept of pseudo-symplecticness in order to construct explicit Runge-Kutta methods, which mimic symplectic ones. Of particular interest are methods of order (p, 2p), i.e., of orderp and pseudo-symplecticness order 2p, for which the growth of the global error remains linear. The aim of this note is to show that the lower bound for the minimal number of stages can be achieved forp=4 andp=5.     

A bound on the maximum strong order of stochastic Runge-Kutta methods for stochastic ordinary differential equations

In Burrage and Burrage [1] it was shown that by introducing a very general formulation for stochastic Runge-Kutta methods, the previous strong order barrier of order one could be broken without having to use higher derivative terms. In particular, methods of strong order 1.5 were developed in which a Stratonovich integral of order one and one of order two were present in the formulation. In this present paper, general order results are proven about the maximum attainable strong order of these stochastic Runge-Kutta methods (SRKs) in terms of the order of the Stratonovich integrals appearing in the Runge-Kutta formulation. In particular, it will be shown that if ans-stage SRK contains Stratonovich integrals up to orderp then the strong order of the SRK cannot exceed min{(p+1)/2, (s−1)/2},p≥2,s≥3 or 1 ifp=1.     

The line analog of Ramsey numbers

For positive integersr ands, f′(r, s) is defined as the smallest positive integerp such that every connected (ordinary) graph of orderp contains eitherr mutually adjacent lines ors mutually disjoint lines. It is found thatf’(r,s) =(r−1) (s−1)+2 unlessr=2 and s ≠ 1, in which casef′(2,s)=3. Definitions not given here can be found in [7, 8].     

Stability and accuracy for implicit semidiscretizations of hyperbolic problems

Summary In this paper we give bounds for the error constants of certain classes of stable implicit finite difference methods for first order hyperbolic equations in one space dimension. We consider classes of methods that user downwind ands upwind points in the explicit part andR downwind andS upwind points in the implicit part, respectively, and that are of optimal orderp=min (r+R+s+S, 2(r+R+1), 2(s+S)).In some cases the error constant of interpolatory methods [5] can be improved. The results are proved via the order star technique. They are further used to determine methods of optimal order that are stable.     

A-stable diagonally implicit Runge-Kutta-Nyström methods for parallel computers

In this paper, we study diagonally implicit Runge-Kutta-Nyström methods (DIRKN methods) for use on parallel computers. These methods are obtained by diagonally implicit iteration of fully implicit Runge-Kutta-Nyström methods (corrector methods). The number of iterations is chosen such that the method has the same order of accuracy as the corrector, and the iteration parameters serve to make the method at least A-stable. Since a large number of the stages can be computed in parallel, the methods are very efficient on parallel computers. We derive a number of A-stable, strongly A-stable and L-stable DIRKN methods of orderp withs ^* (p) sequential, singly diagonal-implicit stages wheres ^*(p)=[(p+1)/2] ors ^* (p)=[(p+1)/2]+1,[°] denoting the integer part function.These investigations were supported by the University of Amsterdam with a research grant to enable the author to spend a total of two years in Amsterdam.     

On implicit Runge-Kutta methods with a stability function having distinct real poles

Because of their potential for offering a computational speed-up when used on certain multiprocessor computers, implicit Runge-Kutta methods with a stability function having distinct poles are analyzed. These are calledmultiply implicit (MIRK) methods, and because of the so-calledorder reduction phenomenon, their poles are required to be real, i.e., only real MIRK's are considered. Specifically, it is proved that a necessary condition for aq-stage, real MIRK to beA-stable with maximal orderq+1 is thatq=1, 2, 3 or 5. Nevertheless, it is shown that for every positive integerq, there exists aq-stage, real MIRK which is stronglyA ₀-stable with orderq+1, and for every evenq, there is aq-stage, real MIRK which isI-stable with orderq. Finally, some useful examples of algebraically stable real MIRK's are given.This work was supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-18107 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23665-5225.     

On the number of lines in planar spaces

SupposeS is a planar space withv>4 points and letq be the positive real number such thatv=q ³+q²+q+1. Assuming a weak non-degeneracy condition, we shall show thatS has at least (q²+1)(q²+q+1) lines with equality iffq is a prime power andS=PG(3,q).     

On implicit Runge-Kutta methods with high stage order

It is well known that high stage order is a desirable property for implicit Runge-Kutta methods. In this paper it is shown that it is always possible to construct ans-stage IRK method with a given stability function and stage orders−1 if the stability function is an approximation to the exponential function of at least orders. It is further indicated how to construct such methods as well as in which cases the constructed methods will be stiffly accurate.     

Average CaseL∞-Approximation in the Presence of Gaussian Noise

We consider the average caseL_∞-approximation of functions fromC^r([0, 1]) with respect to ther-fold Wiener measure. An approximation is based onnfunction evaluations in the presence of Gaussian noise with varianceσ²>0. We show that the n th minimal average error is of ordern^{−(2r+1)/(4r+4)} ln^1/2 n, and that it can be attained either by the piecewise polynomial approximation using repetitive observations, or by the smoothing spline approximation using non-repetitive observations. This completes the already known results forL_q-approximation withq<∞ andσ0, and forL_∞-approximation withσ=0.     

Some permutation groups of degreep=6q+1

Transitive permutation groups of degrees 43, 67, 79, 103 and 139 are classified.In this note we consider insoluble transitive permutation groups of degreeq = 6q+1 wherep andq are primes and summarise the computations whereby these groups have been classified for some small values ofq. The result which allows progress on this problem is due to McDonough [1]; he showed that if such a group has a Sylowp-normaliser of order 3p then it is isomorphic either toPSL(3, 3) orPAL(3, 5) (of degrees 13, 31 respectively). Using this theorem machine computations along the lines of those done by Parker, Nikolai and Appel [3, 2] for degreesp=2q+1 andp=4q+1 give the following     

An inverse eigenvalue problem: ComputingB-stable Runge-Kutta methods having real poles

The implementation of implicit Runge-Kutta methods requires the solution of large sets of nonlinear equations. It is known that on serial machines these costs can be reduced if the stability function of ans-stage method has only ans-fold real pole. Here these so-called singly-implicit Runge-Kutta methods (SIRKs) are constructed utilizing a recent result on eigenvalue assignment by state feedback and a new tridiagonalization, which preserves the entries required by theW-transformation. These two algorithms in conjunction with an unconstrained minimization allow the numerical treatment of a difficult inverse eigenvalue problem. In particular we compute an 8-stage SIRK which is of order 8 andB-stable. This solves a problem posed by Hairer and Wanner a decade ago. Furthermore, we finds-stageB-stable SIRKs (s=6,8) of orders, which are evenL-stable.     

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.     

Edge sets contained in circuits

A graphG withn vertices has propertyp(r, s) ifG contains a path of lengthr and if every such path is contained in a circuit of lengths. G. A. Dirac and C. Thomassen [Math. Ann.203 (1973), 65–75] determined graphs with propertyp(r,r+1). We determine the least number of edges in a graphG in order to insure thatG has propertyp(r,s), we determine the least number of edges possible in a connected graph with propertyp(r,s) forr=1 and alls, forr=k ands=k+2 whenk=2, 3, 4, and we give bounds in other cases. Some resulting extremal graphs are determined. We also consider a generalization of propertyp(2,s) in which it is required that each pair of edges is contained in a circuit of lengths. Some cases of this last property have been treated previously by U. S. R. Murty [inProof Techniques in Graph Theory, ed. F. Harary, Academic Press, New York, 1969, pp. 111–118].     

Superconvergent explicit two-step peer methods

We consider explicit two-step peer methods for the solution of nonstiff differential systems. By an additional condition a subclass of optimally zero-stable methods is identified that is superconvergent of order p=s+1$p=s+1$, where s$s$ is the number of stages. The new condition allows us to reduce the number of coefficients in a numerical search for good methods. We present methods with 4–7 stages which are tested in FORTRAN90 and compared with DOPRI5 and DOP853. The results confirm the high potential of the new class of methods.     

Galois groups ofp-extensions with two ramification points

LetK _p (p, q) be the maximalp-extension of the field ℚ of rational numbers with ramification pointsp andq. LetG _p (p, q) be the Galois group of the extensionK _p(p.q)/ℚ. It is known thatG _p(p, q) can be presented by two generators which satisfy a single relation. The form of this relation is known only modulo the second member of the descending central series ofG _p(p, q). In this paper, we find an arithmetical-type condition on which the form of the relation modulo the third member of the descending central series ofG _p(p, q) depends. We also consider two examples withp=3,q=19 andp=3,q=37. Translated from Lietuvos Matematikos Rinkinys, Vol. 40, No. 1, pp. 48–60, January–March, 2000. Translated by H. Markšaitis