October 23 - 27, 2006
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.
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.
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.
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.
(http://www.ima.umn.edu/~leykin/PHCmaple)
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)
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 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.
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.
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/).
Scenario for SINGULAR presentation
1 Overview on SINGULAR
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 P^{n} associated to coker(M) for M being a graded module.s
It uses the Tate resolution over the exterior algebra.
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.
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.
Joint with Masayuki Noro.
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.
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.
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.
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.
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.
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.
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.
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.
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 10^{17} terms.
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.
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.
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.