MACIS 2007 -- Mathematical Aspects in Computer and Information Sciences

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]