28.01.2005

POSTDOC POSITION IN COMPUTER SCIENCE
ECOLE NORMALE SUPERIEURE, LYON FRANCE

   IMPLEMENTATION OF A VALIDATED INFINITE NORM

Other postdoc offers (cryptology, computer algebra) are available
and can be consulted at
http:// www.ens-lyon.fr/LIP/Arenaire/

KEYWORDS: infinite norm, elementary functions, interval arithmetic,
variable precision

SUPERVISORS: Jean-Michel Muller {Jean-Michel.Muller@ens-lyon.fr},
Nathalie Revol {Nathalie.Revol@ens-lyon.fr}

LOCATION: LIP + address + url

PREFERRED DURATION: 12 months

ARENAIRE PROJECT
Arenaire is a  project of 16  researchers which aims at  elaborating
and consolidating knowledge in the field of computer arithmetic.  We
contribute  to the improvement of   the available arithmetic, at the
hardware  level   as well as  at  the  software level, on computers,
processors,   dedicated or    embedded    chips, etc.   Reliability,
accuracy, and speed are major goals that drive our studies.  We also
take  into account other    constraints such as power   consumption,
certification  using formal   proof   techniques or  reliability  of
numerical software.  Target arithmetics  are fixed or floating point
format, interval arithmetic, finite  fields arithmetic  and multiple
precision.


SCIENTIFIC CONTEXT:
One of the research topics of Arenaire is the hardware or
software computation,
as efficiently as possible, of elementary
functions (sine, exponential, arc-tangent...).
The notion of efficiency is related to the target application
(computing time, memory, circuit area, accuracy).
The method consists in approximating the considered elementary
function f by a polynomial, on a fixed domain (usually a
small interval) and thus the polynomial of given degree that
best approximates f is sought; constraints may be added on
the coefficients of the polynomial.
For a candidate polynomial p, the quality of the approximation is
measured by the infinite norme of the error (f-p) on the considered
interval and our goal is to bound as accurately as possible this error
and to get validated bounds.

RESEARCH PROJECT:
Given a function f (given analytically and not by its value
at some points), a polynomial p and an interval I,
the candidate will have to design and implement an algorithm
that provides bounds (upper and lower bounds) of the infinite
norm of (f-p) on I.
- The result must be validated in order to guarantee the quality
of the approximation: this will be obtained via interval arithmetic.
- The computing precision is variable and not one of the usual
(single or double) computing precision: indeed, intermediate
computations of the error require more precision than the
target precision; furthermore, some applications concern digital
signal processing, where the precision differs from the usual
ones.

A possible extension concerns the determination of the best
polynomial of given degree, when constraints on the coefficients
are to be taken into account.

EXISTING WORK: the library MPFI implements interval arithmetic
with variable and arbitrary precision. Language: C/C++.


SKILLS: PhD in computer science or numerical analysis
- PhD in computer science + basic knowledge in NA
- PhD in numerical analysis + programming, preferrably in C/C++

CONTACT: contact ASAP Jean-Michel Muller
{Jean-Michel.Muller@ens-lyon.fr},
Nathalie Revol {Nathalie.Revol@ens-lyon.fr}