Explicit General Linear Methods with Inherent Runge–Kutta Stability

A class of general linear methods is derived for application to non-stiff ordinary differential equations. A property known as inherent Runge–Kutta stability guarantees the stability regions of these methods are the same as for Runge–Kutta methods. Methods with this property have high stage order which enables asymptotically correct error estimates and high order interpolants to be computed conveniently. Some preliminary numerical experiments are given comparing these methods with some well known Runge–Kutta methods.     

L r Estimates for Degenerate Elliptic Problems

We prove L ^r estimates for the Dirichlet problem –div(a(x,u,Du))=f with f in L ^q for 1q+, where the operator satisfies (|s|)|| ^p a(x,s,), with p>1. These estimates are obtained without symmetrization and are sharp in some cases.     

The Parameters of Bipartite Q-polynomial Distance-Regular Graphs

Let denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Suppose ₀, ₁, ..., _D is a Q-polynomial ordering of the eigenvalues of . This sequence is known to satisfy the recurrence _{i – 1} – _i + _{i + 1} = 0 (0 > i > D), for some real scalar . Let q denote a complex scalar such that q + q ^–1 = . Bannai and Ito have conjectured that q is real if the diameter D is sufficiently large.We settle this conjecture in the bipartite case by showing that q is real if the diameter D 4. Moreover, if D = 3, then q is not real if and only if ₁ is the second largest eigenvalue and the pair (, k) is one of the following: (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), or (2, 5). We observe that each of these pairs has a unique realization by a known bipartite distance-regular graph of diameter 3.     

Eulerian numbers with fractional order parameters

Summary The aim of this paper is to generalize the well-known Eulerian numbers, defined by the recursion relationE(n, k) = (k + 1)E(n – 1, k) + (n – k)E(n – 1, k – 1), to the case thatn is replaced by . It is shown that these Eulerian functionsE(, k), which can also be defined in terms of a generating function, can be represented as a certain sum, as a determinant, or as a fractional Weyl integral. TheE(, k) satisfy recursion formulae, they are monotone ink and, as functions of , are arbitrarily often differentiable. Further, connections with the fractional Stirling numbers of second kind, theS(, k), > 0, introduced by the authors (1989), are discussed. Finally, a certain counterpart of the famous Worpitzky formula is given; it is essentially an approximation ofx in terms of a sum involving theE(, k) and a hypergeometric function.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

Approximation by Reciprocals of Polynomials with Positive Coefficients in L p Spaces

We prove that, if f(x) L ^p _[0,1], 1 < p < , f(x) 0, x [0,1], f 0, then there is a polynomial p(x) ⁺ _n such that f - 1/p _LP C(p)(f,n ^-1/2) _LP where ⁺ _n indicates the set of all polynomials of degree n with positive coeficients (see the definition (1) in the text).     

Slope Estimates of Artin–Schreier Curves

Let X/F_p be an Artin–Schreier curve defined by the affine equation y ^p –y=f(x) where f(x)F_p[x] is monic of degree d. In this paper we develop a method for estimating the first slope of the Newton polygon of X. Denote this first slope by NP₁(X/F_p). We use our method to prove that if p>d2 then NP₁(X/F_p)(p–1)/d/(p–1). If p>2d4, we give a sufficient condition for the equality to hold.     

Some best possible bounds concerning the traces of finite sets II

LetX be ann-element set and be a family of its subsets. Consider the family _x = {F – {x} : F } for a givenx X. We write(m, n) (m – k, n – 1), when for all with || m, there exists an elementx ofX such that| _x| m – k. We show that (m, n) (m – 10,n – 1) for allm 5n and (m, n) (m – 13,n – 1) for allm 29n/5.     

Equivalence Bimodule Between Non-Commutative Tori

The non-commutative torus C ^*(ⁿ,) is realized as the C*-algebra of sections of a locally trivial C*-algebra bundle over S with fibres isomorphic to C ^*n/S, ₁) for a totally skew multiplier ₁ on ⁿ/S. D. Poguntke [9] proved that A is stably isomorphic to C(S) C(^*( Zⁿ/S, ₁) C(S) A M_kl( C) for a simple non-commutative torus A and an integer kl. It is well-known that a stable isomorphism of two separable C*-algebras is equivalent to the existence of equivalence bimodule between them. We construct an A-C(S) A-equivalence bimodule.     

The Remaining Service Time upon Reaching a High Level in M/G/1 Queues

The distribution of the remaining service time upon reaching some target level in an M/G/1 queue is of theoretical as well as practical interest. In general, this distribution depends on the initial level as well as on the target level, say, B. Two initial levels are of particular interest, namely, level 1 (i.e., upon arrival to an empty system) and level B–1 (i.e., upon departure at the target level).In this paper, we consider a busy cycle and show that the remaining service time distribution, upon reaching a high level B due to an arrival, converges to a limiting distribution for B. We determine this asymptotic distribution upon the first hit (i.e., starting with an arrival to an empty system) and upon subsequent hits (i.e., starting with a departure at the target) into a high target level B. The form of the limiting (asymptotic) distribution of the remaining service time depends on whether the system is stable or not. The asymptotic analysis in this paper also enables us to obtain good analytical approximations of interesting quantities associated with rare events, such as overflow probabilities.     

On the Projections of Multivalued Maps

This paper considers analogues of the Helmholtz projections of the set of selections of a piecewise smooth multivalued map , n2. It is shown that, for mn–1 (m=1), the closure of the projection of on the subspace of gradient fields (solenoidal vector fields) is a convex set. For the general case, there are given point-wise conditions on the values of the map which ensure that the closure of the projection of contains the zero element. Possible applications to optimal control problems are discussed.     

The Construction of Practical General Linear Methods

Using the property of inherent Runge—Kutta stability, it is possible to construct diagonally implicit general linear methods with stability regions exactly the same as for Runge—Kutta methods. In addition to A-stable methods found in this way, it is also possible to construct explicit methods with stability regions identical to those of explicit Runge—Kutta methods. The use of doubly companion matrices makes it possible to find all explicit and diagonally-implicit methods possessing the inherent Runge—Kutta stability property.This revised version was published online in October 2005 with corrections to the Cover Date.     

A r (Ω)-Weighted Imbedding Inequalities for A-Harmonic Tensors

We prove the basic A _r ()-weighted imbedding inequalities for A-harmonic tensors. These results can be used to estimate the integrals for A-harmonic tensors and to study the integrability of A-harmonic tensors and the properties of the homotopy operator T: C (D, ^l )C (D, ^l–1).     

Implications of order reduction for implicit Runge-Kutta methods

Stability analysis of Runge-Kutta (RK) formulas was originally limited to linear ordinary differential equations (ODEs). More recently such analysis has been extended to include the behaviour of solutions to nonlinear problems. This extension led to additional stability requirements for RK methods. Although the class of problems has been widened, the analysis is still restricted to a fixed stepsize. In the case of differential algebraic equations (DAEs), additional order conditions must be satisfied [6] to achieve full classical ODE order and avoid possible order reduction. In this case too, a fixed stepsize analysis is employed. Such analysis may be of only limited use in quantifying the effectiveness of adaptive methods on stiff problems.In this paper we examine the phenomenon of order reduction and its implications on variable-step algorithms. We introduce a global measure of order referred to here as the observed order which is based on the average stepsize over the region of integration. This measure may be better suited to the study of stiff systems, where the stepsize selection algorithm will vary the stepsize considerably over the interval of integration. Observed order gives a better indication of the relationship between accuracy and cost. Using this measure, the observed order reduction will be seen to be less severe than that predicated by fixed stepsize order analysis.Supported by the Information Technology Research Centre of Ontario, and the Natural Science and Engineering Research Council of Canada.     

Mathematical expectations of functions of sums of a random number of independent terms

Conditions are found which must be imposed on a function g(x) in order that M g(₁+₂+ + _v < if M g(_i) < and M g(v) < ,, ₁, ₂, , _n, ... being non-negative and independent, being integral, and {_i} being identically distributed. The result is applied to the theory of branching processes.Translated from Matematicheskie Zametki, Vol. 3, No. 4, pp. 387–394, April, 1968.     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

Estimation of density functions by order statistics

The properties of the empirical density function,f _n(x) = k/n( _j ⁺ – _j-1 ⁺ ) if _j-1 ⁺ < x ⁺ where _j-1 ⁺ and _j ⁺ are sample elements and there are exactlyk – 1 sample elements between them, are studied in that practical point of view how to choose a suitablek for a good estimation. A bound is given for the expected value of the absolute value of difference between the empirical and theoretical density functions.     

Two-phases Method and Branch and Bound Procedures to Solve the Bi–objective Knapsack Problem

The classical 0–1 knapsack problem is considered with two objectives. Two methods of the two–phases type are developed to generate the set of efficient solutions. In the first phase, the set of supported efficient solutions is determined by optimizing a parameterized single-objective knapsack problem. Two versions are proposed for a second phase, determining the non-supported efficient solutions: both versions are Branch and Bound approaches, but one is breadth first, while the other is depth first. Extensive numerical experiments have been realized to compare the results of both methods.     

On a characterization of polynomials by divided differences

Summary We consider the functional equationf[x ₁,x ₂,, x _n ] =h(x ₁ + +x _n ) (x ₁,,x _n K, x _j x _k forj k), (D) wheref[x ₁,x ₂,,x _n ] denotes the (n – 1)-st divided difference off and prove Theorem. Let n be an integer, n 2, let K be a field, char(K) 2, with # K 8(n – 2) + 2. Let, furthermore, f, h: K K be functions. Then we have that f, h fulfil (D) if, and only if, there are constants a_j K, 0 j n (a := a_n, b := a_{n – 1}) such thatf = ax ⁿ +bx ^{n – 1} + +a ₀ and h = ax + b.     

Some Asymptotic Results for the M/M/∞ Queue with Ranked Servers

We consider an M/M/ model with m primary servers and infinitely many secondary ones. An arriving customer takes a primary server, if one is available. We derive integral representations for the joint steady state distribution of the number of occupied primary and secondary servers. Letting =/ be the ratio of arrival and service rates (all servers work at rate ), we study the joint distribution asymptotically for . We consider both m=O(1) and m scaled to be of the same order as . We also give results for the marginal distribution of the number of secondary servers that are occupied.     

On the Rubin–Stark Conjecture for a special class of CM extensions of totally real number fields

We use Greithers recent results on Brumers Conjecture to prove Rubins integral version of Starks Conjecture, up to a power of 2, for an infinite class of CM extensions of totally real number fields, called nice extensions under the assumption that a certain Iwasawa –invariant vanishes. As a consequence and under the same assumption, we show that the Brumer–Stark Conjecture is true for nice extensions, up to a power of 2.Mathematical Subject Classification (1991): 11R42, 11R58, 11R27Research on this project was partially supported by NSF grants DMS–9801267 and DMS–0196340.in final form: 16 July 2003