Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
July 2 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
Machine-efficient polynomial approximants
- Speaker:
Nicolas Brisebarre (CNRS, LIP/Arenaire, ENS Lyon)
- Abstract:
Polynomial approximations are often used when implementing functions
on a computing system. In most cases, the polynomial that best approximates
(for a given distance and in a given interval) a function has coefficients
that are not exactly representable with a finite number of bits. And yet,
for practical applications, we have to consider polynomial approximations
which must satisfy some constraints like: if n denotes the maximal degree
of the polynomials under consideration, the i-th coefficient, for i = 0,
..., n, of the approximant must be a rational number with denominator
2^{m_i}, where m_i (i = 0, ..., n) is a sequence of rational integers
which is given or to be determined, according to the target application.
We present a heuristic method which uses the algorithmic of the
euclidean lattices, in particular the LLL algorithm, which makes it possible
to compute a very good (and sometimes the best) polynomial approximation
under this kind of constraints when the supremum norm is considered. Some
similar techniques also work for the L^2 norm.
[Works of Brisebarre, Chevillard, Hanrot, Muller, Tisserand and Torres]
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar