First presenter Co-presenter(s)
Name :  Guillaume Moroz * Name:   
E-mail: E-mail:  
Affiliation: Maplesoft Name:   
Department:   E-mail:    
City: Name:   
State/Province:   E-mail:    
Country: Canada Name:   
Talk
Number:
09-03  E-mail:    
Session: 9- Symbolic and Numeric Computation Schedule:
 
Room:
Saturday, 14:30
 
B-3432
Related website:  
Title of
presentation:
Chebyshev expansion for yet another paving algorithm
Abstract:

The problem of paving the solution of polynomial inequalities with rectangular boxes has many applications in real geometry: among the most important ones are volume computation of semi-algebraic sets, and uniform point sampling. Consider the inequality p>0, where p is a multivariate polynomial. The problem of box paving consists in approximating the set of solutions of p>0 with rectangular boxes. In the framework of spatial subdivision tree algorithms, the main issues are: 1. the design of a sufficient criterion to detect if p has no real zero in a given box 2. the design of heuristics to split a box when the criterion doesn't allow us to conclude Many approaches have been used to address these issues, including Taylor expansion, Bernstein expansion, adapted narrowing operators... On another hand, while the Chebyshev polynomials have very good properties for numerical approximations of functions, they have rarely been used in the context of multi-dimensional box paving. Indeed, we will show that the Chebyshev expansion has very nice properties for the problem of box paving, and we will present the results we obtained with a high-level implementation in maple.