Abstract: Handling three-dimensional objects is required for mechanical design, thermal study, mathematical illustrations... Transferring objects between applications is possible using plug-ins and a common specification. Many low level specifications, like wavefront .obj, use coordinates. In contrast, Pycao is a language developed as a python module to avoid coordinates as much as possible. The primary focus is on geometrical concepts for the most concise possible description of the objects. The paradigms include the classical framework of affine geometry, carrying objects inside boxes, various frames attached to those boxes, markers glued to the objects, and a class to build libraries. In the backend, the computations take place in a massive space, to globalize the affine and linear constructions, and to handle barycenters easily. A "natural geometrical language" for 3d-objects is still to be defined by consensus as an aggregation of concepts from various pieces of software. Pycao is a step in this direction. The goal of the talk is to describe the concepts used in the pycao software, both from the end-user and from the developer point of view. The pycao language, with documentation and a povray plug-in can be downloaded: http://math.univ-angers.fr/~evain/software/softwareIntro.html
Abstract: Over the recent years, the importance of research software has gradually been more recognized. One may well say that a numerical experiment has become a valid and important part of a publication, especially in applied mathematics. Nonetheless, there are no generally applied scientific standards for computer based experiments. To start with, the documentation on how computational results have been obtained is often not available or very immature. Especially in the scientific computing and applied mathematics domain this is crucial, since numerical software is usually employed to verify hypotheses in a publication. Without the means to confirm these results, claims about validity, accuracy and performance cannot (fully) be comprehended. In this contribution, we address the general issue of good scientific practices for computer based experiments via the notions of replicability, reproducibility, and reusability. Based on theoretical considerations, we propose best practices for mathematical software which fit all projects that meet some basic requirements. These minimal, but still widely applicable, recommendations are assembled into a guideline which is accompanied by real-world examples.
Abstract: Currently, only a limited number of fonts are available for high quality mathematical typesetting, such as Knuth's computer modern font, the Stix font, and several fonts from the TeX Gyre family. An interesting challenge is to develop tools which allow users to pick any existing favorite font and to use it for writing mathematical texts. We will present progress on this problem as part of recent developments in the GNU TeXmacs scientific text editor.
Abstract: Voronoi diagrams tessellate the space where each cell corresponds to an associated generator under an a priori defined distance definition and have been extensively used to solve geometric problems in various disciplines. Additively-weighted Voronoi diagrams, also called the Voronoi diagram of circular disks and spherical balls, have many critical applications and a few algorithms are known. However, algorithmic robustness remains a major hurdle to use these Voronoi diagrams in practice. There are two primary approaches to design robust algorithms: the exact-computation and topology-oriented approaches. The former uses high-precision arithmetic and guarantees mathematical correctness with a high cost of computational resources. The latter focuses on topological properties to keep consistency using logical computation rather than numerical computation. In this paper, we present a robust and efficient algorithm for computing the Voronoi diagram of circular disks using a topology-oriented incremental method. The algorithm is rather simple as it primarily checks topological changes only during each disk is incrementally inserted into a previously constructed Voronoi diagram of some other disks. We will show that the proposed algorithm is significantly superior to CGAL in both robustness and efficiency, particularly for big data. Then, we will discuss how the topology-oriented incremental method can be easily applied to construct the Voronoi diagram of spherical balls.
Keywords: topology-oriented,additively-weighted,Voronoidiagram, disk, circle, robustness, algorithm
Abstract: To analyze a priori the accuracy of an algorithm in floating-point arithmetic, one usually derives a uniform error bound on the output, valid for most inputs and parametrized by the precision p. To show further that this bound is sharp, a common way is to build an input example for which the error committed by the algorithm comes close to that bound, or even attains it. Such inputs may be given as floating-point numbers in one of the IEEE standard formats (say, for p=53) or, more generally, as expressions parametrized by p, that can be viewed as symbolic floating-point numbers. With such inputs, a sharpness result can thus be established for virtually all reasonable formats instead of just one of them. This, however, requires the ability to run the algorithm on those inputs and, in particular, to compute the correctly-rounded sum, product, or ratio of two symbolic floating-point numbers. In this talk, we show how these basic arithmetic operations can be performed automatically. We introduce a way to model symbolic floating-point data, and present algorithms for round-to-nearest addition, multiplication, fused multiply-add and, in some cases, division. An implementation as a Maple library is also described, and experiments using examples from the literature are presented to illustrate its interest in practice.
Speaker: Antoine Plet
Abstract: It is commonly known that the free Boolean algebra on n free generators is isomorphic to the Boolean algebra of Boolean functions of n variables. The free distributive lattice on n free generators is isomorphic to the distributive lattice of monotone Boolean functions of n variables. In previous papers we have introduced the concept of De Morgan function and proved that the free De Morgan algebra on n free generators is isomorphic to the De Morgan algebra of De Morgan functions of n variables. This is a solution of the problem posed by B.I. Plotkin. A bilattice is a set with two lattice structures (the connection between the Lattice structures is postulated, too). Bilattices are a natural generalization of the classical two-valued logic, and were introduced by M. Ginsberg. Then M.Fitting found that bilattices provided a uniform semantics for the logic programming languages. Characterizations of bilattices of different varieties by the superproduct of two lattices proved by various authors (M.Ginsberg, M.Fitting, A.Romanowska, Yu.Movsisyan, J.D.H. Smith, A.Avron, and others) is well-known. In this paper we give a new characterization of distributive bilattices via new Boolean-type functions. Namely we introduce the concepts of bi-De Morgan function and prove that the bi-De Morgan functions of n variables form a distributive bilattice and that the free distributive bilattice on n free generators is isomorphic to the distributive bilattice of bi-De Morgan functions of n variables.
Abstract: We address a variant of the classical Steiner tree problem defined over undirected graphs (USTP). The objective is to determine the Steiner tree rooted at a source node with minimum cost and such that the number of edges is less than or equal to a given threshold. The link constrained USTP (LCSTP) belongs to the NP-hard class. We formulate a Lagrangian relaxation for the LCSTP in order to determine valid bounds on the optimal solution. To solve the Lagrangian dual, we develop a dual ascent heuristic based on updating one multiplier at time. The proposed heuristic relies on the execution of some sub-gradient iterations whenever the multiplier update procedure is not able to generate a significant increment of the Lagrangian dual objective. We calculate an upper bound on the LCSTP by adjusting the infeasibility of the solution obtained at each iteration. The solution strategy is tested on instances inspired by the scientific literature.
Abstract: The parallel machine scheduling environment is of fundamental practical and theoretical significance. In this research the authors present a complex heuristic approach based on tabu search for unrelated parallel machine scheduling with the objective of minimizing total completion times. Several theoretical results are provided that makes implementation of the algorithms for large-scale problems easy and fast. Computational results will be presented and compared with CPLEX software.