Perfection for pomonoids

A pomonoid S is a monoid equipped with a partial order that is compatible with the binary operation. In the same way that M-acts over a monoid M correspond to the representation of M by transformations of sets, S-posets correspond to the representation of a pomonoid S by order preserving transformations of posets.     

Algorithms for approximation of invariant measures for IFS

We prove convergence of two algorithms approximating invariant measures to iterated function systems numerically. We consider IFSs with finitely many continuous and injective non-overlapping maps on the unit interval. The first algorithm is a version of the Ulam algorithm for IFSs introduced by Strichartz et al. [16]. We obtain convergence in the supremum metric for distribution functions of the approximating eigen-measures to a unique invariant measure for the IFS. We have to make some modifications of the usual way of treating the Ulam algorithm due to a problem concerning approximate eigenvalues, which is part of our more general situation with weights not necessarily being related to the maps of the IFS. The second algorithm is a new recursive algorithm which is an analogue of forward step algorithms in the approximation theory of ODEs. It produces a sequence of approximating measures that converges to a unique invariant measure with geometric rate in the supremum metric. The main advantage of the recursive algorithm is that it runs much faster on a computer (using Maple) than the Ulam algorithm.Mathematics Subject Classification (2000): 37A30, 37C30, 37M25, 47A58Acknowledgement I would like to express my deep gratitude to Andreas Strömbergsson and to the anonymous referee. The referee had several very enlightening comments, which Andreas helped me to deal with. Section 4 is essentially due to Andreas and he also came up with the new Proposition 3 and helped me to improve Lemma 1. Thanks also to Svante Janson, Anders Johansson, Sten Kaijser, Robert Strichartz and Hans Wallin.     

Symmetric excited states for a mean-field model for a nucleon

In this paper, we consider a stationary model for a nucleon interacting with the ω and σ mesons in the atomic nucleus. The model is relativistic, and we study it in a nuclear physics nonrelativistic limit. By a shooting method, we prove the existence of infinitely many solutions with a given angular momentum. These solutions are ordered by the number of nodes of each component.     

A constant-factor approximation algorithm for multi-vehicle collection for processing problem

We define the multiple-vehicle collection for processing problem (mCfPP) as a vehicle routing and scheduling problem in which items that accumulate at customer sites over time should be transferred by a series of tours to a processing facility. We show that this problem with the makespan objective (mCfPP( $C_{\max }$ )) is NP-hard using an approximation preserving reduction from a two-stage, hybrid flowshop scheduling problem. We develop a polynomial-time, constant-factor approximation algorithm to solve mCfPP( $C_{\max }$ ). The problem with a single site is analyzed as a special case with two purposes. First, we identify the minimum number of vehicles required to achieve a lower bound on the makespan, and second, we characterize the optimal makespan when a single vehicle is utilized.     

An Algorithm for Robust Inference for the Cox Model with Frailties

Abstract

This article proposes a robust method of statistical inference for the Cox's proportional hazards model with frailties. We use the Metropolis—Hastings algorithm and the bootstrap method. We present a computationally efficient algorithm with a customized data structure to implement this method and demonstrate this technique with real data.     

Projection Method for Cauchy Problem for an Operator-Differential Equation

In the current paper, we study a projection method for a Cauchy problem for an operator-differential equation with a leading self-adjoint operator A(t) and a subordinate linear operator K(t) in a Hilbert space. The projection subspaces are linear spans of eigenvectors of an operator similar to A(t). It is assumed that the operators A(t) and K(t) are sufficiently smooth. Error estimates for the approximate solutions and their derivatives are obtained. The application of the developed method for solving the initial boundary value problems is given.     

Preventive Support for Kindergarteners Most At-Risk for Mathematics Difficulties: Computer-Assisted Intervention

Weaknesses in early number skills have been found to be a risk factor for later difficulties in mathematical performance. Nevertheless, only a few intervention studies with young children have been published. In this study, the responsiveness to early support in kindergarteners with most severe difficulties was examined with two different computer programs. Two intervention groups were matched by age, visuo-spatial, and phonological working memory, as well as early number skills. After a short and intensive computerized intervention, the results indicated significant intervention effects for verbal counting Wilcoxon ES (r) = 0.46, and dot counting fluency, r = 0.52, when practiced with GraphoGame Math, as well as for basic arithmetic, r = 0.63, when practiced with Number Race. The findings suggest that a targeted computerized practice can produce specific training effects in kindergarteners most at-risk for mathematics difficulties. The results are discussed with regard to practical implications for educational game development.     

Error estimates for a Galerkin method for a class of model equations for long waves

The Galerkin method, together with a second order time discretization, is applied to the periodic initial value problem for $$\frac{\partial }{{\partial t}}(u - (a(x)u_x )_x ) + (f(x,u))_x = 0$$ . Heref(x, ·) may be highly nonlinear, but a certain cancellation effect is assumed for∫f(x, u) _x u. Optimal order error estimates inL ₂,H ₁, andL _∞ are derived for a general class of piecewise polynomial spaces.     

A ternary structure for biplanes

In this paper we introduce a ternary operation with certain qualities on a set ofk–1 elements and prove that it generates a biplane withk points on a block, and also that any (finite) biplane withk points on a block gives rise to at least one algebraic structure with the above qualities.     

Computing solutions for matching games

A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting w: E? \mathbb R₊{w: E\to {\mathbb R}_+}. The player set is N and the value of a coalition S í N{S \subseteq N} is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n ² log n) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core member if the core is nonempty. This algorithm improves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments. Second we show that the nucleolus of an n-player matching game with a nonempty core can be computed in O(n ⁴) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games.     

New methods for determining quasi-stationary distributions for markov chains

We shall be concerned with the problem of determining quasi-stationary distributions for Markovian models directly from their transition rates Q. We shall present simple conditions for a μ-invariant measure m for Q to be μ-invariant for the transition function, so that if m is finite, it can be normalized to produce a quasi-stationary distribution.     

Probabilistic and deterministic convergence proofs for software for initial value problems

The numerical solution of initial value problems for ordinary differential equations is frequently performed by means of adaptive algorithms with user-input tolerance τ. The time-step is then chosen according to an estimate, based on small time-step heuristics, designed to try and ensure that an approximation to the local error commited is bounded by τ. A question of natural interest is to determine how the global error behaves with respect to the tolerance τ. This has obvious practical interest and also leads to an interesting problem in mathematical analysis. The primary difficulties arising in the analysis are that: (i) the time-step selection mechanisms used in practice are discontinuous as functions of the specified data; (ii) the small time-step heuristics underlying the control of the local error can break down in some cases. In this paper an analysis is presented which incorporates these two difficulties. For a mathematical model of an error per unit step or error per step adaptive Runge–Kutta algorithm, it may be shown that in a certain probabilistic sense, with respect to a measure on the space of initial data, the small time-step heuristics are valid with probability one, leading to a probabilistic convergence result for the global error as τ→0. The probabilistic approach is only valid in dimension m>1 this observation is consistent with recent analysis concerning the existence of spurious steady solutions of software codes which highlights the difference between the cases m=1 and m>1. The breakdown of the small time-step heuristics can be circumvented by making minor modifications to the algorithm, leading to a deterministic convergence proof for the global error of such algorithms as τ→0. An underlying theory is developed and the deterministic and probabilistic convergence results proved as particular applications of this theory. This revised version was published online in June 2006 with corrections to the Cover Date.     

A numerical method for solving the Dirichlet problem for the wave equation

In this paper we present a numerical method for solving the Dirichlet problem for a two-dimensional wave equation. We analyze the ill-posedness of the problem and construct a regularization algorithm. Using the Fourier series expansion with respect to one variable, we reduce the problem to a sequence of Dirichlet problems for one-dimensional wave equations. The first stage of regularization consists in selecting a finite number of problems from this sequence. Each of the selected Dirichlet problems is formulated as an inverse problem Aq = f with respect to a direct (well-posed) problem. We derive formulas for singular values of the operator A in the case of constant coefficients and analyze their behavior to judge the degree of ill-posedness of the corresponding problem. The problem Aq = f on a uniform grid is reduced to a system of linear algebraic equations A _ll q = F. Using the singular value decomposition, we find singular values of the matrix A _ll and develop a numerical algorithm for constructing the r-solution of the original problem. This algorithm was tested on a discrete problem with relatively small number of grid nodes. To improve the calculated r-solution, we applied optimization but observed no noticeable changes. The results of computational experiments are illustrated.     

A method for constructing t-norms

In this paper a new type of t-operators with double thresholda,b ∈ (0,1),a ≤b, is presented, each pair (t-norm,t-conorm) consisting of two dual elements with respect to a negation with double threshold.     

Some existence theorems for the Dirichlet problem for quasilinear elliptic equations

Summary The purpose of this paper is to establish the existence of a solution of the Dirichlet problem for a quasilinear elliptic equation. We prove that the problem (1), (2) is solvable for all _j (j=1,...), where _j are eigenvalues of a linear elliptic operator that is associated with a given quasilinear elliptic operator by a limiting process. We also discuss this problem with a boundary data in L². This leads in a natural way to the Dirichlet problem in a weighted Sobolev space.     

Contraction obstructions for treewidth

We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.     

Redundancy for localized frames

Redundancy is the qualitative property which makes Hilbert space frames so useful in practice. However, developing a meaningful quantitative notion of redundancy for infinite frames has proven elusive. Though quantitative candidates for redundancy exist, the main open problem is whether a frame with redundancy greater than one contains a subframe with redundancy arbitrarily close to one. We will answer this question in the affirmative for ℓ ¹-localized frames. We then specialize our results to Gabor multi-frames with generators in M ¹(R ^d ), and Gabor molecules with envelopes in W(C, l ¹). As a main tool in this work, we show there is a universal function g(x) so that, for every ε =s> 0, every Parseval frame {f _i } _i=1 ^M for an N-dimensional Hilbert space H _N has a subset of fewer than (1+ε)N elements which is a frame for H _N with lower frame bound g(ε/(2M/N − 1)). This work provides the first meaningful quantative notion of redundancy for a large class of infinite frames. In addition, the results give compelling new evidence in support of a general definition of redundancy given in [5].     

Remarks on multiplicity result for the Dirichlet problem for nonlinear elliptic equations

In this paper we prove the multiplicity result for the Dirichlet problems (A _s ) and (B _t ) with a boundary data inL ² (ϖQ) and with the nonlinearity interacting with the spectrum of the elliptic operatorL. The fact that the boundary data is inL ² leads in a natural way to the Dirichlet problem in a weighted Sobolev space. We follow methods and arguments from the recent papers of Walter and McKenna [11] and [12].     

Necessary and Sufficient Conditions for Viability for Nonlinear Evolution Inclusions

We consider the viability problem for nonlinear evolutions inclusions of the form u′(t)?∈?Au(t)?+?F(u(t)), where A is an m-dissipative (possible nonlinear and multi-valued) operator acting in a Banach space X, K?X is a nonempty, locally closed set and $F:K{\user1{ \rightsquigarrow }}X$ is with nonempty, convex, closed and bounded values. We define the concept of A-quasi-tangent set to K at a given point ξ?∈?K and we prove a necessary condition for C ⁰-viability expressed in terms of this new tangency concept. We next show that, under various natural extra-assumptions, the necessary condition is also sufficient. We extend the results to the quasi-autonomous case, we deal with the existence of noncontinuable or even global C ⁰-solutions and, as applications, we deduce a comparison result and a sufficient condition for null controllability.