October 23-27, 2006
SAGE — software for algebra and geometry experimentationOctober 23, 2006 10:50 am - 11:40 am
The goal of SAGE is to create an optimal software environment for research
and experimentation in algebra, geometry, number theory, cryptography, and
related areas. The speaker started SAGE in 2005 by combining together the
very best of existing free software (e.g., Singular, PARI, GAP, Macaulay2,
Maxima, gfan, etc), creating interfaces to non-free software (e.g., MAGMA,
Maple, Mathematica), and beginning to fill in the gaps with new code. Now
many developers have joined him in working on filling these gaps and
making SAGE a polished and efficient piece of software. This talk will
demo SAGE, and explain how it works.
Software installation/poster session/reception
October 23, 2006 4:00 pm - 6:00 pm
Software developers will offer their software for installation
on the laptops of the participants at various booths.
Tutorial/demonstration sessionOctober 25, 2006 4:00 pm - 7:00 pm
Tutorial/demonstration sessionOctober 26, 2006 4:00 pm - 7:00 pm
Introduction to Bertini: a software package for numerical algebraic geometry
October 27, 2006 1:40 pm - 2:30 pm
Bertini is a new software package for computation in the field of numerical
algebraic geometry. Among other things, Bertini is capable of producing all
complex isolated solutions of a given polynomial as well as points on each
positive-dimensional irreducible component. Bertini makes use of adaptive
multiprecision, singular endgames, straight-line programs, and several other
useful tools. This talk will cover some of the capabilities of Bertini as well
as some of the implementation details.
CoCoALib, a C++ library for computations in commutative algebraOctober 25, 2006 9:30 am - 10:20 am
For almost 20 years the CoCoA project has been conducting research into
computational commutative algebra, developing new algorithms and offering
implementations in the interactive program "CoCoA." Recently we took the
decision to rebuild the software from scratch with the specific aim of
making excellent implementations available to all researchers. The
implementations will be accessible in three distinct ways:
as a standalone interactive system, as a networked service (via an
OpenMath-like communications channel), as a C++ library, called
CoCoALib (free and open in the sense of the GPL).
CoCoALib, being the core of the project, is also its most evolved
part, and is the part that we shall look at most closely.
Maple 11 previewOctober 27, 2006 3:00 pm - 3:50 pm
A preview to some of the new features
of the next version of Maple will be given, in particular,
to the improvements in the area of algebraic geometry and
polynomial system solving resulting from integrating
Jean-Charles Faugere's package FGb and Fabrice Rouillier's package RS.
Macaulay 2, a software system for algebraic geometry
October 23, 2006 9:30 am - 10:20 am
Macaulay 2 supports research in algebraic geometry and commutative
algebra. Its versatile framework, based on Buchberger's algorithm for
computing Groebner bases, combined with an object-oriented interpreted language
supporting the introduction of new high-level mathematical types, allows
advanced algorithms to be coded. I'll demonstrate it, and I will describe
recent improvements aimed to support third-party development of code, including
the package system, the debugger, and the documentation processor.
4ti2 -- A software package for algebraic, geometric and combinatorial problems
on linear spacesOctober 25, 2006 10:50 am - 11:40 am
Hilbert bases, Graver bases and toric Gröbner bases are at the heart of
many problems arising in mathematics or in practice. In this talk we
present the main functionality and the algorithmic theory behind the
software package 4ti2. Furthermore, we present applications (theoretical
and computational) from various mathematical fields such as toric
algebra, integer programming or statistics.
Within this workshop, this talk is accompanied by a tutorial on 4ti2 by
Algebra & algorithms for differential elimination & completionOctober 24, 2006 9:30 am - 10:20 am
Differential algebra provides an algebraic viewpoint on nonlinear
The motivating questions for this talk are:
- How do we define the general solution of a nonlinear equations
- What are the conditions for a differential system to have a solution
- How do we measure the "degrees of freedom" for the solution set of a
Theory and algorithms for those are extensions of commutative algebra
(prime ideal decomposition, Hilbert polynomials) and Groebner bases
The library diffalg in Maple supports this introduction to constructive
It has been developed by F. Boulier (1996) and the speaker afterwards.
A recent extension of differential algebra to non-commutative derivations,
and its implementation in diffalg, allow to treat systems bearing on
Computing tropical varieties in GfanOctober 26, 2006 3:00 pm - 3:50 pm
The tropical variety of a polynomial ideal I in n variables over Q is a
polyhedral complex in n-dimensional space. We may consider it as a
subfan of the Groebner fan of I. The polyhedral cones in the Groebner
fan can be computed using Groebner bases and by applying "Groebner walk"
techniques. This gives one method for computing the tropical variety of
I. We show how the method can be refined by applying a connectivity
result for tropical varieties of prime ideals and an algorithm for
constructing tropical bases of curves. The presented algorithms have
been implemented in the software package Gfan.
This is joint work with
T. Bogart, K. Fukuda, D. Speyer, B. Sturmfels and R. Thomas.
Parallel implementation of the polyhedral homotopy method for
polynomial systemsOctober 25, 2006 1:40 pm - 2:30 pm
The polyhedral homotopy method is known to be a powerful numerical method for
approximating all isolated solutions of a system of polynomial equations.
We discuss a parallel implementation of the polyhedral homotopy method,
a dynamic enumeration of all fine mixed cells which is used in constructing a family of
polyhedral homotopy functions and extensions of the Hornor Scheme to multivariate
polynomials for efficient evaluation of a system of polynomials and their partial
derivatives in the polyhedral homotopy method.
New recombination techniques for polynomial factorization
algorithms based on Hensel lifting
October 26, 2006 10:50 am - 11:40 am
Multivariate polynomial factorization algorithms are necessary
ingredients to several tasks in computational algebraic geometry such
as prime and primary decompositions. They are also extremely useful in
many places where they are not necessary but where they lead to major
speedups by splitting problems into several smaller ones.
In this talk I will present recent results concerning the
factorization reductions from several to two variables via Bertini's
theorem, and then from two to one variable. These reductions are based
on the very classical Hensel lifting strategy and new fast
recombination devices. Over a prime coefficient field, I will show
that the irreducible factorization of a bivariate polynomial of
bidegree (m,n) roughly reduces to the factorization of a univariate
polynomial of degree n, a Hensel lifting to precision m+1, and O~( m
n^2 ) arithmetic operations to recombine the lifted factors.
Finally we will report on practical performances of the new
algorithms, and on comparisons with other software.
D-modules for Macaulay 2October 26, 2006 9:30 am - 10:20 am
The package D-modules for Macaulay 2 implements the majority of
the now classical algorithms in the computational D-module theory. Based
on the ability of Macaulay 2 engine to compute Gröbner bases in
the Weyl algebra, the package provides, in particular, tools to work with
holonomic D-modules such as the algorithms for b-functions, localized
modules, restriction, etc. Amongst the applications there are computation
of the local cohomology modules, polynomial and rational solutions, and
(Joint work with Harry Tsai)
SYNAPS, a library for symbolic-numeric computationOctober 25, 2006 3:00 pm - 3:50 pm
SYNAPS (SYmbolic Numeric APplications) is a C++ library devoted to symbolic
and numeric computations. It provides data-structures for the manipulation of
basic algebraic objects, such as vectors, matrices (dense, sparse,
structured), univariate and multivariate polynomials. It contains solvers
for univariate and multivariate polynomials, including generalized normal form or subdivision solvers, tools for the manipulatiion of algebraic numbers, for the construction of resultants, ... In this talk, we will
describe shortly its design, its main features and functionalities, show some applications in computational geometry for algebraic curves and surfaces and explain how it can be embbeded in an interpreter such as mathemagix or a modeling tool such as axel.
Sums of squares of polynomials and SOSTOOLSOctober 26, 2006 1:40 pm - 2:30 pm
Sum of squares (SOS) programs are a particular class of convex optimization
problems, that combine in a very appealing way notions from algebraic and
computation (in particular, semidefinite programming). They are based on the
squares decomposition for multivariate polynomials, and have found many
applications, mainly through semidefinite relaxations of polynomial
In this talk we will quickly review the basic SOS framework, focusing on the
(developed in collaboration with Stephen Prajna, Antonis Papachristodoulou,
and Pete Seiler).
The ideas and algorithms will be motivated and illustrated via interesting
including Systems and Control, quantum information, and game theory.
Application of numerical algebraic geometry to partial differential equationsOctober 27, 2006 10:50 am - 11:40 am
In Numerical Algebraic Geometry, solution components of polynomial systems
are characterized by witness points. Such nice points are computed efficiently
by continuation methods.
In this talk, which is joint
work with Wenyuan Wu and Jan Verschelde, I will outline progress on extending
methods to Partial Differential Equations.
I will describe the jet geometric picture of PDE in their jet space, to which
the methods of Numerical Algebraic Geometry are applied.
In particular witness points in jet geometry are cut out by the intersection of
linear spaces with submanifolds in jet space (there will be nice pictures).
Applications to constrained mechanical
systems; overdetermined systems for symmetries of differential equations will
On computing using FGb/RS softwareOctober 24, 2006 3:00 pm - 3:50 pm
The goal of this lecture is to show how to use efficiently FGb and RS
software for solving various kinds of polynomial systems.
Such software can nowadays be used as a "black box" in many cases (J.
Gehrard's presentation) for computing/studying real roots of polynomial
systems, but the objective here is to show how to use them in extreme
We will introduce, step by step, several tricks and advanced options,
including the related mathematical background, and show how to solve some
examples presented in the tutorial which took place at IMA in September
Gauss-Manin systems for isolated singularities in
singularOctober 27, 2006 9:30 am - 10:20 am
The Gauss-Manin system of a function is a direct image in the category
of D-modules. For the case of isolated singularities there are two
Singular libraries to compute it: gmssing.lib for (local) isolated
hypersurface singularities, gmspoly.lib for (global) tame polynomial
In both cases the Gauss-Manin system carries a rich structure: an
embedded (Brieskorn) lattice with an induced differential structure, a
(Kashiwara-Malgrange) V-filtration, a monodromy operation defining a
weight filtration, and a mixed Hodge structure. Resulting invariants
like the spectral pairs belong to the finest known invariants of
isolated hypersurface singularities.
In the talk we focus on the case of tame polynomials to discuss the
above structures and the main ideas behind the algorithmic methods to
Towards a black-box solver for finite games: The Gambit systemOctober 24, 2006 10:50 am - 11:40 am
An intriguing fact about the celebrated Nash equilibrium concept in
games is that it can be expressed mathematically in a variety of ways:
as a fixed point, a solution to a complementarity program, a (global)
minimizer, or a solution to a system of polynomial equations and
As a result, there are general-purpose algorithms to compute Nash
on finite games. Many of these algorithms relate specifically to
well-studied areas of numerical programming, including linear
homotopy path-following, and solving polynomial systems.
Game theory appears in a broad range of disciplines, and is taught
at the undergraduate level. Students and practitioners alike need a
to specify and analyze games without needing to worry about the
details of finding equilibria. The Gambit system is an Open Source
set of software tools for specifying and analyzing games, with the goal
of packaging quality implementations of numerical codes from experts in
a convenient form for general use. This talk will introduce the Gambit
system and outline current implementations of algorithms for computing
equilibrium, with special emphasis on the role of a method for computing
all equilibria which uses the PHCPACK system as a backend.
PHCpack: a software platform for numerical algebraic geometryOctober 24, 2006 1:40 pm - 2:30 pm
PHCpack is a software package for Polynomial Homotopy Continuation
to numerically solve polynomial systems. In the past five years,
the package has been extended with tools to compute a numerical
irreducible decomposition. Other features include deflation for
isolated singularities and an equation-by-equation solver.
Most recently, PHCpack has been extended with a translation of the
program MixedVol (by Tangan Gao, Tien-Yien Li, Mengnien Wu) to compute
mixed volumes and define polyhedral homotopies more efficiently.
What should a software package for numerical algebraic geometry be?October 23, 2006 1:40 pm - 2:30 pm
It has been approximately twenty years since the initial germination of
numerical continuation as an approach to finding solution points of systems
of polynomial equations and ten years since its flowering into numerical
algebraic geometry, which facilitates description of solution sets of any
dimension and operations on these, such as intersection and fiber products.
We will attempt to step back from the torrent of recent developments to
sketch out the big picture of what a general software package for numerical
algebraic geometry should be: what core functions are necessary, how these
can be organized into higher level algorithms, and how this might be wedded
to user interfaces that allow access by non-experts while still being open
to new advances in algorithms.
APAtools: A Maple/Matlab toolbox for approximate polynomial
algebraOctober 23, 2006 3:00 pm - 3:50 pm
This talk presents a Maple/Matlab toolbox for basic polynomial
with exact or approximate data. The toolbox includes software for
the approximate GCD, approximate factorization, dual basis and
identification, as well as numerical elimination in solving polynomial
systems. We shall present the underlying theory of approximate
algebra, the main approach of the algorithms, and computational