MACIS 2007

Mathematical Aspects of Computer and Information Sciences 2007, Paris, France, December 5-7, 2007


[Home] [Organization] [Submission] [Program] [Venue] [Accomodation] [Registration]

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 Geometry


The 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 rationals


In 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 Analysis


Geometric 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
  • Representing and Solving Finite-Domain Constraint Problems Using Systems of Polynomials
    Chris Jefferson, Peter Jeavons, Martin Green and Marc van Dongen.
    [pdf]
  • Complexity Analysis of Random Massive Algebraic System
    Wei Wei, Binghui Guo and Zhiming Zheng.
    [pdf]