## MACIS 2007Mathematical Aspects of Computer and Information Sciences 2007, Paris, France, December 5-7, 2007
## Invited speakers- Oliver Labs :
*Visualization Challenges in Real Algebraic Geometry* - Mark Van Hoeij :
*The complexity of factoring univariate polynomials over the rationals* - Chee Yap :
*Complete Adaptive Subdivision Algorithms and their Analysis*
## Schedule## Wednesday, December 5## 9h00- 9h30 : Welcome## 9h30-10h30 : Oliver Labs - Visualization Challenges in Real Algebraic GeometryThe visualization of algebraic implicitly given curves and surfaces is still an area of active research. There are already implementations of algorithms which produce correct results - in principal - for any inut. However, for applications one is often interested in real-time visualizations. And the implementations mentioned above are too slow for this, even for plane curves of moderate degree and coefficient size. There are several numerical algorithms which attempt to solve this problem, but these fail to produce correct results in many cases. In the talk, we discuss some of these issues and present a list of equations which may serve as a list of visualization challenges. ## 10h30-11h00 : Coffee Break## 11h00-12h00-
*The Minimum-Backlog Problem* Michael Bender, Sandor Fekete, Alexander Kröller, Vincenzo Liberatore, Joseph Mitchell, Valentin Polishchuk and Jukka Suomela. [pdf] -
*Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm* Claire Herrbach, Alain Denise and Serge Dulucq. [pdf]
## 12h00-13h30 : Lunch## 13h30-15h30-
*Parallel Implementation of a Subsystem-by-Subsystem Solver* Yun Guan and Jan Verschelde. [pdf] -
*On Computing Solutions of Linear Diophantine Equations with One Non-linear Parameter* Stefan Schuster and Armin Größlinger. [pdf] -
*Certified solutions of polynomials with uncertainties* David Daney, Jean Pierre Merlet and Odile Pourtallier. [pdf]
## 15h30-16h00 : Coffee Break## 16h00-17h30-
*Model Reduction of Chemical Reaction Systems using Elimination* François Boulier, Marc Lefranc, François Lemaire and Pierre-Emmanuel Morant. [pdf] -
*A New Maple Package for Solving Parametric Polynomial Systems* Songxin Liang, Jürgen Gerhard and David Jeffrey. [pdf] -
*Bezout matrices, Subresultants and Parameters* Gema M. Diaz-Toca, Laureano Gonzalez-Vega and Jounaidi Abdeljaoued. [pdf]
## Thursday, December 6## 9h00-10h00 : Mark Van Hoeij - The complexity of factoring univariate polynomials over the rationalsIn 2001 a new algorithm was introduced for factoring polynomials over the rationals. This algorithm was soon adopted by several computer algebra systems because of its good practical performance. However, it has thus far resisted attempts to prove a competitive complexity result for it. This talk will present a complexity result for this algorithm that matches its experimentally observed asymptotic behavior. ## 10h00-10h30 : Coffee Break## 10h30-12h00-
*Real solving polynomial systems of inequalities: the case of bounded sets of solutions* Mohab Safey El Din. [pdf] -
*Computing Critical Points by Continuation* Kathy Piret and Jan Verschelde. [pdf] -
*Optimizing the maximal real root of a polynomial by a special cylindrical algebraic decomposition* Masaaki Kanno, Silvia Gandy, Hirokazu Anai and Kazuhiro Yokoyama. [pdf]
## 12h00-13h30 : Lunch## 13h30-15h30-
*An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection* Isabel Bermejo, Ignacio Garcia-Marco and Juan Jose Salazar-Gonzalez. [pdf] -
*Computational aspects of Castelnuovo-Mumford regularity* Isabel Bermejo and Philippe Gimenez. [pdf] -
*Efficient Computation of Syzygies by Faugere's F5 algorithm* Gwenole Ars and Amir Hashemi. [pdf] -
*On the Invariant Properties of Hyperbolic Bivariate Third-Order Linear Partial Differential Operators* Ekaterina Shemyakova and Franz Winkler. [pdf]
## 15h30-16h00 : Coffee Break## 16h00-18h00-
*Interpolation of Shifted-Lacunary Polynomials* Mark Giesbrecht and Daniel Roche. [pdf] -
*Fast low rank approximations of matrices and tensors* Shmuel Friedland, Volker Mehrmann, Agnieszka Miedlar and Mechie Nkengla. [pdf] -
*Structured Condition Numbers of Sylvester Matrices* Bingyu Li, Zhuojun Liu and Lihong Zhi. [pdf] *Reductions in Computational Complexity using Clifford Algebras* Rene Schott, G. Stacey Staples [pdf]
## Evening: Social dinner## Friday, December 7## 9h00-10h00 : Chee Yap - Complete Adaptive Subdivision Algorithms and their AnalysisGeometric operations on curves and surfaces can be based on algebraic approaches (e.g., cylindrical algebraic decomposition, resultants) or on numerical/geometric approaches (e.g., subdivision methods, interval methods). We focus on the latter approaches as they are practical, easy to implement and has adaptive complexity. But such algorithms are rarely complete. We describe some current work in providing complete and adaptive algorithms for isotopic approximations of implicit curves. In particular, we describe a complete subdivision algorithm that can treat singular curves. This extends the recent work of Plantinga-Vegter. Then we address the complexity analysis of such algorithms. For this, we consider the one-dimensional analogue of approximating curves; the algorithm now amounts to real root isolation via evaluation-based subdivision. We provide a novel integral analysis of the complexity of the non-singular case of algorithm. ## 10h00-10h30 : Coffee Break## 10h30-12h00-
*Minimizing the symmetric difference distance in conic spline approximation* Sunayana Ghosh and Gert Vegter. [pdf] -
*Numerical Computation of Grobner Bases for Zero-dimensional Polynomial Ideals* Jean-Charles Faugère and Liang Ye. [pdf] -
*Certified 2-SAT with Modus Ponens* Serge Burckel. [pdf]
## 12h00-13h30 : Lunch## 13h30-15h30-
*Resultant and Random Multivariate Polynomials* Andre Galligo. [pdf] -
*Computing Roots of Polynomials using Bivariate Quadratic Clipping* Brian Moore and Bert Juettler. [pdf] -
*Triangulating the Real Projective Plane* Mridul Aanjaneya and Monique Teillaud. [pdf] -
*Dealing with the algebraic numbers arising when analyzing arrangements of quartic plane curves* Jorge Caravantes and Laureano Gonzalez-Vega. [pdf]
## 15h30-16h00 : Coffee Break## 16h00-17h00 |