SWIM 08

Small Workshop on Interval Methods

Montpellier, France
June 2008, Thursday 19 and Friday 20,

LIRMM, Amphi St Priest

Université de Montpellier 2
Campus Saint-Priest - Bât. 2860,
rue de Saint Priest 34 090
Montpellier Cedex 5, France

Contact: Nacim Ramdani: nacim.ramdani(at)inria(dot)

Luc Jaulin: jaulinlu(at)ensieta(dot)fr

Swim08 is now finished. We had 21 speakers. Several countries were represented (Pologne, Brazil, Bulgaria, Spain, Canada, Switzerland, Pakistan, France). All talks and all questions have been done in English. The slides are now available for all (see below).

Next year Swim 09 will be. We don’t known yet where it will take place.

1)

2)

3)

4)

5)

6)

Why such a workshop?

Since about eight years, we have an active French working group named MEA (Méthodes ensemblistes pour l'automatique), which belongs to the larger structure GDR MACS. The MEA group encloses 235 people at the moment.

The aim of our MEA group is to promote interval analysis, constraint propagation and other set-based methods in order to apply these tools to estimation, robotics, control and other engineering areas.

Four times a year, we have a one-day scientific meeting (often in Paris) and we make our slides available on our website http://www.lirmm.fr/ensemble. Unfortunately, although our site is in French, most of the slides for the talks are in English and can be easily found on this site.

For instance, the slides of our last meeting are available at http://www.lirmm.fr/ensemble/spip.php?article12

This year, for the first time, we would like to open ourselves to the international interval community by organizing a two-day informal and free workshop in Montpellier (south of France). This workshop should offer the opportunity to review and discuss the state-of-the-art in interval methods and their applications.

How to participate?

It suffices to send us (i.e to Nacim Ramdani: nacim.ramdani@inria.fr and Luc Jaulin: jaulinlu@ensieta.fr) an email. That’s all. If you want to present a contribution, (of course, related to interval analysis, set-membership methods or constraint propagation), please, send us a title and a 10 lines abstract before June 10. Note that all slides will be made available in a pdf format on this site, after the workshop.

The workshop is free, but, nothing will be provided (no CD-Roms, no banquet, no meal…). Hopefully, Montpellier is a beautiful town, with good places to eat, nice hotels… and suggestions will be given. Do not hesitate to ask us any question.

Where SWIM 2008 took place?

SWIM’08 took place at the following address:

Amphi St Priest
Université Montpellier 2 –

Campus Saint-Priest - Bât. 2860,

rue de Saint Priest
34 090 Montpellier Cedex 5
France

From the center of Montpellier, Saint-Priest campus can be reached by tramway (line 1, direction Mosson) (stop at station « Château d'Ô »).

In case of problem, you can call the organizers Nacim (06 17 83 35 42) or Luc (06 82 99 00 41).

Preliminary Program

============================================================

Thursday June 19

9h00-10h00 : Welcome. Coffee

=============================================================

10h-12h :  Session  CSP , nonlinear system and intervals arithmetics

- Jamila Sam-Haroud, Artificial Intelligence Laboratory, Lausanne

(Switzerland)

Title: Enhancing numerical constraint propagation using multiple

inclusion representations

- Gilles Trombettoni, Gilles Chabert.

Title: Constructive Interval Disjunction: past, present, and future

- Ignacio Araya, Bertrand Neveu, Gilles Trombettoni.

Title: Exploiting Common Subexpressions in Numerical CSPs

- Jean-Pierre MERLET, INRIA Sophia Antipolis. Title: Influence of

uncertainties on ultrasonic localisation systems

Title: Computing the range of real eigenvalues of an interval matrix

- Nathalie Revol, INRIA Rhones Alpes

Title : Standardization and interval arithmetics

=============================================================

=============================================================

14h-15h : Plenary Talk

Ned Nedialkov, Dept. of Computing and Software, McMaster University,

Title: Interval Tools for ODEs and DAEs

=============================================================

=============================================================

============================================================

15h-16h30  : Session Continuous Reachability and Verification

- Nacim Ramdani, INRIA Sophia-Antipolis Mediterranee and LIRMM UMR 5506,

CNRS UM2 Montpellier.

Title: Reachability of uncertain nonlinear systems using a nonlinear

hybridization

- Olivier Bouissou, CEA Saclay - DRT/DTSI/SOL/MeASI Gif-sur-Yvette

Title: Using guaranteed integration of ODEs for the verification of

embedded software.

- Nicolas Delanoue, LISA, Angers.

Title: : Attraction domain of a nonlinear system using interval analysis.

- M. Lhommeau, LISA Angers

Title: Inner and outer approximation of the capture basin of a state

space model using interval analysis

===========================================================

16h30-17h30  : Session CSP again

- Dominique LOHEZ, ISEN-Lille

Title: Relational and Algebraic Concepts  for Automated  Interval Reasoning

- Guillaume Verger, LIRMM, Montpellier.

Title: CSPs and Quantified CSPs

- Maëlenn AUFRAY (ENSIACET - Toulouse), Adrien BROCHIER and Wulff POSSART

Title:  S.I.V.I.A. Applied to Dielectric Spectroscopy: a Guaranteed

Parameter Estimation Using Interval Analysis

===========================================================

20h00 Workshop Dinner.

===========================================================

===========================================================

Friday June 20th

===========================================================

===========================================================

9h00-9h30 : Coffee

===========================================================

===========================================================

9h30 -12h: Session Estimation,  uncertainty and CSP

- Olivier STRAUSS, LIRMM UMR CNRS Univ. Montpellier.

Title: Imprecise estimation in signal processing.

- Emmanuel Bénazéra, Louise Trave-Massuyes, LAAS, Toulouse.

Title: Set-Theoretic Estimation of Hybrid System Configurations.

- Farah Mourad, Fahed Abdallah, Hichem Snoussi, Cédric Richard, UTC,

LM2S, UTT

Title: Guaranteed boxed localization in MANETs by interval analysis and

constraints propagation techniques.

- Philippe LANGLOIS (DALI, Univ. Perpignan) and Nicolas Louvet (Arénaire, INRIA and ENS Lyon)

Title: Accurate results with compensated algorithms and validated error bounds in floating point computation: principles and applications.

- Jan Sliwka, ENSIETA, Brest.

Title: SAUC’ISSE : our interval robot

- Alexandre Goldsztejn

Title: A New Framework for Sharp and Efficient Resolution of NCSP with

Manifolds of Solutions

- Luc Jaulin and Gilles Chabert, ENSIETA.

Title: Resolution of nonlinear interval problems using symbolic interval

arithmetic.

- Gilles Chabert and Luc Jaulin, DTN, ENSIETA.

Title: : Interval and Boolean constraint propagation for simultaneous

localization and map building

- Sébastien LENGAGNE, Nacim RAMDANI, Philippe FRAISSE (LIRMM / INRIA)

Title: Application of Interval Analysis : safe path planning.

==========================================

==========================================

14h-15h : Visit of Robotics Lab. LIRMM.

==========================================

15h-16h : Round Table

==========================================

16h : End of Workshop

==========================================

==========================================

Abstracts

1)      Jan Sliwka, ENSIETA, Brest.

Title: SAUC’ISSE : our interval robot. Slides.

Movie of Sauc’isse taken by an underwater camera.

Movie of Sauc’isse for the experiment.

Data available for the localization.

Movie illustrating the interval localization method..

Results obtained by the interval localization method (txt file).

Abstract: Sauc’isse is an autonomous underwater robot. It uses interval computation and constraint propagation tools to localize itself. The robot is equipped with a sonar, a gyrometer and accelerometers. The robot is assumed to know the exact shape of the environment (here a swimming pool). Many outliers occur in the data provided by the sonar. An interval method is then used to obtain a dynamic fusion of all data. The associated method is fast (since it uses constraint propagation) and extremely robust with respect to outliers. To the best of our knowledge, it is the first time a robot embeds interval method to control itself. In this talk, the principle of the localization method will be explained, the construction of the robot will be shown and some videos will be displayed in order to illustrate the good behaviour of the robot.

This robot has been built at ENSIETA School for the SAUC’E competition (Student Autonomous Underwater Challenge European) that will take place in Brest July 7th to 10th 2008.

2)      Jean-Pierre MERLET, INRIA Sophia Antipolis.

Title: Influence of uncertainties on ultrasonic localisation systems. Slides.

Abstract: Ultrasonic emitter/receivers are frequently used in robotics to locate objects. The basic principle is to have an emitter that sends an ultrasonic wave and several receivers that receive the echo of the sound wave. The time difference of arrival (TDOA) of the signal between two receivers is then used to estimate the difference of distances between the object and the receivers. Having at least 3 receivers usually allows to determine the location of the object. However errors on the sound velocty, frequency of the sound wave, respective location of the

receivers and measurements errors on the TDOA, influence the result of the localisation. In a first part we will illustrate the influence of these  parameters while in the second part we will show that interval analysis allows one to determine the possible locations of the receivers to ensure that localisation error is less than a given threshold over a given region. These locations are provided as a region, thereby allowing to determine the possible tolerance on the receiver placement..

3)      Emmanuel Bénazéra, Louise Trave-Massuyes,, LASS, Toulouse

Title: Set-Theoretic Estimation of Hybrid System Configurations. Slides.

Abstract: Hybrid systems serve as a powerful modelling paradigm for representing complex continuous controlled systems that exhibit discrete switches in their dynamics. The system and the models of the system are non deterministic due to operation in uncertain environment. Bayesian belief update approaches to stochastic hybrid system state estimation face a blow up in the number of state estimates. Therefore most popular techniques try to maintain an approximation of the true belief state either by sampling or by maintaining a limited number of trajectories. It appears these limitations can be avoided by using bounded intervals to represent the state uncertainty. As a consequence, the true system state can be captured by a finite number of hybrid configurations. A set of dedicated algorithms is detailed that can compute these configurations efficiently. Results are presented on two systems of the hybrid system literature.

4)      Nacim Ramdani, INRIA Sophia-Antipolis Mediterranee and LIRMM UMR 5506, CNRS UM2 Montpellier.

Title: Reachability of uncertain nonlinear systems using a nonlinear hybridization. Slides.

Abstract: we investigate nonlinear reachability computation in presence of model uncertainty, via guaranteed set integration. We show how this can be done by using the classical Muller's existence theorem. The core idea developed is to no longer deal with whole sets but to derive instead two nonlinear dynamical systems which involve no model uncertainty and which bracket in a guaranteed way the space reachable by the original uncertain system. We give a rule for building the bracketing systems. In the general case, the bracketing systems obtained are only piecewise Ck-continuously differential nonlinear systems and hence can naturally be modeled with hybrid automata. We show how to derive the hybrid model and how to address mode switching. An example is given with a biological process

5)      Farah Mourad, Fahed Abdallah, Hichem Snoussi, Cédric Richard, UTC, LM2S, UTT.

Title: Guaranteed boxed localization in MANETs by interval analysis and constraints propagation techniques. Slides.

Abstract: In this contribution, we propose an original algorithm for self-localization in mobile ad-hoc networks. The proposed technique, based on interval analysis, is suited to the limited computational and memory resources of mobile nodes. The incertitude about the estimated position of each node is propagated in an interval form. The propagation is based on a state space model and formulated by a constraints satisfaction problem. Observations errors as well as anchor nodes imperfections are taken into account in a simple and computational-consistent way.  A simple Waltz algorithm is then applied in order to contract the solution, yielding a guaranteed and robust online estimation of the mobile node's position. Simulation results on mobile node group  trajectories corroborate the efficiency of the proposed technique and show that it compares favorably  to particle filtering methods.

6)      Luc Jaulin and Gilles Chabert, ENSIETA.

Title: Resolution of nonlinear interval problems using symbolic interval arithmetic. Slides.

Abstract: An interval-valued problem is a problem where the unknown variables take interval values. Such a problem can be defined by interval constraints, such as "the interval X=[a,b] is a subset of X*X". Interval valued problems often appear when we want to analyze a priori the behaviour of an interval solver. To solve interval-valued problems, we propose to transform the constraints on intervals into constraints on their bounds. For instance, the previous interval constraint (X is a subset of X*X) can be transformed into the following bound constraint "a>min(a*a,a*b,b*b) and b<max(a*a,a*b,b*b)". Classical interval solvers can then be used to solve the resulting bound constraints. The procedure which transforms interval constraints into equivalent bound constraints can be facilitated by using symbolic interval arithmetic. While classical intervals can be defined as a pair of two real numbers, symbolic intervals can be defined as a pair of two symbolic expressions. An arithmetic similar to classical interval arithmetic can be defined for symbolic intervals. The approach will be motivated by several examples related to estimation and experimental design.

7)      Gilles Chabert and Luc Jaulin, DTN, ENSIETA.

Title: : Interval and Boolean constraint propagation for simultaneous localization and map building. Slides.

Abstract. The SLAM (Simultaneous localization and map building) problem asks if it is possible for an autonomous robot to move in an unknown environment and build a map of this environment while simultaneously using this map to compute its location.

During the talk, it will be shown that, when the landmarks are identical and when outliers occur, the general SLAM problem can be cast into a constraint propagation problem (CSP) where Boolean and numerical variables occur. The corresponding CSP is nonlinear and classical nonlinear methods have some difficulties to deal with this type of problems in a reliable way.

A basic interval constraint propagation algorithm to solve the CSP will be proposed.

The efficiency of the approach will be illustrated on a two-hour experiment where an actual underwater robot is involved. This four-meter long robot build by the GESMA (Groupe d’étude sous-marine de l’Atlantique) is equipped with many sensors (such as sonars, Loch-Doppler, gyrometers, …) which provide the data.

8)      Nicolas Delanoue, LISA, Angers.

Title: : Attraction domain of a nonlinear system using interval analysis. Slides.

Abstract : Consider a given dynamical system, described by \dot{x} = f (x) (where f is a nonlinear function) and [x0] a subset of R^n. We present an algorithm, based on interval analysis, able to show that there exists a unique equilibrium state x^\infty \in [x0] which is asymptotically stable. The effective method also provides a set [x] (subset of [x0 ]) which is included

in the attraction domain of x^\infty. In a second time, the flow of the ordinary differential equation \dot{x} = f (x) is discretized, inclusion methods are combined with graph theory to compute a set which is included in the attraction domain of x^\infty.

9)      Olivier STRAUSS, LIRMM UMR CNRS Univ. Montpellier.

Title: Imprecise estimation in signal processing. Slides.

Abstract: A wide range of digital analysis and signal processing procedures inherently rely on methods for reconstructing a continuous underlying signal from a set of sampled corrupted values. These values are usually uniformly sampled, since the measures come from systematic observations. Kernels are essential tools in this context, since they are used in reconstruction, impulse response modeling, resampling, interpolation, linear or non-linear transformations, stochastic or band-pass filtering, etc. In digital signal processing, kernels are mainly used to derive discrete algorithms from a continuous representation. Within most applications, a kernel can be seen as a weighted neighborhood ensuring a smooth interplay between continuous and discrete domains. They can be visualized as bumps that can be shifted to any location of the signal domain, so as to absorb or spread the information contained in the signal. They are often bounded, monomodal and symmetric. Digital signal derivation is a typical example of such an application. The classical finite differences method usually fails to perform the estimation of the derivative of the signal, especially with a noisy signal. The kernel-based method consists of computing the sampled derivative of an estimation of the continuous signal. This estimation is obtained by convolving the original discrete signal with a continuous kernel, chosen to lower the impact of both acquisition noise and quantization effect. The implementation of such a method simply consists

of convolving the original sampled signal with the derivative of the chosen kernel, which is also a kernel. Most of the kernels used in signal processing are summative kernels, or linear combinations of summative kernels. A summative kernel is a positive function, the integral of which equals 1. A summative kernel has a relevant meaning in the scope of uncertainty theories since it induces a probability measure. Therefore, when signal processing involving a convolution can be considered as a linear combination of expectations based on the probability measure induced by the involved summative kernels. When the proper kernel to be used for a particular application cannot precisely specified, one can be interested in the possibility of replacing a single kernel by the family of possibly adequate kernels. A maxitive kernel is another way for defining a weighted neighborhood. It is a [0,1] valued function whose maximum value attains 1. A maxitive kernel has also a relevant meaning in the scope of uncertainty theories since it induces a possibility measure. Moreover, since a possibility measure defines a convex set of probability measures, a maxitive kernel defines a convex set of summative kernels. Therefore, convoluting the signal to be processed by all the summative kernels belonging to convex

set will lead to an interval-valued response. In this talk, we propose to extend the conventional expectation operator to the different non-additive confidence measures induced by using

maxitive kernels instead of summative kernels. This shift from summative- to maxitive kernel aims at accounting for an ill-knowledge on the proper kernel to be used.

10)  Ignacio Araya, Bertrand Neveu, Gilles Trombettoni.

Title: Exploiting Common Subexpressions in Numerical CSPs. Slides.

Abstract: It is acknowledged that the symbolic form of the equations is crucial for interval-based solving techniques to efficiently handle systems
of (in)equations over the reals. However, only a few automatic transformations of the system have been proposed so far.  Common Subexpression
Elimination (CSE) is the main feature in code optimization. In interval analysis, Vu, Schichl, Sam-Haroud, Neumaier exploit common subexpressions
by transforming the (in)equation system into a unique directed acyclic graph. They claim that the impact of common subexpressions on the gain in
CPU time would be only due to a reduction in the number of operations. This paper brings two main contributions.  First, due to properties related
to interval arithmetics, we prove theoretically and experimentally that exploiting certain common subexpressions of equations not only reduces the
number of operations, but also brings additional filtering/contraction during propagation. Second, contrarily to existing approaches and based on a
better exploitation of n-ary plus and times operators, we propose a new algorithm I-CSE that identifies and exploits ALL the useful'' common
subexpressions. We show on a sample of benchmarks that I-CSE detects more useful common subexpressions than traditional approaches and leads
generally to significant gains in performance (of sometimes several orders of magnitude).

11)  Gilles Trombettoni, Gilles Chabert.

Title: Constructive Interval Disjunction: past, present, and future. Slides.

Abstract: We present two new filtering/contraction operators for numerical CSPs (systems with constraints over the reals) based on constructive disjunction,
as well as a new splitting heuristic.  The fist operator (CID} is a generic algorithm enforcing constructive disjunction with intervals.  The second
one (3BCID) is a hybrid algorithm mixing constructive disjunction and shaving, another technique already used with numerical CSPs through
the algorithm 3B. Finally, the splitting strategy learns from the CID filtering step the next variable to be split, with no overhead. Experiments
have been conducted with 20 benchmarks. On several benchmarks, CID and 3BCID produce a gain in performance of orders of magnitude
over a standard strategy. CID compares advantageously to the 3B operator while being simpler to implement. The last part of the talk describes
the most recent improvements and ideas to provide an adaptive version of CID.


12)  Ned Nedialkov, Dept. of Computing and Software, McMaster University, Canada.

Title: Interval Tools for ODEs and DAEs. Slides.

Abstract: An interval method for initial value problems (IVPs) in ordinary differential equations (ODEs) has two important advantages over

approximate ODE methods: when it computes a solution to an ODE problem, it (1) proves that a unique solution exists and (2) produces rigorous

bounds that are guaranteed to contain it. Such bounds can be used to ensure that this solution satisfies a condition in a safety-critical calculation,

to help prove a theoretical result, or simply to verify the accuracy and reliability of the results produced by an approximate ODE solver.

We overview interval methods and software for IVP ODEs, discuss applications of these methods, and present the author's interval ODE

solver VNODE-LP.

Computing rigorous bounds in IVPs for differential-algebraic equations (DAEs) is a substantially more challenging task than in ODEs.

A promising approach is Pryce's structural analysis combined with Taylor series methods. We outline this approach and discuss recent developments.

13)  Guillaume Verger, LIRMM, Montpellier.

Title: CSPs and Quantified CSPs. Slides.

Abstract: Constraint satisfaction has been studied from the seventies (Montanary

1974, Waltz 1975). Constraint programming has been applied in numerous domains such as

computer graphics, natural language, optimization problems, molecular biology etc...

I will present a state of the art of techniques used in Constraint programming, in the case of

finite discrete domains. These techniques concern constraint propagation algorithms

(Forward Checking,Arc-Consistency, Path Arc-Consistency, Singleton Arc-Consistency...) and

search techniques (Backtrack, Back-Jumping, Variable and Value Ordering

heuristics...). Since 1995, interest in the Quantified Constraint Satisfaction Problem

is growning. The QCSP can be seen as an extension of CSP in which variables are either

existentially or universally quantified. I will present the different techniques used to solve such

problems, some of them are adapted from techniques used in quantified Boolean formulas (QBF),

the quantified extension of SAT.

14)  Jamila Sam-Haroud, Artificial Intelligence Laboratory, Lausanne (Switzerland)

Title: Enhancing numerical constraint propagation using multiple inclusion representations. Slides.

Abstract:  Building tight and conservative enclosures of the solution set is of

crucial importance in the design of  efficient complete solvers for

numerical constraint satisfaction problems (NCSP).

The talk will present an generic algorithm  enabling the cooperative

use, during constraint propagation,  of  multiple enclosure techniques.

This allows bringing into the constraint propagation framework the

strength of techniques coming from different areas such as interval arithmetic, affine

arithmetic or mathematical programming. Some experiments illustrating

the potential of the approach will be reported.

15)  Sébastien LENGAGNE, Nacim RAMDANI, Philippe FRAISSE (LIRMM / INRIA)

Title: Application of Interval Analysis : safe path planning. Slides.

Abstract: In humanoid robotics field, path planning is used to compute off-line,

a database of complex motions. Path planning problem is to find the

motion that satisfies a set of equality and inequality constraints and

minimizes a cost function. Some inequality constraints must be validated

over the whole motion duration. Nevertheless optimization algorithms

deal with a finite number of constraints. That is why, the

discretization of the inequality constraints is necessary.

Usual path planning methods use a time-point discretization, that

computes the values of the constraints over a time-grid. This will produce

a solution that satisfies the constraints for the considered time-point.

However no information is given about the constraint validity elsewhere.

So, we present the safe path planning method that uses classical

optimization algorithms, but replaces the time-point discretization of

the constraint with a time-interval discretization.

Experimental results concerning the 2-D model with 6 degrees of freedom

of the HOAP-3 humanoid robot prove that the classical path planning method

allows some constraint violations, whereas our safe path planning method

generates motions which ensure the balance and the integrity of the robot.

16)  Olivier Bouissou, CEA Saclay - DRT/DTSI/SOL/MeASI Gif-sur-Yvette

Title: Using guaranteed integration of ODEs for the verification of embedded software. Slides.

Abstract: In this talk, I will give an insight of why we must take into account

the physical environment of embedded programs when we deal with

their verification. This implies the analysis of a wider system that

contains two parts : a discrete program and a continuous

environment. If the analysis of the discrete part is well studied, the

verification of the continuous part and of the interactions between

both is more recent. In this talk, I will focus on the analysis of

the continuous subsystem using guaranteed integration techniques,

i.e. tools that compute verified bounds on the solution of ODEs using

interval methods. In particular, I will present a new algorithm for

this that is based on a classical Runge-Kutta order 5 numerical method

for which exact error bounds are computed. I will also present

experimental results that compare this approach with the tool VNODE.

Title: Computing the range of real eigenvalues of an interval matrix. Slides.

Abstract: We propose an algorithm for computing the set of eigenvalues of an

interval matrix. It is based on the branch-and-prune method and exhibits

diverse interval analysis techniques including regularity tests, among

others. Particularly, the Jansson-Rohn algorithm turned out to be very

efficient recognizing outer boxes, and its modification was developed to

recognize inner boxes as well. Our approach enables not only to compute

the range of eigenvalues with a given accuracy, but in the most of cases

we are able to find out in reasonable time the exact boundary points.

Finally, we demonstrate efficiency of the proposed method on a series of

numerical experiments.

18)  Maëlenn AUFRAY (ENSIACET - Toulouse), Adrien BROCHIER and Wulff POSSART

Title:  S.I.V.I.A. Applied to Dielectric Spectroscopy: a Guaranteed Parameter Estimation

Using Interval Analysis. Slides.

Abstract: Dielectric spectra of materials are often difficult to analyze since

the common software algorithms and line shape functions do not always

provide unambiguous data for the fitted parameters. In this

presentation, a software, based on a global optimization algorithm which

uses interval analysis, is presented. Taking into account the

experimental error of each data point in the measured dielectric

spectrum, the sofware provides a confidence interval for every parameter

of the dielectric function implemented in the software. This is

demonstrated for an epoxy monomer with a sum of Debye relaxators as

dielectric line shape function. This software is also able to deliver

and guarantee the number of relaxation processes even if they are in

part masked by other phenomena like conductivity or electrode

polarization.

19)  Philippe Langlois (DALI, Univ. Perpignan) and Nicolas Louvet (Arénaire, INRIA and ENS Lyon)

Title: Accurate results with compensated algorithms and validated error bounds in floating point computation: principles and applications. Slides.

Abstract: In this talk we focus the reliability of floating point computation
where rounding errors worsen the significance of computed results
(data error is not here considered). Compensated algorithms allow us
to compute very accurate results of some classic algorithms (summation,
inner product, polynomial evaluation, triangular linear solution)
within a very realistic running-time overcost. It is classic to
also compute a dynamic bound of the remaining error of
these accurate solutions. This a posteriori bound is validated
(whereas computed in floating point arithmetic), its overcost is
reasonable and the bound can be thin enough to decide, for example,
whether a computed result is a faithful rounding of the exact value.
We present some of these points being motivate by the following
question we ask to the interval arithmetic expert audience: when
these accurate, validated and fast algorithms can be an alternative to
interval arithmetic?


20)  Jorge Florez, Mateu Sbert, Josep Vehí (Mice, Girona, spain)

Title: Improving ray tracing of implicit surfaces using interval arithmetic. Slides.

Abstract: Ray tracing of implicit surfaces suffers of reliability problems when

surfaces having thin parts are rendered: such features are missed and not

appear in the final image. Those problems are caused for the truncation

performed in the floating-point representation in the computers.

Many authors have used Interval Arithmetic in the intersection test to

perform a guaranteed ray tracing. However, there are still two open

problems in the ray tracing of implicit surfaces based on Interval

Arithmetic: a) Ray tracing is slow, but Interval Arithmetic is slow too

which reduces the efficiency in all the process. b) Interval Arithmetic

has been applied to solve point sampling problems in the intersection

tests. But the application of Interval Arithmetic to solve problems

related with point sampling in the distribution of the rays inside the

pixel, have not been studied. In this work, some algorithms to deal with

those problems are presented.

21)  Nathalie Revol (INRIA, Univ. Lyon, LIP, France)

Title: Survey of Proposals for the Standardization of Interval Arithmetic. Slides.

Abstract:  The context of this work is the recent approval by IEEE of a committee

on the standardization of interval arithmetic (bearing the number P1788).

A first task of this working group will be to review existing proposals

and points of view on interval arithmetic.

In this talk, the need for a total and closed system is motivated. The

approach adopted here is not to give a commented list of proposals.

Instead, different points of view will be presented. A first convenient

distinction consists in considering algorithms for constraint programming:

two operating modes are adopted, the "forward" and the "backward" modes,

and they give rise to two different families of definitions.

Another distinction between the existing definitions of interval arithmetic

concerns the considered underlying set: either the reals, or extended reals

(ie. reals and the infinities).

Then, links with floating-point arithmetic, for implementation issues,

will be discussed. Finally, a tentative list of operators will be given.

FAQ

1)      How could I register the MEA group?
If you understand French, you can enter for free to MEA. You will receive less than one email a week related to the next MEA meetings, information about some conference of interest…

Come back to http://www.ensta-bretagne.fr/jaulin/