Return to READ_ME CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Schubert

Import the second public release of PHCpack.

OKed by Jan Verschelde.

Numerical Schubert Calculus with PHCv2.

This directory is entirely new in this release of PHC.

SAGBI homotopies are a concatenation of three homotopies :
1) polyhedral homotopies to set up the start system;
2) flat deformation using a Groebner basis for the Grassmannian;
3) Cheater's homotopy towards real target system.

There are three parts in this library:
1) Groebner and SAGBI homotopies
2) original Pieri homotopy algorithm : chain by chain
3) poset-based organization of the Pieri homotopies
The test programs are grouped per part.

--------------------------------------------------------------------------------
file name                        : short description
--------------------------------------------------------------------------------
brackets                         : representation/manipulation of brackets
brackets_io                      : input/output of brackets
bracket_monomials                : monomials of brackets
bracket_monomials_io             : input/output of bracket monomials
bracket_polynomials              : polynomials in the brackets, complex coeff
bracket_polynomials_io           : input/output for bracket polynomials
straightening_syzygies           : implementation of straightening algorithm
bracket_expansions               : expansion of brackets
chebychev_polynomials            : Chebychev polynomials for the conjecture
osculating_planes                : input for the Shapiro^2 conjecture
matrix_homotopies                : management of homotopies between matrices
evaluated_minors                 : determinant computations
sagbi_homotopies                 : set up of the SAGBI homotopies
driver_for_sagbi_homotopies      : driver to the SAGBI homotopies
--------------------------------------------------------------------------------
ts_brackets                      : test manipulation of brackets 
ts_brackmons                     : test bracket monomials
ts_brackpols                     : test bracket polynomials
ts_straighten                    : test straightening algorithm
ts_expand                        : test expansion of brackets
ts_local                         : test localization
ts_cheby                         : test working with Chebychev polynomials
ts_shapiro                       : test generation of input planes
ts_detrock                       : test various root counts on (m,p)-system
ts_sagbi                         : calls the driver to the SAGBI homotopies
--------------------------------------------------------------------------------
pieri_trees                      : representation/creation of Pieri trees
pieri_trees_io                   : output of Pieri trees
pieri_root_counts                : produces a list of Pieri chains
symbolic_minor_equations         : symbolic form of equations in Pieri homotopy
numeric_minor_equations          : evaluated equations in the Pieri homotopy
determinantal_systems            : construction of equations from expansions
solve_pieri_leaves               : compute solutions at leaves of Pieri tree
specialization_of_planes         : set up the moving cycles
pieri_continuation               : traces the paths defined by Pieri homotopy
plane_representations            : conversion between vector and matrix reps
pieri_deformations               : deforms down along the Pieri chains
ts_org_pieri                     : test of original Pieri homotopy algorithm
--------------------------------------------------------------------------------
localization_posets              : posets of top-bottom pivots
localization_posets_io           : output routines for localization posets
pieri_homotopies                 : construction of the Pieri homotopies
curves_into_grassmannian         : representation of the q-curves
curves_into_grassmannian_io      : output facilities for the q-curves
deformation_posets               : posets of solution planes
ts_posets                        : test on creation of the posets
ts_defpos                        : test on deformation posets
drivers_for_input_planes         : generators of input for Pieri algorithm
driver_for_pieri_homotopies      : driver for the Pieri homotopies
driver_for_quantum_pieri         : driver for counting q-maps
ts_pieri                         : test on the Pieri homotopies
mainenum                         : main driver as called by PHC
--------------------------------------------------------------------------------
The equations in the Groebner homotopies are set up by means of the 
straightening algorithm.  Because the Groebner homotopies are not efficient,
they are only auxiliary to the set up of the SAGBI homotopies, which arise 
from expanding the brackets in the linear equations over the Grasmannian.

Organization of the Pieri homotopies :

The original Pieri Homotopy Algorithm is organized in a chain-by-chain 
fashion, whereas the newer implementation uses posets.
The poset-oriented Pieri Homotopy Algorithm works better, but since most of
the basic packages is recycled, we can keep the original Pieri at low cost.
Both implementations have three distinct aspects:

1) combinatorial root count

A. The Pieri tree delivers chains of increasing sequences of brackets.
   Every chain models a sequence of nested subspaces, with lowering
   dimensions towards the leaves of the tree.  The set of input planes
   is partitioned into two nonempty sets and one set containing only the
   last input plane.  For each of the two sets a Pieri tree is constructed.
   A contribution to the root count is made by each pair of leaves that 
   satisfies Pieri's condition, for which a triple intersection of input
   plane yields a start solution.  The input to this combinatorial root
   count is a partition of the list of codimensions.  As output we obtain
   a list of pairs of leaves that satisfy Pieri's condition.

  Ada soft : Pieri_Trees, Pieri_Trees_io, Pieri_Root_Counts

B. The poset-oriented Pieri homotopy algorithm only needs one concept,
   that of a localization pattern.  This pattern is determined by a
   couple of pivots indicating the topmost and bottommost nonzero entries.

  Ada soft : Localization_Posets

2) symbolic-numeric computation

   An intersection condition corresponds to the vanishing of all maximal
   minors of a matrix which is not necessarily square.
   Each matrix consists of two blocks, for coefficients and indeterminates.
   The Laplace expansion into minors respects this division and is
   written formally as a polynomial that is quadratic in brackets.
   To obtain a polynomial system we evaluate the minors, this is the
   numerical part in setting up the equations.
   The zeros in the localization pattern are determined by the positioning
   of the current node in the Pieri trees, but as far as the choice of the
   ones is concerned, we can divide by the largest element in each column to
   obtain a scaling and a numerically favorable representation of the equations.

   Only minor modifications were needed in the poset-oriented version.

  Ada soft : Symbolic_Minor_Equations, Numeric_Minor_Equations
             Determinantal_Systems, Solve_Pieri_Leaves

3) deforming geometries

A. The pairs of chains that end in pairs of leaves that satisfy Pieri's
   condition form the backbone of the deformations in the Pieri homotopy
   algorithm.  The deformations start at the pairs of leaves with a triple
   intersection and move down in the Pieri trees until they reach the
   lowest node where the all intersection conditions are satisfied.
   While moving down we move to larger subspaces which admits the intersection
   with more input planes.  In the case where all codimensions equal one,
   at each node the current solution plane satisfies one more nontrivial
   intersection requirement with an additional input plane.

  Ada soft : Pieri_Homotopies, Pieri_Continuation, Pieri_Deformations

B. The continuous analogue to the localization posets are deformation posets.
   These posets contain in their nodes the solution p-planes at that level.

  Ada soft : Deformation_Posets