Search

This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps f , g : X → Y , and the second computes the group [ Σ X , Y ] ∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to A ⊆ X . [ABSTRACT FROM AUTHOR]

An automated general purpose method is introduced for computing a rigorous estimate of a bounded region in ℝ n whose points satisfy a given property. The method is based on calculations conducted in interval arithmetic and the constructed approximation is built of rectangular boxes of variable sizes. An efficient strategy is proposed, which makes use of parallel computations on multiple machines and refines the estimate gradually. It is proved that under certain assumptions the result of computations converges to the exact result as the precision of calculations increases. The time complexity of the algorithm is analyzed, and the effectiveness of this approach is illustrated by constructing a lower bound on the set of parameters for which an overcompensatory nonlinear Leslie population model exhibits more than one attractor, which is of interest from the biological point of view. This paper is accompanied by efficient and flexible software written in C++ whose source code is freely available at . [ABSTRACT FROM AUTHOR]

In this paper we describe a singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. Singly exponential algorithms for computing the zeroth Betti number, and the Euler–Poincaré characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zeroth one. As a consequence we also obtain algorithms for computing semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set in singly exponential time, which improves on the complexity of the previously published algorithms for this problem. [ABSTRACT FROM AUTHOR]