HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
Software for Algebraic Geometry
October 23 - 27, 2006


Daniel J. Bates (University of Minnesota, Twin Cities)
http://www.math.colostate.edu/~bates/

Introduction to Bertini: A Software Package for Numerical Algebraic Geometry
October 27, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(ppt)
  • Talks(A/V)(ram)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

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.

Anna M. Bigatti (Università di Genova)
http://www.dima.unige.it/~bigatti/

CoCoALib, A C++ Library for Computations in Commutative Algebra
October 25, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • demo.cocoa(presentation material)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • demo-PolyRing.C (presentation material)
  • Talks(A/V)(ram)

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.

Jürgen Gerhard (Maplesoft)

Maple 11 preview
October 27, 2006

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)
http://dangrayson.com/

Macaulay 2, A Software System for Algebraic Geometry
October 23, 2006

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.

Yun Guan (University of Illinois, Chicago)
Jan Verschelde (University of Illinois, Chicago)
http://www2.math.uic.edu/~jan/

PHClab: A MATLAB/Octave interface to PHCpack
December 31, 1969

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.

Yun Guan (University of Illinois, Chicago)

PHClab
December 31, 1969


Tatsuyoshi Hamada (Fukuoka University)
http://holst.sm.fukuoka-u.ac.jp/~hamada/

KNOPPIX/Math
December 31, 1969

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

Tatsuyoshi Hamada (Fukuoka University)
http://holst.sm.fukuoka-u.ac.jp/~hamada/

KNOPPIX/Math
December 31, 1969

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.

Raymond Hemmecke (Otto-von-Guericke-Universität Magdeburg)
http://www.math.uni-magdeburg.de/~hemmecke

4ti2 -- A Software Package for Algebraic, Geometric and Combinatorial Problems on Linear Spaces
October 25, 2006

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.

Evelyne Hubert (Institut National de Recherche en Informatique Automatique (INRIA))
http://www-sop.inria.fr/members/Evelyne.Hubert

Algebra & Algorithms for Differential Elimination & Completion
October 24, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Notes(pdf)
  • Talks(A/V)(ram)

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)
http://home.imf.au.dk/jensen/

Computing Tropical Varieties in Gfan
December 31, 1969

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.

Anders Nedergaard Jensen (Aarhus University)
http://home.imf.au.dk/jensen/

Computing Tropical Varieties in Gfan
October 26, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(ps)
  • Talks(A/V)(ram)

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.

Masakazu Kojima (Tokyo Institute of Technology)
http://www.is.titech.ac.jp/~kojima/

Parallel Implementation of the Polyhedral Homotopy Method for Polynomial Systems
October 25, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Talks(A/V)(ram)

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.

Grégoire Lecerf (Université Versailles/Saint Quentin-en-Yvelines)
http://lecerf.perso.math.cnrs.fr/

New Recombination Techniques for Polynomial Factorization Algorithms Based on Hensel Lifting
October 26, 2006

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.

Anton Leykin (Georgia Institute of Technology)
http://people.math.gatech.edu/~aleykin3

PHCmaple
December 31, 1969

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)

Anton Leykin (University of Minnesota, Twin Cities)
http://people.math.gatech.edu/~aleykin3

D-modules for Macaulay 2
October 26, 2006

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)

Anton Leykin (Georgia Institute of Technology)
http://people.math.gatech.edu/~aleykin3

D-modules for Macaulay2
December 31, 1969

The package D-modules for Macaulay 2 implements the majority of the algorithms in the computational D-module theory.

(http://www.ima.umn.edu/~leykin/Dmodules)

Peter Nicholas Malkin (Université Catholique de Louvain)

4ti2 – Computing with Lattices, Cones, and Subspaces
December 31, 1969

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.

Bernard Mourrain (Institut National de Recherche en Informatique Automatique (INRIA))
http://www-sop.inria.fr/galaad/mourrain/

SYNAPS, A Library for Symbolic-numeric Computation
October 25, 2006

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.

Pablo A. Parrilo (Massachusetts Institute of Technology)
http://www.mit.edu/~parrilo/

Sums of Squares of Polynomials and SOSTOOLS
October 26, 2006

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.

Gregory J. Reid (University of Western Ontario)
http://www.orcca.on.ca/~reid/NewWeb/

Application of Numerical Algebraic Geometry to Partial Differential Equations
October 27, 2006

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.

Gregory J. Reid (University of Western Ontario)
http://www.orcca.on.ca/~reid/NewWeb/

Software for Partial Differential Equations
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • IMASoftwareTutorial.mws(mws)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • TutSystems.txt(txt)

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.

Fabrice Rouillier (Institut National de Recherche en Informatique Automatique (INRIA))
http://fgbrs.lip6.fr/fabrice/

On Computing Using FGb/RS Software
October 24, 2006

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

Hans Schöenemann (Universität Kaiserslautern)

SINGULAR – A Tool for Algebraic Geometry
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Abstract(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Poster(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Tutorial/Demo(demo)

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 Pn associated to coker(M) for M being a graded module.s It uses the Tate resolution over the exterior algebra.


Mathias Schulze (Oklahoma State University)
http://www.math.okstate.edu/~mschulze/

Gauss-Manin Systems for Isolated Singularities in Singular
October 27, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Talks(A/V)(ram)

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.

Robin Scott (University of Western Ontario)

Approximate Groebner Bases - A Backwards Approach
December 31, 1969

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.

Nobuki Takayama (Kobe University)
http://www.math.sci.kobe-u.ac.jp/~taka/

Some Useful Functions in Risa/Asir
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Poster(pdf)

Joint with Masayuki Noro.


DEMiCs, Software for Dynamic Enumeration of all Mixed Cells
December 31, 1969

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)

Towards a Black-box Solver for Finite Games: The Gambit System
October 24, 2006

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.

Theodore L. Turocy (Texas A & M University)

The Gambit System for Computing in Finite Games
December 31, 1969

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.

Jan Verschelde (University of Illinois, Chicago)
http://www2.math.uic.edu/~jan/

PHCpack: A Software Platform for Numerical Algebraic Geometry
October 24, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Talks(A/V)(ram)

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.

Jan Verschelde (University of Illinois, Chicago)
http://www2.math.uic.edu/~jan/
Yan Zhuang (Wolfram Research, Inc.)
http://www2.uic.edu/~yzhuan1/resume.htm

Parallel Implementation of the Polyhedral Homotopy Method
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Poster abstract(pdf)

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.

John Voight (Dartmouth College)
http://www.math.dartmouth.edu/~jvoight/

Algorithms for Algebraic Geometry in Magma
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • magma-demo.m(Presentation Material)

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)
http://www.nd.edu/~cwample1/

What Should a Software Package for Numerical Algebraic Geometry Be?
October 23, 2006
  • Talks(A/V)(ram)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(ppt)

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.

Charles W. Wampler (General Motors Corporation)
http://www.nd.edu/~cwample1/

Demonstration of HomLab
December 31, 1969

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.

Thomas Wolf (Brock University)

Solving Large Overdetermined Systems with CRACK
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Demo Slides(pdf)

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.

Thomas Wolf (Brock University)

The Package CRACK for Solving Large Overdetermined Systems
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Poster(pdf)

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.

Wenyuan Wu (Michigan State University)
http://www.math.msu.edu/~wenyuanwu/

Symbolic and Numerical Methods for Partial Differential Equations
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Poster(pdf)

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)
http://www.neiu.edu/~zzeng/

APAtools: A Maple/Matlab Toolbox for Approximate Polynomial Algebra
October 23, 2006
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Talks(A/V)(ram)

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.

Connect With Us:
Go