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.
Daniel R. Grayson (University of Illinois at Urbana-Champaign)
Macaulay 2, a software system for algebraic geometry
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.
PHCpack is a package for Polynomial Homotopy Continuation,
created to numerically solve systems of polynomial equations.
The executable program "phc" produced by PHCpack has several
options (the most popular one "-b" offers a blackbox solver) and
is menu driven. PHClab is a collection of scripts which call phc
from within a MATLAB or Octave session. It provides an interface
to the blackbox solver for finding isolated solutions. PHClab
also interfaces to the numerical irreducible decomposition,
giving access to the tools to represent, factor, and intersect
positive dimensional solution sets.
KNOPPIX/Math is a project to archive free mathematical software and
free mathematical documents and offer them on KNOPPIX.
It provides a desktop for mathematicians that can be
set up easily and quickly.
http://www.knoppix-math.org/
KNOPPIX/Math contains a lot of documents and packages
of mathematical software systems.
Once you run the live system, you can experience a wonderful world of
mathematical software systems without needing to make any installations
yourself.
Our system includes TeX, OpenOffice.org, Firefox, Emacs,
Kile, a KDE based GUI TeX editor, WhizzyTEX
and Active-DVI, a pair of WYSIWYG utilities for TeX documents,
and GNU TeXmacs, an office suite for TeX writing.
The DVD also includes many additional mathematical software systems
or libraries with documents, such as BLAS, Coq, Dynagraph,
GAP, Geomview, ginac, gmp, Gnuplot, Hyplane, jtem, Kali, Kan, KSEG, LAPACK,
Macaulay2, Maxima, NZMATH, Octave, OpenXM, PARI/GP, PHCpack,
polymake, Qhull, R, Risa/Asir, SAGE, Singular, SnapPea,
surf, surfex, Surface Evolver, synaps, Teruaki, XaoS, and Yorick, ...
Participants try the followings on their laptop in this tutorial.
1. Starting KNOPPIX/Math from DVD.
2. Saving data to a flash memory.
3. Installation of VMware(or Parallels)/knoppix/math.
4. Starting several mathematical software systems in the KNOPPIX/Math DVD.
Requirements for the laptop.
PC AT compatibles with a DVD drive or
Intel Mac.
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.
Anders Nedergaard Jensen (Aarhus University)
Computing tropical varieties in Gfan
We will demonstrate how the Gfan software can be used for computing Groebner
fans and tropical varieties of polynomial ideals. For Groebner fans we will see
how to do computations up to symmetry, draw the fans and do interactive Groebner
walks. Tropical computations are more involved. The following problems can be
handled by Gfan: intersecting tropical hypersurfaces, computing tropical bases
of curves and traversing tropical varieties of prime ideals. These will all be
demonstrated. We will discuss the most common problems one encounters with the
tropical part of the software: finding a starting cone, specifying symmetries,
selecting an appropriate output format and reading the output.
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.
New recombination techniques for polynomial factorization
algorithms based on Hensel lifting
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.
This Maple package provides a convenient interface to
the functions of PHCpack, a collection of numerical algorithms for
solving polynomial systems using polynomial homotopy continuation.
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)
Peter Nicholas Malkin (Université Catholique de Louvain)
4ti2 – Computing with lattices, cones, and subspaces
In this demonstration, we present the main functionality of the software
package 4ti2. Using 4ti2, we can compute Hilbert bases, Graver bases,
Groebner bases, and Markov bases of lattices, and the rays of a cone and
the circuits of a linear subspace. 4ti2 also has functions to optimize
integer linear programs.
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 this talk symbolic software will be described for overdetermined
systems of Partial Differential Equations.
The symbolic software is the rifsimp package which is available in distributed
Maple (since
Maple 7). It is tightly integrated and automatically called in many
applications
of Maple (e.g. its ODE and PDE solving routines). It was programmed by Allan
Wittkopf.Examples and applications of the use of this software will be given.
Some problems will also be used so that participants can try them during the
session.
Examples include: determination of initial data uniqueley determining solutions
of PDE;
determination of normal forms for PDE; determination of formal power series for
PDE;
determination of symmetries of PDE; integration of PDE.Strategies for tackling difficult problems and examples of their use.
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.
Fabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA)) http://fgbrs.lip6.fr/fabrice/
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.
I will give a short overview of the abilities of Singular,
with special emphasis on the
new features of Singular version 3.0.
2 Applications
The main part of the presentation will concentrate on the following tools for algebraic geometry:
2.1 Non-commutative Extension (G-algebras)
We demonstrate Singular's non-commutative extension
and show an application of it to compute the cohomology of twists of a sheaf
F on Pn associated to coker(M) for M being a graded module.s
It uses the Tate resolution over the exterior algebra.
The normalization will be computed for a reduced ring
R/I.
The result is a list of rings of the form
Ri /Ii.
The normalization of R/I is the product of the
factor rings of the rings in the list divided out by the ideals.
2.3 Primary Decomposition
There are two algorithms implemented in Singular
which provide primary decomposition:
primdecGTZ, based on Gianni/Trager/Zacharias (written by Gerhard Pfister) and primdecSY, based on Shimoyama/Yokoyama (written by Wolfram Decker and Hans Schoenemann).
We will demonstrate some examples of both.
2.4 Absolute Factorization And Absolute
Primary DecompositionThe absolute factorization of a multivariate polynomial
f with
coefficients in a field K of characteristic zero computes a suitable
field extension L (of K) and computes an absolutely irreducible factor of f in that extension.These routines are used to compute an absolute primary decomposition:
the routines return an list of he absolute prime components together
with its number of conjugates.
Robin Scott (University of Western Ontario)
Approximate Groebner bases - a backwards approach
The Grobner basis of a polynomial system is arguably the most
fundamental object of exact computational polynomial algebra, as it
answers many of the important questions of commutative algebra,
such as ideal membership and computation of the Hilbert
polynomial. It is traditionally computed using variants of
Buchberger's algorithm. Here, we take a backwards approach, and
show that a Grobner basis can be computed using the Hilbert polynomial
and another important basis from the jet theory of partial
differential equations: an involutive basis. This direction,
motivated by approximate systems, will allow us to avoid the
strict monomial orderings and ordered elimination (reduction)
strategies, at the heart of Buchberger-type methods, which are
usually numerically unstable.
For the the computation of exact bases for an ideal near to the
one from which we began, we make avid use of structured
(numerical) linear algebra. Additionally, we introduce
approximate leading terms and an approximate reduced row echelon
form. Neither of these require Gaussian elimination, unlike the exact case.
William Stein (University of Washington)
SAGE — software for algebra and geometry experimentation
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.
DEMiCs, software for dynamic enumeration of all mixed
cells
Enumeration of all mixed cells plays an essential role in the
polyhedral homotopy method; numerical method for solving polynomial systems.
Recently, we have developed a software, DEMiCs, which finds all mixed cells
using dynamic enumeration tree. It fairly surpasses the static enumeration in
computational time. This talk presents several techniques used in DEMiCs and
demonstrates its effectiveness.
Theodore L. Turocy (Texas A & M University)
The Gambit system for computing in finite games
Gambit is a collection of computer code for representing, building, and
manipulating finite games in extensive or strategic form. This session
will introduce the main components of Gambit. Gambit provides a
graphical user interface for manually creating, visualizing, and
analyzing
game trees and payoff tables. Several programs for computing Nash
equilibria are provided, including specialized ones for two-player and
constant-sum games. Gambit's modular structure makes it possible to
plug in other analytical programs; this feature will be illustrated with
a program to compute Nash equilibria with PHCpack as a computational
backend. The underlying representation library facilitates programming
new computational methods, as well as the automation of the construction
of large games or of families of games, which will be demonstrated with
some examples using the binding of the Gambit library to the scripting
language Python.
Theodore L. Turocy (Texas A & M University)
Towards a black-box solver for finite games: The Gambit system
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.
Homotopy methods to solve polynomial systems are well suited
for parallel computing because the solution
paths defined by the homotopy can be tracked independently. For
sparse polynomial systems, polyhedral
methods give efficient homotopy algorithms. The polyhedral
homotopy methods run in three stages: (1)
compute the mixed volume; (2) solve a random coefficient start
system; (3) track solution paths to solve
the target system. This paper is about how to parallelize the
second stage in PHCpack. We use a static
workload distribution algorithm and achieve a good speedup on
the cyclic n-roots benchmark systems.
Dynamic workload balancing leads to reduced wall times on large
polynomial systems which arise in mechanism design.
2000 Mathematics Subject Classification. Primary 65H10.
Secondary 14Q99, 68W30.Key words and phrases. Continuation methods, load balancing,
parallel computation, path following,
polynomial systems, polyhedral homotopies.This material is based upon work
supported by the National Science Foundation under
Grant No. 0105739 and Grant No. 0134611.
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.
We will demonstrate the use of algorithms for algebraic geometry implemented
in the computer algebra system Magma. These algorithms include the usual
commutative algebra functions which operate on schemes (defined by the
vanishing of polynomial equations in affine or projective space), including
efficient Groebner basis methods. Magma also contains many quite
specialized functions for working with familiar objects like plane curves.
Charles W. Wampler (General Motors Corporation)
Demonstration of HomLab
HomLab, a suite of Matlab routines, was created for learning about the
numerical solution of polynomial systems using homotopy continuation.The
package is distributed for use with the book Sommese and Wampler, The
Numerical Solution of Systems of Polynomials Arising in Engineering and
Science, World Scientific, 2005. In addition to the main software package,
the HomLab distribution includes codes to be used in working the exercises
at the end of each chapter.
While created for use with the book, HomLab is a general-purpose solver,
fast enough for moderately-sized systems. It provides the capability to
find all isolated solutions and to provide witness points on
positive-dimensional solution sets. Parameter continuation is available
for tracking nonsingular isolated solutions through a parameterized family
of polynomials, eliminating the overhead that otherwise would be imposed by
degenerate and positive-dimensional components.The software can be downloaded at
http://www.nd.edu/~cwample1/HomLab/main.html
The HomLab User's Manual appears as Appendix C of Sommese and Wampler.
Charles W. Wampler (General Motors Corporation)
What should a software package for numerical algebraic geometry be?
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.
Thomas Wolf (Brock University)
The package CRACK for solving large overdetermined systems
The poster gives an overview about recent algorithmic extensions, the
interface and visualization aids, the ability to trade speed for safety or
memory and other safety enhacing measures.
Starting as an automatic tools to integrate overdetermined
systems of linear PDEs, CRACK developed in recent years to a package
that is also well suited for polynomially non-linear systems.
Newer algorithms, like one for reducing the number of terms are
essentially different from the Groebner basis algorithm and thus a
useful addition which make the package especially suited for solving
large and heavily overdetermined systems. In the talk and demo an
overview shall be given, featuring, for example, the recent extension
that allows to dynamically generate the system to be solved during its
solution process. This became necessary for a computation in discrete
differential geometry where the polynomial consistency conditions for a
3-dimensional face formula involve 1017 terms.
In this poster both symbolic and numerical methods will be described for
overdetermined systems of Partial Differential Equations.
The symbolic method is the rifsimp package which is available in distributed
Maple. The symbolic-numeric methods are the combination of symbolic differential
elimination (using rifsimp) with numerical homotopy continuation (using phc)
together with Maple programs. Comparison of different methods and examples are
given.This is joint work with Greg Reid, Jan verschelde and Allan Wittkopf and is a
partner to the talk: Application of Numerical Algebraic Geometry to Partial
Differential Equations given by Greg Reid.
Zhonggang Zeng (Northeastern Illinois University)
APAtools: A Maple/Matlab toolbox for approximate polynomial
algebra
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.
Software installation/poster session/reception
Software developers will offer their software for installation
on the laptops of the participants at various booths.
