Stochastic flows associated to coalescent processes

 We study a class of stochastic flows connected to the coalescent processes that have been studied recently by M?hle, Pitman, Sagitov and Schweinsberg in connection with asymptotic models for the genealogy of populations with a large fixed size. We define a bridge to be a right-continuous process (B(r),r[0,1]) with nondecreasing paths and exchangeable increments, such that B(0)=0 and B(1)=1. We show that flows of bridges are in one-to-one correspondence with the so-called exchangeable coalescents. This yields an infinite-dimensional version of the classical Kingman representation for exchangeable partitions of ℕ. We then propose a Poissonian construction of a general class of flows of bridges and identify the associated coalescents. We also discuss an important auxiliary measure-valued process, which is closely related to the genealogical structure coded by the coalescent and can be viewed as a generalized Fleming-Viot process. Received: 26 November 2002 / Revised version: 10 February 2003 / Published online: 15 April 2003 Mathematics Subject Classification (2000): 60G09, 60J25, 92D30 Key words or phrases: Flow – Coalescence – Exchangeability – Bridge     

Projection methods preserving Lyapunov functions

In this paper we consider ordinary differential equations with a known Lyapunov function. We study the use of Runge–Kutta methods provided with a dense output and a projection technique to preserve any given Lyapunov function. This approach extends previous work of Grimm and Quispel (BIT 45, 2005), allowing the use of Runge–Kutta methods for which the associated quadrature formula does not need to have positive or zero coefficients. Some numerical experiments show the good performance of the proposed technique.     

First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51     

An experimentally based analytical model for the shear capacity of FRP-strengthened reinforced concrete beams

This paper deals with the shear strengthening of Reinforced Concrete (RC) flexural members with externally bonded Fiber-Reinforced Polymers (FRPs). The interaction between an external FRP and an internal transverse steel reinforcement is not considered in actual code recommendations, but it strongly influences the efficiency of the shear strengthening rehabilitation technique and, as a consequence, the computation of interacting contributions to the nominal shear strength of beams. This circumstance is also discussed on the basis of the results of an experimental investigation of rectangular RC beams strengthened in shear with “U-jacketed” carbon FRP sheets. Based on experimental results of the present and other investigations, a new analytical model for describing the shear capacity of RC beams strengthened according to the most common schemes (side-bonded and “U-jacketed”), taking into account the interaction between steel and FRP shear strength contributions, is proposed. Russian translation published in Mekhanika Kompozitnykh Materialov, Vol. 44, No. 3, pp. 339–356, May–June, 2008.     

Instrumenting Mathematical Activity: Reflections on Key Studies of the Educational Use of Computer Algebra Systems

This paper examines the process through which students learn to make functional use of computer algebra systems (CAS), and the interaction between that process and the wider mathematical development of students. The result of ‘instrumentalising‘ a device to become a mathematical tool and correspondingly ‘instrumenting’ mathematical activity through use of that tool is not only to extend students' mathematical technique but to shape their sense of the mathematical entities involved. These ideas have been developed within a French programme of research – as reported by Artigue in this issue of the journal – which has explored the integration of CAS – typically in the form of symbolic calculators – into the everyday practice of mathematics classrooms. The French research –influenced by socio-psychological theorisation of the development of conceptual systems- seeks to take account of the cultural and cognitive facets of these issues, noting how mathematical norms – or their absence – shape the mental schemes which students form as they appropriate CAS as tools. Instrumenting graphic and symbolic reasoning through using CAS influences the range and form of the tasks and techniques experienced by students, and so the resources available for more explicit codification and theorisation of such reasoning. This illuminates an influential North American study– conducted by Heid – which French researchers have seen as taking a contrasting view of the part played by technical activity in developing conceptual understanding. Reconsidered from this perspective, it appears that while teaching approaches which ‘resequence skills and concepts’ indeed defer – and diminish –attention to routinised skills, the tasks introduced in their place depend on another –albeit less strongly codified – system of techniques, supporting more extensive and active theorisation. The French research high lights important challenges which arise in instrumenting classroom mathematical activity and correspondingly instrumentalising CAS. In particular, it reveals fundamental constraints on human-machine interaction which may limit the capacity of the present generation of CAS to scaffold the mathematical thinking and learning of students. This revised version was published online in July 2006 with corrections to the Cover Date.     

Stability of Lotka–Volterra system

The stability of Lotka–Volterra system has been discussed by many authors for two and three species. In this paper, we will discussed the notion of stability for a Lotka–Volterra system with four species. Some criteria and results are given. Our technique depends on the Lyapunov–Razumikhin method. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 61, Optimal Control, 2008.     

Poissonian subordinators,the Wiener–Ornstein–Uhlenbeck field,and a relation between the Ornstein–Uhlenbeck processes and Brownian bridges

We apply to a sequence of i.i.d. random variables a time change operator via a Poisson process that is independent of this sequence. We consider sums of independent copies of processes constructed in this way and having continuous time. Finite limit distributions of these sums coincide with the finite limit distributions of the Wiener–Ornstein–Uhlenbeck field that is the tensor product of a Brownian motion and the Ornstein–Uhlenbeck process. The transition characteristics of the limit Ornstein–Uhlenbeck process are described by Brownian bridges that are builded into the Wiener–Ornstein–Uhlenbeck field. Bibliography: 4 titles.     

Propagation of torsional waves in a prestretched compound hollow circular cylinder

The propagation of torsional waves in a prestressed compound (bi-layered) hollow circular cylinder is in vestigated within the frame work of a piecewise homogeneous body model, with the use of a three-dimensional linerized theory of elastic waves in initially stressed bodies. The elasticity relations for components of the compound cylinder are obtained from the Murnaghan potential. Numerical investigations are performed for bronze and steel. According to the results obtained, the effect of variations in the geometric (the ratio between the thickness of the cylinder and its inner radius) and mechanical parameters on the dispersion curves are analyzed. Russian translation published in Mekhanika Kompozitnykh Materialov, Vol. 44, No. 1, pp. 103–116, January–February, 2008.     

The Stratified Sampling Bootstrap for Measuring the Uncertainty in Mortality Forecasts

In this paper, we propose a procedure for reducing the uncertainty in mortality projections, on the basis of a log bilinear Poisson Lee Carter model (Renshaw and Haberman Appl Stat 52:119–137, 2003a). In the literature, because the non-linear nature of the quantities under consideration has prevented analytical solutions, simulation techniques have been used in order to provide prediction intervals for forecasted quantities (for example, Brouhns et al. Scand Actuar J 3:212–224, 2005, Renshaw and Haberman Insur Math Econ 42:797–816, 2008). In this respect, we adopt the bootstrap simulation approach in order to measure the uncertainty affecting mortality projections. In particular, we propose making the bootstrap procedure more efficient by using a specific variance reducing technique, the so-called Stratified Sampling technique. To this end, we propose a two stage simulation bootstrap procedure where variance reducing techniques are combined with the simple bootstrap of the Poisson Lee Carter version. Numerical applications are shown using the results for some datasets.     

A Simple Proof of the Restricted Isometry Property for Random Matrices

We give a simple technique for verifying the Restricted Isometry Property (as introduced by Candès and Tao) for random matrices that underlies Compressed Sensing. Our approach has two main ingredients: (i) concentration inequalities for random inner products that have recently provided algorithmically simple proofs of the Johnson–Lindenstrauss lemma; and (ii) covering numbers for finite-dimensional balls in Euclidean space. This leads to an elementary proof of the Restricted Isometry Property and brings out connections between Compressed Sensing and the Johnson–Lindenstrauss lemma. As a result, we obtain simple and direct proofs of Kashin’s theorems on widths of finite balls in Euclidean space (and their improvements due to Gluskin) and proofs of the existence of optimal Compressed Sensing measurement matrices. In the process, we also prove that these measurements have a certain universality with respect to the sparsity-inducing basis.      

Analysis of space–time discontinuous Galerkin method for nonlinear convection–diffusion problems

The paper presents the theory of the discontinuous Galerkin finite element method for the space–time discretization of a nonstationary convection–diffusion initial-boundary value problem with nonlinear convection and linear diffusion. The problem is not singularly perturbed with dominating convection. The discontinuous Galerkin method is applied separately in space and time using, in general, different space grids on different time levels and different polynomial degrees p and q in space and time dicretization. In the space discretization the nonsymmetric, symmetric and incomplete interior and boundary penalty (NIPG, SIPG, IIPG) approximation of diffusion terms is used. The paper is concerned with the proof of error estimates in “L ²(L ²)”- and “DG”-norm formed by the “L ²(H ¹)”-seminorm and penalty terms. A special technique based on the use of the Gauss–Radau interpolation and numerical integration has been used for the derivation of an abstract error estimate. In the “DG”-norm the error estimates are optimal with respect to the size of the space grid. They are optimal with respect to the time step, if the Dirichlet boundary condition has behaviour in time as a polynomial of degree ≤ q.     

Schubert polynomials of types A--D

Schubert polynomials of type B, C, and D have been described first by S. Billey and M. Haiman [BH] using a combinatorial method. In this paper we give a unified algebraic treatment of Schubert polynomials of types A–D in the style of the Lascoux–Schützenberger theory in type A, i.e. Schubert polynomials are generated by the application of sequences of divided difference operators to “top polynomials”. The use of the creation operators for Q-Schur and P-Schur functions allows us to give: (1) simple and natural forms of the “top polynomials”, (2) formulas for the easy computation with all divided differences, (3) recursive structures, and (4) simplified derivations of basic properties. Received: 23 July 1998     

An analytical study on the bond behaviour between an externally bonded FRP and concrete in the case of continuous beams

One of the greatest challenges in structural engineering nowadays is the strengthening, upgrading, and retrofitting of existing structures. The use of fibre-reinforced polymers (FRPs) bonded to the tension face of a structural member is an attractive technique in this field of application. The strengthening of reinforced concrete structures by means of an externally bonded reinforcement (EBR) is achieved by gluing a FRP laminate to the concrete substrate. For an efficient utilization of the FRP EBR systems, an effective stress transfer is required between the FRP and concrete. The paper discusses the bond behaviour between a FRP and concrete in the case of flexural strengthening of continuous beams. With respect to this type of beams, only a few studies have been reported, though continuous members often occur in concrete constructions. The structural behaviour of statically indeterminate elements is typically characterized by redistributions of the internal forces. These distributions are related to the nonlinear deformations of the beams and has also a distinct influence on the bond behaviour between the FRP and concrete. Russian translation published in Mekhanika Kompozitnykh Materialov, Vol. 44, No. 3, pp. 389–402, May–June, 2008.     

Treating Free Variables in Generalized Geometric Global Optimization Programs

Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Recently, some exponential-based decomposition methods [Maranas and Floudas, 1997,Computers and Chemical Engineering 21(4), 351–370; Floudas et al., 1999 , Handbook of Test Problems in Local and Global Optimization, Kluwer Academic Publishers, Boston, pp. 5–105; Floudas, 2000 Deterministic Global Optimizaion: Theory, Methods and Application, Kluwer Academic Publishers, Boston, pp. 257–306] have been developed for GGP problems. These methods can only handle problems with positive variables, and are incapable of solving more general GGP problems. This study proposes a technique for treating free (i.e., positive, zero or negative) variables in GGP problems. Computationally effective convexification rules are also provided for signomial terms with three variables.     

The Diffie–Hellman problem and generalization of Verheul’s theorem

Bilinear pairings on elliptic curves have been of much interest in cryptography recently. Most of the protocols involving pairings rely on the hardness of the bilinear Diffie–Hellman problem. In contrast to the discrete log (or Diffie–Hellman) problem in a finite field, the difficulty of this problem has not yet been much studied. In 2001, Verheul (Advances in Cryptology—EUROCRYPT 2001, LNCS 2045, pp. 195–210, 2001) proved that on a certain class of curves, the discrete log and Diffie–Hellman problems are unlikely to be provably equivalent to the same problems in a corresponding finite field unless both Diffie–Hellman problems are easy. In this paper we generalize Verheul’s theorem and discuss the implications on the security of pairing based systems.      

Spectral gaps in the dirichlet and neumann problems on the plane perforated by a doubleperiodic family of circular holes

We show that the spectrum of the Dirichlet and Neumann problems for the Laplace operator in the plane perforated by a double–periodic family of circular holes contains gaps (even any a priori given number of gaps) of certain radii of holes. The result is obtained by asymptotic analysis of the cell spectral problem, interpreted as a problem in a domain with thin bridges. Some open questions are stated.     

Interval propagation and search on directed acyclic graphs for numerical constraint solving

The fundamentals of interval analysis on directed acyclic graphs (DAGs) for global optimization and constraint propagation have recently been proposed in Schichl and Neumaier (J. Global Optim. 33, 541–562, 2005). For representing numerical problems, the authors use DAGs whose nodes are subexpressions and whose directed edges are computational flows. Compared to tree-based representations [Benhamou et al. Proceedings of the International Conference on Logic Programming (ICLP’99), pp. 230–244. Las Cruces, USA (1999)], DAGs offer the essential advantage of more accurately handling the influence of subexpressions shared by several constraints on the overall system during propagation. In this paper we show how interval constraint propagation and search on DAGs can be made practical and efficient by: (1) flexibly choosing the nodes on which propagations must be performed, and (2) working with partial subgraphs of the initial DAG rather than with the entire graph. We propose a new interval constraint propagation technique which exploits the influence of subexpressions on all the constraints together rather than on individual constraints. We then show how the new propagation technique can be integrated into branch-and-prune search to solve numerical constraint satisfaction problems. This algorithm is able to outperform its obvious contenders, as shown by the experiments.     

Cognitive and self-selective routing for sensor networks

New approaches to Quality-of-Service (QoS) routing in wireless sensor networks which use different forms of learning are the subject of this paper. The Cognitive Packet Network (CPN) algorithm uses smart packets for path discovery, together with reinforcement learning and neural networks, while Self-Selective Routing (SSR) is based on the “Ant Colony” paradigm which emulates the pheromone-based technique which ants use to mark paths and communicate information about paths between different insects of the same colony (Koenig et al. in Ann Math Artif Intell 31(1–4): 41–76, 2001). In this paper, we present first experimental results on a network test-bed to evaluate CPN’s ability to discover paths having the shortest delay, or shortest length. Then, we present small test-bed experiments and large-scale network simulations to evaluate the effectiveness of the SSR algorithm. Finally, the two approaches are compared with respect to their ability to adapt as network conditions change over time.     

Analysing maintenance data to gain insight into systems performance

The high cost of maintenance in the processing industry implies the need for optimal planning of maintenance strategy. In order to achieve this there is a need to understand the underlying failure processes, which are often very complex. In this paper, a new semi-parametric approach, combining Cox regression with density kernal smoothing, is introduced to estimate the underlying performance. The approach has been applied to several processes and it allowed insight into each process, which would not have been achieved if traditional approaches had been used. Particularly, the refurbishment of processes had a significant impact on the rate failure. This paper concludes by assessing this impact of refurbishment on the maintenance programme.     

A test for legitimate decks

Bondy and Hemminger (Graph reconstruction—a survey, J. Graph Theory 1 (1977) 227–268) give three necessary conditions namely subgraph condition, degree sequence condition and symmetric array condition (of Randic) for Legitimate decks. We have strengthened the degree sequence condition (SDSC) and extended the symmetric array condition (ESAC). We prove that both these are necessary conditions for legitimate decks and ESAC implies SDSC and symmetric array condition. ESAC gives a graph G¹ which has the same degree sequence as the prospective graph determined by the deck and the point deletions of G¹ have the same degree sequence as the given cards. Examples of illegitimate decks satisfying ESAC, legitimate decks giving G¹ with point deletions different from the given deck, deck giving more than one (non isomorphic) G¹ etc. are given. We develop this ESAC to a test to determine whether a deck is legitimate or not. Also we point out how the failure of reconstruction conjecture (if it is so) for (p?1)-point graphs can hamper the characterization of legitimate decks of p-point graphs. We extend these results to colored graphs and digraphs also.