numerical Schubert calculus
===========================
The module schubert.py exports the hypersurface and quantum
Pieri homotopies to solve the following Schubert problem:
Given a sequence of generic m-planes and a corresponding
sequence of interpolation points, compute all maps of
degree q that meet the given m-planes nontrivially at
the interpolation points.
Pieri homotopies
----------------
The Pieri homotopies illustrates the homotopy approach.
1. Based on the dimension of the input problem, there is a formal
root count on the number of solutions, a root count that is
exact for sufficiently generic instances of the input; and
an upper bound for the number of isolated solution in all cases.
2. For sufficiently generic instances of the input, the performance
of homotopies is optimal in the sense that every solution path
defined by the homotopies ends at an actual solution of the problem.
The methods exported by the schubert module do the following:
1. Compute the formal root count for any m, p, and q.
This calculation goes fast and gives an impression on the
hardness of the problem.
2. Generate random instances of the problem for any (m,p,q).
3. Compute all solutions with the Pieri homotopies.
4. Verify the solutions with solutions.
5. Generate a instance of the problem known to be fully real.
The session below runs the Pieri homotopies to compute all linear maps
that produce 2-planes meeting 8 given 2-planes at random interpolation points:
::
>>> from phcpy.schubert import pieri_root_count
>>> (m,p,q) = (2,2,1)
>>> n = m*p + q*(m+p)
>>> r = pieri_root_count(m,p,q)
Pieri root count for (2, 2, 1) is 8
the localization poset :
n = 0 : ([3 4],[3 4],1)([2 5],[2 5],1)
n = 1 :
n = 2 : ([2 4],[3 5],2)
n = 3 :
n = 4 : ([2 3],[3 6],2)([2 3],[4 5],2)([1 4],[3 6],2)([1 4],[4 5],2)
n = 5 :
n = 6 : ([1 3],[4 6],8)
n = 7 :
n = 8 : ([1 2],[4 7],8)
>>> from phcpy.schubert import random_complex_matrix
>>> L = [random_complex_matrix(m+p,m) for k in range(n)]
>>> points = random_complex_matrix(n,1)
>>> from phcpy.schubert import run_pieri_homotopies
>>> (f,fsols) = run_pieri_homotopies(m,p,q,L,points)
The function **test()** of the module ``schubert``
runs an interactive session to solve instances that
are fully real (in case q = 0).
Littlewood-Richardson homotopies
--------------------------------
With the Littlewood-Richardson homotopies
we can solve general Schubert problems.
The input to a Schubert problem is a sequence of n-by-n matrices and a
corresponding list of intersection conditions, represented by brackets.
For example, the bracket [2, 4, 6] imposes on a 3-plane in 6-space that it
meets nontrivially the space spanned by the first two columns of the
corresponding matrix in a line and that it meets
the space spanned by the first four columns of
the corresponding matrix in a 2-plane.
For a generic sequence of input matrices, there are exactly two 3-planes
in 6-space that satisfy the conditions imposes by the three brackets
[2,4,6], [2,4,6], and [2,4,6], as computed in the session below.
::
>>> from phcpy.schubert import resolve_schubert_conditions as rsc
>>> brackets = [[2,4,6],[2,4,6],[2,4,6]]
>>> rsc(6,3,brackets)
the dimension of the planes : 3
the number of conditions : 3
[2 4 6] and [2 4 6] form a happy configuration.
+1[2 4 6]*[2 4 6] = +1[2 3 4]+2[1 3 5]+1[1 2 6]
[2 3 4] and [2 4 6] are not happy and will not create any children.
[1 3 5] and [2 4 6] are happy and will create children...
[1 2 6] and [2 4 6] are not happy and will not create any children.
The new formal equations :
+2[1 3 5]*[2 4 6] = +2[1 2 3]
All formal equations in the intersection poset :
+1[2 4 6]*[2 4 6] = +1[2 3 4]+2[1 3 5]+1[1 2 6]
+2[1 3 5]*[2 4 6] = +2[1 2 3]
The intersection condition resolved :
+1[2 4 6]*[2 4 6]*[2 4 6]
= (+1[2 3 4]+2[1 3 5]+1[1 2 6])*[2 4 6]
= +2[1 2 3]
2
To compute the 2-planes, we run the Littlewood-Richardson homotopies,
continuing the session from above:
::
>>> from phcpy.schubert import littlewood_richardson_homotopies as lrh
>>> (count, flags, sys, sols) = lrh(6, 3, brackets, verbose=False)
>>> count
2
>>> for sol in sols: print(sol)
...
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x11 : -1.95764646993258E-01 1.07253045769427E+00
x32 : 2.69552376387238E-01 -4.99588315456159E-01
x53 : -9.21562255223665E-01 -9.28437273121748E-01
== err : 3.559E-16 = rco : 4.125E-02 = res : 7.772E-16 =
t : 1.00000000000000E+00 0.00000000000000E+00
m : 1
the solution for t :
x11 : -5.85142692165828E-01 -9.14161314393362E-02
x32 : -5.16006715209336E-01 3.41609194636644E-01
x53 : -6.60253695726872E-02 -1.15262273262567E+00
== err : 2.706E-13 = rco : 9.880E-02 = res : 4.219E-15 =
>>> len(sys)
13
The Littlewood-Richardson homotopies computed two solutions of a system
of 13 equations in 3 unknowns.