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.     

A large set containing few orbits of measure preserving transformations

Summary There exists a Borel set C of product Lebesgue measure one in the Hilbert cube having the property that, for every measure preserving transformationT of the unit interval, allT-orbits contained inC originate from a zero set. This settles an infinite dimensional version of a problem raised by Th. M. Rassias.     

Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.     

Partially finite convex programming,Part I: Quasi relative interiors and duality theory

We study convex programs that involve the minimization of a convex function over a convex subset of a topological vector space, subject to a finite number of linear inequalities. We develop the notion of the quasi relative interior of a convex set, an extension of the relative interior in finite dimensions. We use this idea in a constraint qualification for a fundamental Fenchel duality result, and then deduce duality results for these problems despite the almost invariable failure of the standard Slater condition. Part II of this work studies applications to more concrete models, whose dual problems are often finite-dimensional and computationally tractable.     

Relatively pseudocomplemented semilattices amalgamate strongly

Letk be any finite or infinite cardinal andS _ω the symmetric group of denumerable infinite degree. It is shown that fori<k ifG _i is thei-th row of a matrix whose columns are allk-termed sequences of elements ofS _ω in each of which all but a finite number of terms are equal to the identity ofS _ω thenG _i 's (withG _i ⁻¹ 's defined in an obvious way and with coordinatewise multiplication amongG _i 's andG _i ⁻¹'s) generate the Free Group onk free generatorsG _i . Analogously, Free Abelian and other types of free groups are also constructed. Presented by L. Fuchs.     

Spatially homogeneous random evolutions

Spatially homogeneous random evolutions arise in the study of the growth of a population in a spatially homogeneous random environment. The random evolution is obtained as the solution of a bilinear stochastic evolution equation. The main results are concerned with the asymptotic behavior of the solution for large times. In particular, conditions for the existence of a stationary random field are established. Furthermore space-time renormalization limit theorems are obtained which lead to either Gaussian or non-Gaussian generalized processes depending on the case under consideration.     

Lipschitz gradients for global optimization in a one-point-based partitioning scheme

A global optimization problem is studied where the objective function f(x)$f\left(x\right)$ is a multidimensional black-box function and its gradient f^′(x)$f^{\prime }\left(x\right)$ satisfies the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant K$K$. Different methods for solving this problem by using an a priori given estimate of K$K$, its adaptive estimates, and adaptive estimates of local Lipschitz constants are known in the literature. Recently, the authors have proposed a one-dimensional algorithm working with multiple estimates of the Lipschitz constant for f^′(x)$f^{\prime }\left(x\right)$ (the existence of such an algorithm was a challenge for 15 years). In this paper, a new multidimensional geometric method evolving the ideas of this one-dimensional scheme and using an efficient one-point-based partitioning strategy is proposed. Numerical experiments executed on 800 multidimensional test functions demonstrate quite a promising performance in comparison with popular DIRECT-based methods.     

Polynomial solution of the most general linear Fredholm integrodifferential–difference equations by means of Taylor matrix method

In this article, a Taylor matrix method is developed to find an approximate solution of the most general linear Fredholm integrodifferential–difference equations with variable coefficients under the mixed conditions in terms of Taylor polynomials. Also numerical examples are presented, which illustrate the pertinent features of the method. In some numerical examples, MAPLE modules are designed for the purpose of testing and using the method.     

The subconstituent algebra of a bipartite distance-regular graph; thin modules with endpoint two

We consider a bipartite distance-regular graph Γ with diameter D?4, valency k?3, intersection numbers b_i,c_i, distance matrices A_i, and eigenvalues θ₀>θ₁>?>θ_D. Let X denote the vertex set of Γ and fix x∈X. Let T=T(x) denote the subalgebra of Mat_X(C) generated by , where A=A₁ and denotes the projection onto the ith subconstituent of Γ with respect to x. T is called the subconstituent algebra (or Terwilliger algebra) of Γ with respect to x. An irreducible T-module W is said to be thin whenever for 0?i?D. By the endpoint of W we mean . Assume W is thin with endpoint 2. Observe is a one-dimensional eigenspace for ; let η denote the corresponding eigenvalue. It is known where , and d=⌊D/2⌋. To describe the structure of W we distinguish four cases: (i) ; (ii) D is odd and ; (iii) D is even and ; (iv) . We investigated cases (i), (ii) in MacLean and Terwilliger [Taut distance-regular graphs and the subconstituent algebra, Discrete Math. 306 (2006) 1694-1721]. Here we investigate cases (iii), (iv) and obtain the following results. We show the dimension of W is D-1-e where e=1 in case (iii) and e=0 in case (iv). Let v denote a nonzero vector in . We show W has a basis , where E_i denotes the primitive idempotent of A associated with θ_i and where the set S is {1,2,…,d-1}∪{d+1,d+2,…,D-1} in case (iii) and {1,2,…,D-1} in case (iv). We show this basis is orthogonal (with respect to the Hermitian dot product) and we compute the square-norm of each basis vector. We show W has a basis , and we find the matrix representing A with respect to this basis. We show this basis is orthogonal and we compute the square-norm of each basis vector. We find the transition matrix relating our two bases for W.     

Total restrained domination in graphs with minimum degree two

In this paper, we continue the study of total restrained domination in graphs, a concept introduced by Telle and Proskurowksi (Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550) as a vertex partitioning problem. A set S of vertices in a graph G=(V,E) is a total restrained dominating set of G if every vertex is adjacent to a vertex in S and every vertex of V?S is adjacent to a vertex in V?S. The minimum cardinality of a total restrained dominating set of G is the total restrained domination number of G, denoted by γ_tr(G). Let G be a connected graph of order n with minimum degree at least 2 and with maximum degree Δ where Δ?n-2. We prove that if n?4, then and this bound is sharp. If we restrict G to a bipartite graph with Δ?3, then we improve this bound by showing that and that this bound is sharp.