Limits of parallelism in explicit ODE methods

Numerical methods for ordinary initial value problems that do not depend on special properties of the system are usually found in the class of linear multistage multivalue methods, first formulated by J.C. Butcher. Among these the explicit methods are easiest to implement. For these reasons there has been considerable research activity devoted to generating methods of this class which utilize independent function evaluations that can be performed in parallel. Each such group of concurrent function evaluations can be regarded as a stage of the method. However, it turns out that parallelism affords only limited opportunity for reducing the computing time with such methods. This is most evident for the simple linear homogeneous constant-coefficient test problem, whose solution is essentially a matter of approximating the exponential by an algebraic function. For a given number of stages and a given number of saved values, parallelism offers a somewhat enlarged set of algebraic functions from which to choose. However, there is absolutely no benefit in having the degree of parallelism (number of processors) exceed the number of saved values of the method. Thus, in particular, parallel one-step methods offer no speedup over serial one-step methods for the standard linear test problem. Although the implication of this result for general nonlinear problems is unclear, there are indications that dramatic speedups are not possible in general. Also given are some results relevant to the construction of methods.Work supported in part by National Science Foundation grants DMS 89 11410 and DMS 90 15533 and by US Department of Energy grant DOE DEFG02-87ER25026. Work of the second author was completed while at the University of Illinois.     

Asymptotic Behavior of Sobolev-Type Orthogonal Polynomials on a Rectifiable Jordan Curve or Arc

Our object of study is the asymptotic behavior of the sequence of polynomials orthogonal with respect to the discrete Sobolev inner product <formula> \langle f, g \rangle = ∈t_{E} f(ξ) \overline{g(ξ)} ρ(ξ) |d ξ|+ f(Z) A g(Z)^H, </formula> where E is a rectifiable Jordan curve or arc in the complex plane f(Z) = (f(z_1), \ldots, f^{(l_1)}(z_1) , \ldots , f(z_m) , \ldots ,f^{(l_m)}(z_m)), A is an M \times M Hermitian matrix, M l ₁ + ⋅s + l _m + m , |d ξ| denotes the arc length measure, ρ is a nonnegative function on E , and z _i ∈Ω, i=1,2,\ldots,m , where Ω is the exterior region to E . July 23, 1999. Dates revised: September 11, 2000 and February 16, 2001. Date accepted: February 26, 2001.     

Multiderivations of Coxeter arrangements

Let V be an ℓ-dimensional Euclidean space. Let G⊂O(V) be a finite irreducible orthogonal reflection group. Let ? be the corresponding Coxeter arrangement. Let S be the algebra of polynomial functions on V. For H∈? choose α _H ∈V ^* such that H=ker(α _H ). For each nonnegative integer m, define the derivation module D ^(m) (?)={θ∈Der _S |θ(α _H )∈Sα ^m _H }. The module is known to be a free S-module of rank ℓ by K. Saito (1975) for m=1 and L. Solomon-H. Terao (1998) for m=2. The main result of this paper is that this is the case for all m. Moreover we explicitly construct a basis for D ^(m) (?). Their degrees are all equal to mh/2 (when m is even) or are equal to ((m−1)h/2)+m _i (1≤i≤ℓ) (when m is odd). Here m ₁≤···≤m _ℓ are the exponents of G and h=m _ℓ+1 is the Coxeter number. The construction heavily uses the primitive derivation D which plays a central role in the theory of flat generators by K. Saito (or equivalently the Frobenius manifold structure for the orbit space of G). Some new results concerning the primitive derivation D are obtained in the course of proof of the main result. Oblatum 27-XI-2001 & 4-XII-2001?Published online: 18 February 2002     

Characterization of supercommuting matrices

For a given n-by-n matrix A, we consider the set of matrices which commute with A and all of whose principal submatrices commute with the corresponding principal submatrices of A. The properties of this set are examined, with particular attention to its dimension.     

Algebraic models defined over Q of differential manifolds

Here we prove that every compact differential manifold has a smooth algebraic model defined over Q. In dimension 2 we find an algebraic model (may be singular) defined over Q and birational over Q to the projective plane.     

Deciding Frattini is NP-complete

We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.This work was supported in part by Swiss NSF grant 20-32644.91.     

Polynomial decay rate for the dissipative wave equation

Using Fourier integral operators with special amplitude functions, we analyze the stabilization of the wave equation in a three-dimensional bounded domain on which exists a trapped ray bouncing up and down infinitely between two parallel parts of the boundary.     

Integral representations of harmonic functions in half spaces

In this paper, using a modified Poisson kernel in an upper half-space, we prove that a harmonic function u(z) in a upper half space with its positive part u⁺(x)=max{u(x),0} satisfying a slowly growing condition can be represented by its integral in the boundary of the upper half space, the integral representation is unique up to the addition of a harmonic polynomial, vanishing in the boundary of the upper half space and that its negative part u⁻(x)=max{−u(x),0} can be dominated by a similar slowly growing condition, this improves some classical result about harmonic functions in the upper half space.     

Random orderings of the integers and card shuffling

In this paper we study random orderings of the integers with a certain invariance property. We describe all such orders in a simple way. We define and represent random shuffles of a countable set of labels and then give an interpretation of these orders in terms of a class of generalized riffle shuffles.     

STABILITY NUMBER IN SUBCLASSES OF P5-FREE GRAPHS

Two new hereditary classes of P5-free graphs where the stability number can be found in polynomial time are proposed. They generalize several known results.