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 developers will offer their software for installation on the laptops of the participants at various booths.

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.

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.

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 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.

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 Peter Malkin.

Differential algebra provides an algebraic viewpoint on nonlinear differential systems. 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 differential system

Theory and algorithms for those are extensions of commutative algebra (prime ideal decomposition, Hilbert polynomials) and Groebner bases techniques.

The library diffalg in Maple supports this introduction to constructive differential algebra. 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 differential invariants.

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.

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.

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.

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 A-hypergeometric systems.

(Joint work with Harry Tsai)

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.

Sum of squares (SOS) programs are a particular class of convex optimization problems, that combine in a very appealing way notions from algebraic and numeric computation (in particular, semidefinite programming). They are based on the sum of squares decomposition for multivariate polynomials, and have found many interesting applications, mainly through semidefinite relaxations of polynomial optimization problems. In this talk we will quickly review the basic SOS framework, focusing on the SOSTOOLS toolbox (developed in collaboration with Stephen Prajna, Antonis Papachristodoulou, and Pete Seiler). The ideas and algorithms will be motivated and illustrated via interesting new applications, including Systems and Control, quantum information, and game theory.

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 these 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 random 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 also be described.

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 situations. 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 (http://www.ima.umn.edu/2006-2007/T9.15-16.06/).

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 functions. 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 compute them.

An intriguing fact about the celebrated Nash equilibrium concept in finite 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 inequalities. As a result, there are general-purpose algorithms to compute Nash equilibria on finite games. Many of these algorithms relate specifically to well-studied areas of numerical programming, including linear programming, homotopy path-following, and solving polynomial systems. Game theory appears in a broad range of disciplines, and is taught broadly at the undergraduate level. Students and practitioners alike need a tool to specify and analyze games without needing to worry about the computational details of finding equilibria. The Gambit system is an Open Source (GPL) 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 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.

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.

This talk presents a Maple/Matlab toolbox for basic polynomial computations with exact or approximate data. The toolbox includes software for computing the approximate GCD, approximate factorization, dual basis and multiplicity identification, as well as numerical elimination in solving polynomial systems. We shall present the underlying theory of approximate polynomial algebra, the main approach of the algorithms, and computational results.