Pieri Homotopies for Problems in Enumerative Geometry applied to Pole Placement in Linear Systems Control^{∗}

Birkett Huber^{†}  Jan Verschelde^{‡}

May 25, 1999

Abstract

In the numerical Schubert calculus paper, Pieri homotopies were proposed to enumerate all pplanes in ℂ^{m+p} that meet n given (m+1−k_{i})-planes in general position, with k_{1} +k_{2} +⋯+k_{n} = mp as condition to have a finite number of solution p-planes. Essentially the Pieri homotopies turn the deformation arguments of classical Schubert calculus into effective numerical methods by expressing the deformations algebraically and applying numerical path following techniques. In this paper we describe the Pieri homotopy algorithm in terms of a poset of simpler problems. This approach is more intuitive and more suitable for computer implementation than the original chain-oriented description. It also provides a self-contained proof of correctness. We were also able to extend our approach to the quantum Schubert calculus problem of enumerating all polynomial maps of degree q into the Grassmannian of p-planes in ℂ^{m+p} that meet mp+q(m+p) given m-planes in general position sampled at mp + q(m + p) interpolation points. Our approach mirrors existing counting methods for this problem and yields a numerical implementation for the dynamic pole placement problem in the control of linear systems.

AMS Subject Classification. 14N10, 14M15, 65H10, 68Q40, 93B27, 93B55. Keywords. polynomial system, continuation methods, numerical Schubert calculus, Pieri homotopy, cheater’s homotopy, dynamic pole placement problem, control theory, linear system, quantum Schubert calculus, enumerative geometry, Grassmannian.

1 Introduction

A general method to solve geometric problems proceeds by moving the input data to special position, solving the special configuration and then deforming the solutions of the special problem into those of the original configuration. In the second section we show how this technique can be used on the classical problem [18] of finding the two lines in projective 3-space which meet four given lines. Applied to this problem, this general approach forms the simplest instance of the Pieri homotopy algorithm [16].

In the third section we generalize this example to hypersurface conditions. The general problem is to find all p-planes in ℂ^{m+p} that meet mp given m-planes. Assuming that the mp given m-planes are in general position, Schubert [35] counted the number of p-planes meeting those m-planes, establishing recursive and explicit formulas. These p-planes correspond to feedback laws solving the static pole placement problem ([5], [6]) of linear systems control ([10], [17], [47]). Computational experience suggests that the Pieri homotopies are more performant than the Gröbner and SAGBI homotopies also described in [16]. We believe that the reason for this is that the Pieri homotopies are more finely tuned to the geometry of the intersection problem than these other, extrinsic methods.

∗Written by two post-doctors at the Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA 94720-5070, USA.

†E-mail address: birk@msri.org. URL: http://www.msri.org/people/members/birk.

‡Supported in part by NSF under Grant DMS - 9804846 at Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA. E-mail addresses: jan@msri.org, jan@math.msu.edu and jan.verschelde@nanet.ornl.gov. URLs: http://www.msri.org/people/members/jan and http://www.mth.msu.edu/˜ jan.

Establishing a new geometric proof of Pieri’s formula [27], Frank Sottile introduced in [38] intrinsic deformations to solve general intersection conditions given by n planes in general position of dimension m + 1 − k_{i}, for i = 1, 2, …, n. The condition that k_{1} + k_{2} + ⋯ + k_{n} = mp guarantees a finite number of p-planes meeting those n given planes. These Pieri homotopies were elaborated in [16]. In section four we describe this generalization.

Our understanding arose from a first implementation of the Pieri homotopy algorithm and yielded the notion of what we call a ‘localization pattern’. We feel that this is the key meaningful concept in our derivation of the algorithm. Since our aim is to understand practical complexity issues, we excuse ourselves from the explicit use of Schubert varieties [15] in our description. Nevertheless we obtain a self-contained proof of correctness, independent of [16]. The backbone is the poset of localization patterns used to count the roots combinatorially [42] and to set up the homotopies.

Besides rearranging the algorithm in [16] to make it more suitable for computer implementation, one novel feature of this paper is the development of Pieri homotopies for the dynamic pole placement problem. The connection between this problem and the Schubert calculus was established by Joachim Rosenthal in [31] and further developed in [29], [28], [45], and [46]. We arrived at this generalization thanks to a hint of Frank Sottile by reverse engineering on the root counting procedure in [30]. See [4] for other root counts. The adjective ‘quantum’ refers to the important connections between this problem of enumerative geometry and physics [7]. Another related problem is the eigenvalue completion problem [13]. We mention [3] as an alternative recent approach to the dynamic pole placement problem.

The homotopies described in this paper are provided as a separate module in the publicly available software PHCpack [43]. The Pieri homotopy algorithm consists in a combinatorial root count, the symbolic set up of the homotopies and the tracing of the solution curves. This last stage accounts for most of the computational work and is achieved using numerical continuation methods. See [1], [22] for introductions to and [2], [19] for recent surveys on numerical continuation.

This paper ends with a description on computational experiences. We hope to show that the synergy of combinatorics, enumerative geometry and symbolic-numeric methods can contribute something towards the development of numerical algorithms for the pole placement problem, which is formulated as an open problem in [33].

2 The geometry of the Pieri deformations

We can illustrate the geometry of the Pieri deformations on the simplest example of two lines meeting four given lines in projective 3-space.

Recall that projective 3-space is the set of 1-dimensional subspaces of ℂ^{4}. We write ℂ^{4} as the span < e_{1}, e_{2}, e_{3}, e_{4} > of the standard basis vectors e_{1} = (1, 0, 0, 0), e_{2} = (0, 1, 0, 0), e_{3} = (0, 0, 1, 0), and e_{4} = (0, 0, 0, 1). Denote the four given lines by L_{1}, L_{2}, L_{3}, and L_{4}. Without loss of generality we assume that L_{1} is spanned by the first two basis vectors, L_{1} =< e_{1}, e_{2} >, and L_{2} by the last two basis vectors, L_{2} =< e_{3}, e_{4} >. In general, the other two lines L_{3} and L_{4} do not meet each other. This general situation is at the right of Figure 1. Here we are visualizing the real positive orthant of projective 3-space as the interior of the tetrahedron spanned by e_{1}, e_{2}, e_{3} and e_{4}.

[figure: e_{1}; e_{2}; e_{3}; e_{4}; L_{1}; L_{2}; L_{3}; L_{4}; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; e_{1}; e_{2}; e_{3}; e_{4}; L_{1}; L_{2}; L_{3}; L_{4}; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Figure 1: In ℙ^{3} two thick lines meet four given lines L_{1}, L_{2}, L_{3}, and L_{4} in a point. At the left we see a special configuration and the general configuration is at the right.

The special position of L_{1} and L_{2} allows the following special choice of coordinates for the solution line X that meets all four given lines in a point:

X =< x_{1}, x_{2} >= [ \begin{matrix}x_{11} & 0 \\ x_{21} & 0 \\ 0 & x_{32} \\ 0 & x_{42} \end{matrix} ]  (1)

The first column x_{1} of X is the first generator of X and lies on L_{1}. The other generating point x_{2} in the second column lies on L_{2}. By these coordinates the intersection conditions imposed by L_{1} and L_{2} are satisfied already. Since the columns of X may be scaled independently we have two degrees of freedom needed to meet the two remaining intersection conditions imposed by L_{3} and L_{4}.

If we take L_{3} =< e_{1}, e_{3} >, as at the left of Figure 1, we solve the problem as follows. The lines passing through both L_{1} and L_{3} form the plane < e_{1}, e_{2}, e_{3} > which intersects L_{2} at e_{3}. Similarly we see that lines through L_{2} and L_{3} form a plane which must intersect L_{1} at e_{1}. Thus we see that any line which passes through L_{1}, L_{2} and L_{3} must contain either e_{1} or e_{3}. Firstly, consider the set of lines passing through e_{1} and intersecting L_{2}. These lines form a plane < e_{1}, e_{3}, e_{4} > which must intersect L_{4} in a unique point a and thus the line < e_{1}, a > is the unique line through e_{1} intersecting L_{1}, L_{2}, L_{3} and L_{4}. Secondly, the set of lines through e_{3} which intersect L_{1} form a plane which intersects L_{4} in a unique point a′. So we find that the line < e_{3}, a′ > is the unique line passing through e_{3} and intersecting L_{1}, L_{2}, L_{3} and L_{4}. We see that any line that intersects L_{3} at any point other than e_{1} and e_{3} cannot meet both L_{1} and L_{2} because L_{1} ∩ L_{2} = ∅.

An algebraic way to look at this argument goes as follows. Any line which meets both L_{1} and L_{2} must be expressible in the form (1). In order for X to meet L_{3} =< e_{1}, e_{3} > we must be able to find non-trivial linear combinations such that λ_{1}x_{1} + λ_{2}x_{2} = γ_{1}e_{1} + γ_{2}e_{2}. That is the system

[ \begin{matrix}1 & x_{11} & 0 & 0 \\ 0 & x_{21} & 0 & 0 \\ 0 & 0 & 1 & x_{32} \\ 0 & 0 & 0 & x_{42} \end{matrix} ] [ \begin{matrix}−γ_{1} \\ λ_{1} \\ −γ_{2} \\ λ_{2} \end{matrix} ] = 0  (2)

must have a nontrivial solution. This can clearly happen only when x_{21} = 0 or x_{42} = 0. The first case then describes the plane of lines containing e_{1} and meeting L_{2} and gives rise to the solution < e_{1}, a > as above, while x_{42} = 0 yields the solution < e_{3}, a′ >.

Schubert’s principle [34], [49], of “conservation of number” suggests that the number of solutions to the general problem will be the same as the number of the solutions in the special case we just looked at, i.e.: 2. In order to adjust this argument to allow us to find the solutions as well as count them we must consider the process of deforming L_{3} to special position.

The special position we use for L_{3} is given by S =< e_{1}, e_{3} >, so our deformed problem is: find all X such that det(X|L_{1}) = 0, det(X|L_{2}) = 0, det(X|S) = 0, and det(X|L_{4}) = 0. Note that the first two equations are already satisfied when X is chosen as in (1). Specializing the third condition can be achieved by moving the line S into L_{3} taking a convex combination (1 − t)S + tL_{3} of the generating matrices S and L_{3} with t varying from 0 to 1. Fixing the fourth condition and enforcing non-trivial intersection with the moving line yields the homotopy:

H(X, t) = \{ \begin{matrix}det(X|(1 − t)S + tL_{3}) = 0 \\ det(X|L_{4}) = 0 \end{matrix} where X =< x_{1}, x_{2} >, x_{1} ∈ L_{1}, x_{2} ∈ L_{2}.  (3)

Numerical continuation methods trace the solution paths starting at the two solutions X =< e_{1}, a > and X =< e_{3}, b > calculated above for t = 0 to the solutions of the original problem at t = 1.

The plain application of this geometric principle of conservation of number may fail, because on a picture we cannot see whether the multiplicity equals one. Therefore we need to examine the algebraic formulations of the intersection conditions. As local coordinates we choose x_{11} = 1 and x_{32} = 1. Then det(X|S) = 0 ⇔ x_{21}x_{42} = 0. So, at t = 0, as either x_{21} = 0 or x_{42} = 0, the structure of the matrix of partial derivatives of the system H(X, t = 0) is

[ \begin{matrix}x_{42} & x_{21} \\ C_{13}x_{42} − C_{14} & C_{13}x_{21} − C_{23} \end{matrix} ]  (4)

with C_{ij} the 2-by-2 minor by selecting rows i and j from the matrix representation of L_{4}. For L_{4} in general position, the two start solutions are regular and admit well-defined deformations. For general L_{3}, this regularity is maintained up to t = 1.

3 Pieri-type deformations for hypersurface conditions

In this section we extend the approach of the last section to produce an algorithm for computing all p-planes in ℂ^{m+p} that intersect mp given m-planes L_{i} in general position. In order to have a uniform description of the algorithm, we will skip the step of specializing the first two m-planes, and the last step of using linear algebra to intersect with the last m-plane. Instead we will describe the algorithm solely in terms of the continuation step which involved deforming L_{3} to S. Later we shall see that the adding these linear algebra steps back in essentially amounts to truncating the algorithm as we describe it and does yield a significant computational savings.

We represent p-planes in ℂ^{m+p} by (m + p) × p-matrices whose columns form a set of generators. Solutions to our problem are represented by variable (m + p) × p-matrices. We move the input data into special positions such that the solution planes have matrix representations with zero coordinates at specific positions. To specify those positions, we need the following definition.

Definition 1 A localization pattern is an element of {0, ⋆}^{(m+p)×p} such that all stars in a column are contiguous and the row indices in which the bottommost and topmost stars occur strictly increase as functions of the column number. These row indices are called the top and bottom pivots respectively. A p-plane fits a localization pattern if it can be represented by a matrix of generators with zero entries everywhere the localization pattern prescribes them.

Consider for example the case where p = 2, m = 4 and we are looking for all 2-planes which meet eight 4-planes. We can take the first two planes as L_{1} =< e_{1}, e_{2}, e_{3}, e_{4} > and L_{2} =< e_{3}, e_{4}, e_{5}, e_{6} >. For any 2-plane that meets both these planes non-trivially we choose its generators such that one generator lies in L_{1} and the other in L_{2}. Such a 2-plane is represented by a variable matrix

[ \begin{matrix}x_{11} & 0 \\ x_{21} & 0 \\ x_{31} & x_{32} \\ x_{41} & x_{42} \\ 0 & x_{52} \\ 0 & x_{62} \end{matrix} ] which fits the pattern [ \begin{matrix}⋆ & 0 \\ ⋆ & 0 \\ ⋆ & ⋆ \\ ⋆ & ⋆ \\ 0 & ⋆ \\ 0 & ⋆ \end{matrix} ] .  (5)

Planes which satisfy this localization pattern already meet L_{1} and L_{2}. Equivalently, any specialization of the variables x_{ij} in the pattern will result in a p-plane which has non-trivial intersection with L_{1} and L_{2}. Thus our problem is to find values of these variables such that the plane meets the remaining 4-planes. We achieve this by specializing the input planes as follows.

Definition 2 Given a localization pattern X, the special m-plane for the top (bottom) pivots of X is the m-plane S_{X} spanned by the standard basis vectors not indexed by pivots.

By this choice of special m-plane we are able to specialize the localization patterns which the p-planes that meet this special m-plane must fit.

Definition 3 A top (bottom) child of a localization pattern X is a localization pattern obtained by turning a top (bottom) most star of X to a zero.

For the bottom localization pattern in Figure 2 having bottom pivots [3 5], the special 4-plane is < e_{1}, e_{2}, e_{4}, e_{6} >. Lemma 4 states that all 2-planes meeting this special 4-plane and fitting the bottom pattern must fit one of its two children.

[figure: ^{[^{⋆} ^{0}^{⋆} ^{⋆}^{0} ^{⋆}^{0} ^{⋆}^{0} ^{⋆}^{0} ^{0} ]}; [^{⋆} ^{0}^{⋆} ^{⋆}^{⋆} ^{⋆}^{0} ^{⋆}^{0} ^{⋆}^{0} ^{0} ]; ^{[^{⋆} ^{0}^{⋆} ^{⋆}^{⋆} ^{⋆}^{0} ^{⋆}^{0} ^{0}^{0} ^{0} ]}; [3 4]; [3 5]; [2 5]]

Figure 2: A localization pattern with bottom pivots [3 5] and its two children [2 5] and [3 4]. At the right we see the bottom pivots used as a short-hand notation.

Lemma 4 (Hypersurface Pieri rule) Let S_{X} be the special m-plane for top (bottom) pivots of the localization pattern X. Every p-plane that fits X and meets S_{X} also fits one of the (at most p) children of X. Conversely every p-plane that fits a child of X fits X and meets S_{X}.

Proof. A p-plane that fits X meets S_{X} if, and only if, given any specification of the variables of X, we can find a linear combination of the columns of the p-plane which lies in S_{X}. This means that the intersection of the p-plane with S_{X} can be represented as a linear combination of the columns of S_{X}. Finding this linear combination is equivalent to finding a non-trivial element of the kernel of [X|S_{X}]. Since the m columns of S_{X} have pivots distinct from those of the p columns of X, the matrix [X|S_{X}] is an (m + p) × (m + p) matrix with m + p distinct pivot rows. So we can rearrange [X|S_{X}] into a triangular matrix, which is singular precisely when one of the diagonal elements coming from X is specialized to zero. □

The repeated application of Lemma 4 builds up a poset that allows to count the roots. The poset starts at the trivial localization pattern X_{0} which has at column i its top pivot at row i and bottom pivot at row m + i. While there are p-planes that do not fit X_{0}, the set of p-planes that do fit X_{0} includes those for which all Plücker coordinates are non-zero. This is a dense open subset of the Grassmannian and with the general position assumption on our input planes it will suffice to count the number of solution planes which fit X_{0}. This start pattern, X_{0} has exactly mp + p ⋆s and our original list of conditions contains exactly mp given m-planes. Initially we apply Theorem 5 starting at X = X_{0} and n = mp:

Theorem 5 Consider a localization pattern X with p+n ⋆s. For n = 0, X counts for one solution. For n > 0, the number of p-planes fitting X and meeting n general m-planes equals the sum of the number of solution planes fitting the children of X and meeting n − 1 general m-planes.

Before proving the theorem, we illustrate the root counting procedure in Figure 3 where we use the short-hand notation introduced in Figure 2 for the localization patterns.

[figure: [1 2]; 1; [2 3]; 1; [3 4]; 2; [4 5]; 5; [5 6]; 14; n = 0; n = 1; n = 2; n = 3; n = 4; n = 5; n = 6; n = 7; n = 8; [1 3]; 1; [2 4]; 2; [3 5]; 5; [4 6]; 14; [1 4]; 1; [2 5]; 3; [3 6]; 9; [1 5]; 1; [2 6]; 4; [1 6]; 1]

Figure 3: Combinatorial root count for p = 2, m = 4. The brackets at the left are the bottom pivots. The top pivots remain [1 2]. The trivial localization pattern X_{0} corresponds to [5 6]. The roots are counted at the right, starting at the top and adding up the numbers at the leaves while moving down to the root of the poset yielding 14 solutions.

Theorem 5 is proven by induction and follows from the correctness of the Pieri homotopy. Applying the Pieri homotopy algorithm following the root counting procedure through the poset yields an effective algorithm for actually finding the solutions.

Definition 6 Let X be a localization pattern and S_{X} the special m-plane for top (bottom) pivots of X. Suppose that n − 1 general intersection conditions are satisfied for children Y of X i.e.: det(Y |L_{i}) = 0, for i = 1, 2, …, n − 1. To satisfy the nth intersection condition, the Pieri homotopy H(X, t) = 0 is:

H(X, t) = \{ \begin{matrix}det(X|(1 − t)S_{X} + tL_{n}) = 0 \\ det(X|L_{i}) = 0 & i = 1, 2, …, n − 1 \end{matrix} t ∈ [0, 1].  (6)

To illustrate the Pieri homotopy, we consider the situation as in going down to [3 5], with the three 2-planes that fit the left child [2 5] and two 2-planes that fit the right child [3 4]. Locally the situation is pictured in Figure 2, with the global root counting procedure in Figure 3. At t = 0, n = 4, and we have already folded in the first four intersection conditions and are moving the special 4-plane < e_{1}, e_{2}, e_{4}, e_{6} > to the fifth input plane. In general we have the situation as in the following Lemma.

Lemma 7 Consider a localization pattern X with p+n stars and n complex m-planes L_{i} in general position. Suppose we are given all p-planes that meet L_{i}, i = 1, 2, …, n−1 and fit one of the children of X. Then the Pieri homotopy defines regular paths of p-planes, that start at the given p-planes and that end at those p-planes that meet all n general m-planes L_{i} while fitting X.

Proof. Our working space is a product of projective spaces, with as many spaces as there are columns in X. To describe this multi-projective space more precisely, we count the stars in X. For X defined by p-tuples of top and bottom pivots, respectively α, β ∈ ℕ^{p}, we embed the p-planes into ℙ^{d_{1}} × ℙ^{d_{2}} × ⋯ × ℙ^{d_{p}} with d_{i} = β_{i} − α_{i}, i = 1, 2, …, p. To fix an affine coordinate chart we set one coordinate to 1 in every column by scaling the corresponding generator of the p-plane.

Essentially we are applying a multi-homogeneous homotopy [23, 24] in a general situation. By the assumption of this Lemma, all p-planes at t = 0 are regular solutions, as the m-planes L_{i} are in general position. This general position is maintained for all t ∈ [0, 1], ensuring the smoothness of the solution paths.

Rest us to show that we will find all p-planes. Suppose at t = 1 there are more solutions than the paths we have started with. Going backwards with those additional solutions from t = 1 to t = 0 we either move to a singular solution, or to a solution at infinity. But at t = 0, all solutions are regular. By Lemma 4, all solutions have been found and since the localization patterns admit any affine chart, there are no solutions at infinity for t = 0. □

We remark that the root count in Figure 3 by changing only bottom pivots is just one possibility. One could alternatingly change bottom and top pivots in building up the levels of the poset. As was done in section 2, linear algebra can be applied to intersect with the last input plane. Another, more significant optimization includes the special position of the first two input planes. Choosing a basis so that the first two m-planes are already in special position L_{1} =< e_{1}, …, e_{m} > and L_{2} =< e_{p+1}, …, e_{m+p} > amounts to enforcing a different starting pattern for the poset. This has two advantages. The first is that it really forces any pattern meeting all original planes to meet the starting localization pattern regardless of the genericity of the remaining input planes. The second is that it saves the work of doing the two final and most costly (because of highest dimension) continuation steps.

In contrast to the approach of [16], we have separated in our description the hypersurface Pieri homotopy algorithm from the case of general intersection conditions. Our description allows to simplify the definition of special m-planes. However, when all input m-planes are spanned by real matrices, we need the more general choice of special m-planes as defined in [16] to enforce complex arithmetic for avoiding quadratic turning points along the solution paths. Also for the general intersection conditions we need the definition of [16] for special m-planes. So in Definition 2 we replace each of the standard basis vectors e_{i} by vectors b_{i} that have random complex entries in rows i and higher (lower) for bottom (top) pivots i. This adaption of Definition 2 we assume for the rest of the paper.

4 General intersection conditions

In the general case we are looking for p-planes in C^{m+p} which non-trivially meet a list of generic subspaces L_{1}, L_{2}, …, L_{n} where each L_{i} has dimension m + 1 − k_{i}. It turns out each of these conditions removes k_{i} degrees of freedom, and thus that we will expect a finite number of solutions when k_{1} + k_{2} + ⋯ + k_{n} = mp.

In specializing the ith (m + 1 − k_{i})-plane L_{i} we move it to the intersection of k_{i} special mplanes. This deformation of the solution p-planes while moving L_{i} from general to special position proceeds in k_{i} steps, each time specializing zero coordinates in the solution planes. In modeling this deformation we need to be aware of the left and right sides of our localization patterns when working respectively with bottom and top pivots.

Definition 8 For the localization patterns X^{1} and X^{2} we write X^{1} ⊃_{c_{1}} X^{2} to indicate that X^{2} is the child of X^{1} obtained by turning the pivot in column c_{1} of X^{1} to zero. We say that the chain of length j

C = X^{1} ⊃_{c_{1}} X^{2} ⊃_{c_{2}} ⋯ ⊃_{c_{j−1}} X^{j}  (7)

is bottom-left if c_{i−1} ≤ c_{i}, i = 2, …, j for bottom pivots c_{i}, or top-right if c_{i−1} ≥ c_{i}, i = 2, …, j for top pivots c_{i}. If C is bottom-left (resp. top-right), we will call any child X^{j+1} of X^{j} a bottom-left child (resp. top-right child) of C if the chain X^{1} ⊃_{c_{1}} ⋯ ⊃_{c_{j−1}} X^{j} ⊃_{c_{j}} X is also bottom-left (resp. top-right).

In other words, in a bottom-left (top-right) chain, we never take away a bottom (top) pivot in a column to the right (left) of one we have already taken. Note that when C = X^{1} is a length one chain we have not taken any pivots away yet and all children of X^{1} are bottom-left (top-right) children of C.

Notice that the pivots of X^{1} ⊃_{c_{1}} X^{2} are the same except in column c_{1} and that the new pivot of X^{2} can not have been a pivot of X^{1} (otherwise X^{2} would not be a localization pattern). Thus S_{X^{1}} ∩ S_{X^{2}} has dimension m − 1. Similarly we can see that the intersection S_{X^{1}} ∩ S_{X^{2}} with S_{X^{3}} drops the dimension by one whenever X^{3} is a child of X_{2} obtained by deleting a pivot in a column with index less than or equal to c_{1}. This justifies the dimension of the following definition.

Definition 9 For a bottom-left (top-right) chain C = X^{1} ⊃_{c_{1}} X^{2} ⊃_{c_{2}} ⋯ ⊃_{c_{j−1}} X^{j}, and an index 1 ≤ k ≤ j we define a special (m + 1 − k)-plane S_{C}^{k} to be S_{C}^{k} = ∩_{i=1}^{k}S_{X^{i}}, where the S_{X^{i}} are the special m-planes associated to the X^{i} in C.

From now on we assume that we work with bottom pivots.

Lemma 10 (General Pieri rule) Let C be a bottom-left chain of length j ending at X^{j}.

1. All p-planes fitting X^{j} and meeting S_{C}^{j} must fit at least one of X^{j}’s children.

2. A child X^{j+1} meets S_{C}^{j} iff X^{j+1} is a bottom-left child of C, i.e. iff X^{j} ⊃_{c_{j}} X^{j+1} where c_{j+1} ≤ c_{j}.

Proof. Any p-plane which fits X^{j} and meets S_{C}^{j} must also meet S_{X_{j}} and thus must be a child of X^{j} by Lemma 4. This proves the first claim.

Recall from the proof of Lemma 4 that X^{j+1} meets S_{C}^{j} if, and only if, given any specification of the variables of X^{j} for which the pivot elements are non-zero it is possible to find a linear combination of the columns which lies in S_{C}^{j}. Clearly any such linear combination must involve the decremented column c_{j+1} and no columns after it, since all pivots of vectors in S_{C}^{j} must be non-pivots of X^{j}.

If c_{j+1} ≤ c_{j}, then the first c_{j} − 1 columns of X^{j+1} have remained unchanged all the way through the chain, and the last has only had successive pivots removed. Thus S_{C}^{j} must contain a basis vector with a pivot row in each non-pivot of the first c_{j+1} columns of X^{j}. So if we take these basis vectors along with the first c_{j+1} columns of X^{j} we get a set of r_{j} column vectors with r_{j} distinct pivots all in rows r_{j}. Since X^{j+1} is obtained from X^{j} by deleting the pivot of column c_{j+1} we find that the (c_{j+1})th column must be in the span of the remaining columns, and this linear relation can be rewritten to express a vector of S_{C}^{j} as a linear combination of columns of X^{j+1}.

On the other hand, if c_{j+1} > c_{j}, then at least one non-pivot of these first c_{j+1} columns of X^{j} must have been a pivot previously and S_{C}^{j} must have no vector with a pivot in this row. In other words we are looking for a solution to a subsystem of the previous system where we have removed some number of columns (aside from that corresponding to column c_{j+1} of X^{j+1}). Looking at just the pivot rows appearing we get either a square triangular system with non-zeros on the diagonal (if the pivot of column c_{j+1} did not appear) or a non-square system with non-zero pivots in each column. In either case no non-trivial solution is possible. □

Theorem 11 Let X^{1} be a localization pattern with p + ∑_{i=1}^{n−1} k_{i} stars where the k_{i} are the codimension conditions specified in the problem (i.e.: dim(L_{i}) = m + 1 − k_{i}). Further suppose that C = X^{1} ⊃_{c_{1}} X^{2} ⊃_{c_{2}} ⋯ ⊃_{c_{j−1}} X^{j}, (1 ≤ j ≤ k_{n}) is a bottom-left chain starting at X_{1}. For 1 ≤ k ≤ j let U_{C}^{k} be a generic (m + 1 − k_{n})-dimensional subspace of S_{C}^{k} = ∩_{i=1}^{k}S_{X^{i}}. Then the number of p-planes meeting U_{C}^{j−1} as well as L_{1}, …, L_{n−1} and fitting X^{j} is equal to the sum of the numbers of p-planes meeting U_{C}^{j}, L_{1}, …, L_{n−1} and meeting X′ as X′ runs over all bottom-left children of C.

As with the hypersurface case, Theorem 11 is proven by induction and follows from the correctness of a homotopy. Before describing this homotopy we will show that the theorem provides a root count procedure generalizing that of the last section. Combining the homotopy with this counting procedure will yield an effective technique for producing all solutions. It is a little easier to understand the implications of the theorem for root counting if we restate it without reference to the intermediate steps where our input planes are partially specialized:

Corollary 12 Suppose X is a localization pattern with p + ∑_{i=1}^{n} k_{i} stars where the k_{i} are codimension conditions specified in the problem (i.e.: dim(L_{i}) = m + 1 − k_{i}). Then the number of p-planes fitting X and meeting L_{1}, …, L_{n} is equal to the total number of p-planes meeting L_{1}, …, L_{n−1} and fitting at least one descendant X′ of X accessible as a bottom left child of a bottom-left chain of length k_{n} starting at X.

Proof. To see that the corollary follows from Theorem 11, consider applying the theorem k_{n} times starting from the hypothesis of the corollary. Note that the first application of the theorem leaves

[figure: [2 4]; 1; [3 4]; 2; [5 6]; 3; n = 0; n = 1; n = 2; n = 3; n = 4; [3 5]; 2; [4 6]; 3; [1 5]; 0; [2 5]; 1; [3 6]; 3; [1 2]; 1; [1 3]; 1; [1 4]; 1; [2 6]; 1; [1 5]; 1; [1 6]; 1; [1 3]; 0; [2 3]; 0; [2 4]; 1; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Figure 4: Bottom pivots for p = 2, m = 4, k_{i} = 2, i = 1, 2, 3, 4. Only those arcs and nodes are drawn that connect localization patterns reachable by bottom-left chains. The corresponding root count is at the right.

us with the problem of counting the number of p-planes meeting L_{1}, …, L_{n−1}, and also meeting an m + 1 − k_{n} plane lying in S_{X} and fitting a child of X. Each of these numbers can now be counted by applying the theorem to the new case with n = n − 1, j = 2 and C = C^{1} ⊃ C^{2}. This process continues until all our chains have length k_{n} and the subspace U_{C}^{j+1} = S_{C}^{k_{n}} in the conclusion of Theorem 11 is a special m + 1 − k_{n} space and that Lemma 10 implies that any p-plane fitting a bottom-left child of C will meet S_{C}^{j}. □

Figure 4 illustrates the combinatorial root count in a similar fashion as in Figure 3. Starting at the root of the tree we apply the theorem to the case n = 4, j = 1, C = [56] to see that the number of 2-planes which fit the pattern [56] and meet 4 general 3-planes L_{1}, L_{2}, L_{3}, L_{4} is equal to the number of p-planes which fit [46], meet the 3 general 3-planes L_{1}, L_{2}, L_{3} and meet a general 3-plane lying inside the special 4-plane S_{[56]}. A second application of the theorem in the case n = 3, j = 2 C = [56] ⊃_{1} [46] now tells us that this number is equal to the number of p-planes fitting the pattern defined by [36] and meeting the 3 general 3-planes L_{1}, L_{2}, L_{3}. Note that by Lemma 10 we do not get any solutions fitting the pattern defined by [45] (so we omitted [45] in the Figure). Continuing, with n = 3, j = 1, C = [36], we find that the number of 2-planes fitting the pattern defined by [36] and meeting L_{1}, L_{2}, L_{3} is equal to the sum of the numbers fitting the two children of [36] and meeting L_{1}, L_{2}, and a general 3-plane lying inside of S_{[36]}. Applying the theorem with n = 3, j = 2 to the chains [36] ⊃_{1} [26] and [36] ⊃_{2} [35] we find that the total number of 2-planes fitting the pattern defined by [36] and meeting L_{1}, L_{2}, and L_{3} is equal to the sum of the numbers of 2-planes meeting L_{1} and L_{2} and fitting any of the localization patterns defined by [16], [25], and [34].

It is important to note that during the intermediate steps when the chains C have length j > 1, the number of solutions at a node depends on both the localization pattern and the chain. Thus we can only share nodes corresponding to the j = 1 case, i.e.: those nodes with no partially specified input planes. In Figure 4 these cases (with j = 1) are indicated by dotted horizontal lines. Also note that some chains may not make it k_{n} steps and may simply stop and fail to yield any solutions. Both these points are illustrated by considering the localization pattern [15] in Figure 4. Applying Theorem 11 with n = 2, j = 2 on the chains [16] ⊃_{2} [15] yields an equivalence with the numbers of solutions fitting [14] and meeting L_{1} while applying the theorem to with n = 2, j = 2 and the chain [25] ⊃_{1} [15] yields no solutions at all since this chain has no right hand children. We are now ready to define the homotopy which provides our effective proof of Theorem 11.

Definition 13 Let X, n, j, and C be as in Theorem 11, and suppose that the subspaces U_{C}^{j} and U_{C}^{j−1} are represented by (m + p) × (m + 1 − k_{n})-dimensional matrices made up of random linear combinations of the S_{C}^{j} and S_{C}^{j−1} (except that U_{C}^{0} = L_{n}). We define the Pieri Homotopy H_{C}^{j}(X, t) = 0 to be

H_{C}^{j}(X, t) = \{ \begin{matrix}all maximal minors of [X|(1 − t)U_{C}^{j} + tU_{C}^{j−1}] \\ det(X|L_{i}) = 0, i = 1, 2, …, n − 1 \end{matrix} t ∈ [0, 1].  (8)

Note that while this homotopy may well have more equations than unknowns it will turn out to define a non-singular path of solutions through each starting point. Here we will prove that these equations define a homotopy which can be used to find all solutions. We will defer a discussion of techniques for actually following these paths numerically to the next section.

Lemma 14 Supposing that the solutions of H_{C}^{j}(X, 0) = 0 are all nonsingular as X varies over all bottom-left continuations of C then the Pieri homotopy H_{C}^{j}(X, t) = 0 defines regular paths through these solutions which lead to all solutions of H_{C}^{j}(X, 1).

Proof. As in the proof of Theorem 5, our working space is the product ℙ^{d_{1}} × ℙ^{d_{2}} × ⋯ × ℙ^{d_{p}} of projective spaces where d_{j} is the number of stars in each column of X, and we are essentially applying a multi-homogeneous homotopy [23, 24]. By assumption all p-plane solutions at t = 0 are regular, and since U^{j} defines an (m + 1 − k_{n})-dimensional subspace of S_{c}^{j−1} we see that U^{j−1} which defines a generic (m + 1 − k_{n})-dimensional subspace of S_{c}^{j−1} must also define an intersection problem with a solution set consisting of a finite number of regular p-planes. This general position is maintained for all t ∈ [0, 1], ensuring the smoothness of the solution paths.

It remains to show that we will find all p-planes. This argument is exactly analogous to the proof of Theorem 5 except that we rely on Lemma 10 to show that all solutions found must fit some bottom-left child of C when we go backwards. □

Theorem 11 follows from the lemma by induction. We start at the tops of the counting poset where the localization patterns all have exactly p stars and no subspace conditions to meet and hence define unique solutions. The hypotheses of the homotopy lemma are then met and this forces the conditions to be met all the way down.

5 Control of linear systems and quantum Schubert calculus

This section is organized in three parts. We first rephrase the dynamic pole placement problem into a problem of enumerative geometry [31]. Thereafter we derive the critical dimension [46] to have a finite number of solutions. Lastly we state the root-counting theorem [29] and prove it inductively from the correctness of the Pieri homotopies.

We want to control a plant with n internal states x ∈ ℝ^{n} that takes m-inputs u ∈ ℝ^{m} and produces p-outputs y ∈ ℝ^{p} with a dynamic compensator that has q internal states z ∈ ℝ^{q}. Schematically we picture this situation in Figure 5.

The evolution in time of the plant is described by a system of first-order differential equations:

\{ \begin{matrix}ẋ = Ax + Bu \\ y = Cx \end{matrix}  with x ∈ ℝ^{n}, u ∈ ℝ^{m}, y ∈ ℝ^{p}, and A ∈ ℝ^{n×n}, B ∈ ℝ^{n×m}, C ∈ ℝ^{p×m}.  (9)

[figure: u ∈ ℝ^{m}; x ∈ ℝ^{n}; y ∈ ℝ^{p}; z ∈ ℝ^{q}]

Figure 5: Control of an m-input and p-output plant by a q-th order dynamic compensator.

The dynamic compensator obeys a q-th order differential equation, described by the system:

\{ \begin{matrix}ż = F z + Gy \\ u = Hz + Ky \end{matrix}  with z ∈ ℝ^{q} and \begin{matrix}F ∈ ℝ^{q×q}, G ∈ ℝ^{q×p}, \\ H ∈ ℝ^{m×q}, K ∈ ℝ^{m×p}. \end{matrix}  (10)

Concatenation of (9) and (10) yields after elimination of u and y the following closed-loop system:

[ ẋ ż ] = [ \begin{matrix}A + BKC & BH \\ GC & F \end{matrix} ] [ \begin{matrix}x \\ z \end{matrix} ]  (11)

The behavior of this closed-loop system is determined by the n+q eigenvalues of the matrix in (11). For a plant given by the matrix triplet (A, B, C), and n+q eigenvalues, the dynamic pole placement problem asks for the matrix quadruples (F, G, H, K) to determine the dynamic compensators that yield closed loop systems with a specific set of eigenvalues.

We can formulate the dynamic pole placement problem as a geometric problem. In rewriting the characteristic equation of (11) the subscripts in I denote the dimension of the identity matrix. There is only a little magic involved in deriving (14), the rest of the equivalences are deduced by elementary row and column operations.

det (s [ \begin{matrix}I_{n} & 0 \\ 0 & I_{q} \end{matrix} ] − [ \begin{matrix}A + BKC & BH \\ GC & F \end{matrix} ]) = 0  (12)
⇔ det [ \begin{matrix}sI_{n} − A − BKC & −BH \\ −GC & sI_{q} − F \end{matrix} ] = 0  (13)

⇔ det [ \begin{matrix}sI_{n} − A − BKC & −BH & BK & −B \\ −GC & sI_{q} − F & G & 0 \\ 0 & 0 & I_{p} & 0 \\ 0 & 0 & 0 & I_{m} \end{matrix} ] = 0  (14)

⇔ det [ \begin{matrix}sI_{n} − A & 0 & 0 & −B \\ 0 & sI_{q} − F & G & 0 \\ 0 & 0 & I_{p} & 0 \\ 0 & −H & K & I_{m} \end{matrix} ] = 0  (15)

⇔ det [ \begin{matrix}I_{n} & 0 & 0 & −(sI_{n} − A)^{−1}B \\ 0 & I_{q} & G(sI_{q} − F)^{−1} & 0 \\ C & 0 & I_{p} & 0 \\ 0 & −H & K & I_{m} \end{matrix} ] = 0  (16)

⇔ det [ \begin{matrix}I_{n} & 0 & 0 & −(sI_{n} − A)^{−1}B \\ 0 & I_{q} & G(sI_{q} − F)^{−1} & 0 \\ 0 & 0 & I_{p} & C(sI_{n} − A)^{−1}B \\ 0 & 0 & HG(sI_{q} − F)^{−1} + K & I_{m} \end{matrix} ] = 0  (17)

The last m + p rows and columns of (17) represent the intersection of m-planes defined by the given triplet (A, B, C) with p-planes determined by the unknown quadruple (F, G, H, K). As these p-planes depend on the variable s introduced by the the term (sI_{q} −F)^{−1} they have maximal minors of degree q and we call them degree q maps. Thus the dynamic pole placement problem is equivalent to the computation of all maps of degree q into the Grassmannian of p-planes that meet n given m-planes at prescribed s-values. It is easy to see that for each specification of an eigenvalue λ_{i} the condition that the characteristic polynomial (17) vanish at s = λ_{i} enforces one polynomial condition on the set of q-maps.

Note that when q = 0 we are solving the static pole placement problem (u = Ky and F, G, H = 0) and are looking for maps of degree 0 (i.e. constant maps) which meet a specific set of given m-planes. In this case the characteristic equation (17) has degree n and we can find solution planes whenever n is less than the dimension mp of the space of p-planes in (m + p)-dimensional space. At the critical dimension n = mp, we expect the number of such solutions to be finite. In other words when q = 0 and n = mp this analysis transforms the static pole placement problem into the problem of finding all p-planes meeting a set of mp given m-planes dealt with in Section 3. For general q we will be able to use similar methods to solve it, but will need the following lemma which specifies the critical dimension and allows us to produce localization patterns for our maps.

Lemma 15 Let q = dp + r with d, r ∈ ℕ and r < p. The set of (m + p) × p degree q maps is of dimension mp + q(m + p) and has a dense open subset which can be represented by matrices with entrees of maximum degree d in all but the last r columns and degree d + 1 in the remaining r columns.

Proof: Given a polynomial matrix we will define the degree of a column to be the maximum degree of any of its entrees. Also note that two (m + p) × p polynomial matrices define the same map if there is an invertible p × p matrix U(s) which takes one into the other by right multiplication. Lemma 3.1 from [46] tells us that for any (m + p) × p degree q map X′(s), there is a unique choice of column degrees d_{1} ≤ … ≤ d_{p} (with q = d_{1} + ⋯ + d_{p}) such that the X′(s) is equivalent to a matrix X(s) with these column degrees. In other words the sets U_{d_{1},...,d_{p}} of degree q maps which can be represented by (m + p) × p matrices with column degrees d_{1}, …, d_{p} disjointly cover the set of degree q maps.

In order to find the dimension of U_{d_{1},...,d_{p}} we will want to find a canonical form for a general member. By a general member of U_{d_{1},...,d_{p}} we mean, a matrix X(s) whose entrees are polynomials of appropriate degrees with no algebraic relations among the coefficients. If we write a_{i,j}^{k} for the coefficient of s^{k} in the (i, j)-th entry of X(s), we can express our normal form by requiring a_{i,i}^{0} = 1 for i = 1, …, p and if for all i < j we have a_{i,j}^{k} = 0 if k ≤ d_{j} − d_{i} and a_{j,i}^{0} if d_{j} = d_{i}. This normal form is illustrated in Figure 6 and can be achieved by the following algorithm:

for i = 1, 2, …, p do X_{i} := \frac{1}{a_{i,i}^{0}} X_{i};

for j = i + 1, i + 2, …, p do

if d_{i} = d_{j}, then X_{i} := X_{i} − \frac{a_{j,i}^{0}}{a_{j,j}^{0}} X_{j}; zero out a_{j,i}^{0}

\begin{aligned}[ & \begin{matrix}1 & 0 & 0 & 0 + 0s & 0 + 0s + 0s^{2} \\ 0 & 1 & 0 & 0 + 0s & 0 + 0s + 0s^{2} \\ 0 & 0 & 1 & 0 + 0s & 0 + 0s + 0s^{2} \\ ⋆ & ⋆ & ⋆ & 1 + ⋆s & 0 + 0s + ⋆s^{2} \\ ⋆ & ⋆ & ⋆ & ⋆ + ⋆s & 1 + ⋆s + ⋆s^{2} \\ ⋆ & ⋆ & ⋆ & ⋆ + ⋆s & ⋆ + ⋆s + ⋆s^{2} \\ ⋆ & ⋆ & ⋆ & ⋆ + ⋆s & ⋆ + ⋆s + ⋆s^{2} \end{matrix} & ] \\ & U_{0,0,0,1,2} \end{aligned}  \begin{aligned}[ & \begin{matrix}1 & 0 & 0 + 0s & 0 + 0s & 0 + 0s \\ 0 & 1 & 0 + 0s & 0 + 0s & 0 + 0s \\ ⋆ & ⋆ & 1 + ⋆s & 0 + ⋆s & 0 + ⋆s \\ ⋆ & ⋆ & 0 + ⋆s & 1 + ⋆s & 0 + ⋆s \\ ⋆ & ⋆ & 0 + ⋆s & 0 + ⋆s & 1 + ⋆s \\ ⋆ & ⋆ & ⋆ + ⋆s & ⋆ + ⋆s & ⋆ + ⋆s \\ ⋆ & ⋆ & ⋆ + ⋆s & ⋆ + ⋆s & ⋆ + ⋆s \end{matrix} & ] \\ & U_{0,0,1,1,1} \end{aligned}

Figure 6: Standard forms for m = 2, p = 5 and q = 3 with 28 and 31 stars respectively

for k = 0, 1, …, d_{j} − d_{i} do X_{j} := X_{j} − \frac{a_{i,j}^{k}}{a_{i,i}^{0}} s^{k}X_{i}. zero out a_{i,j}^{k}

The genericity of X(s) ensures that the replacements in this algorithm each introduce no zeros besides the desired one in the coefficient a_{i,j}^{k} so that the algorithm is well defined and will terminate having introduced exactly the zeros required for the canonical form. It is easy to check that each of the replacements appearing in the algorithm is equivalent to the application of an invertible transformation. Thus the result defines the same map as the input. Also note that replacing any column of a matrix in this form by a non-trivial linear combination of the other columns yields a matrix which is no longer in this form. Thus any two maps in this form are equivalent if and only if they have the same specifications for the remaining variables, i.e.: the result provides an affine chart defined on a Zariski dense open subset of U_{d_{1},...,d_{p}}.

Since, each column of degree d_{i} polynomials has (d_{i} + 1)(m + p) coefficients, the total number of parameters we started with was (p + q)(m + p) = mp + q(m + p) + p^{2}. Finally the algorithm specifies the p diagonal constant coefficients to 1 and introduces at least two zeros for each ordered pair i < j. In fact the number of zeros introduced is 2 if d_{i} = d_{j} or 1 + d_{j} − d_{i} otherwise. Rewriting this last number as 2 + (d_{j} − d_{i} − 1) and adding up over all \frac{p(p−1)}{2} ordered pairs 1 ≤ i < j ≤ p we find that the number of parameters specified is p^{2} + ∑_{i<j} max(d_{j} − d_{i} − 1, 0). The conclusion of the lemma now follows since the choice of column degrees specified is the only way to choose the d_{i}’s so that they add up to q and no two differ from each other by more than 1. □

The normal form used above was easy to define for general U_{d_{1},...,d_{p}}, and was used in [46] where they use the U_{d_{1},...,d_{p}} as cells in a cellation of the space of degree q maps. For our purposes we need only work in the largest of these cells U_{d,...,d,d+1,...,d+1}. Since this cell has dimension mp + q(m + p) and each root of the degree n + q characteristic equation (17) enforces one polynomial condition on the space of degree q maps we will expect no solutions whenever n is greater than the critical degree mp + q(m + p) − q and a finite number of solutions when n = mp + q(m + p) − q. In both cases we expect no solutions to a generic dynamic pole placement problem to lie on these lower-dimensional pieces. In order to work on U_{d,...,d,d+1...,d+1}, however we will want to use a different normal form analogous to the form used in Section 3. To describe it we start by identifying (m + p)-vectors of degree d polynomials with their (m + p)(d + 1)-element coefficient vectors as follows:

[ a_{1}^{0} + a_{1}^{1}s + ⋯ + a_{1}^{d}s^{d} ; a_{2}^{0} + a_{2}^{1}s + ⋯ + a_{2}^{d}s^{d} ; ⋮ ; a_{m+p}^{0} + a_{m+p}^{1}s + ⋯ + a_{m+p}^{d}s^{d} ] ⇔ [ a_{1}^{0} ; a_{2}^{0} ; ⋮ ; a_{m+p}^{0} ; a_{1}^{1} ; ⋮ ; a_{m+p}^{1} ; ⋮ ; a_{1}^{d} ; ⋮ ; a_{m+p}^{d} ]  (18)

i.e.: the coefficient a_{j}^{k} of s^{k} in polynomial entry in row j in the representation on the left is stored in the ((k + 1)(m + p) + j)-th position in the representation on the right.

Definition 16 Let q = dp + r with d, r ∈ ℕ and r < p. A localization pattern for (m + p) × p maps of degree q is given by a table of of p columns of zeros and stars, where the first p − r columns have dimension (d + 1)(m + p) and the remaining columns have dimensions (d + 2). As in the degree 0 case all stars within a column should be contiguous and the row indices in which the bottom-most and top most stars occur strictly increase as a function of the column index. These row indices are called the top and bottom pivots respectively. It is further required that no two top (bottom) pivots differ by m + p or more. We say that a map fits a localization pattern if it is equivalent to a map given by a matrix of polynomials with the column degrees specified by the pattern and zero coefficients everywhere the pattern requires them.

The dimension of the space of degree q maps which meet a localization pattern X with n stars is n − p. To see this note that the requirements that no pivots differ by m + p places ensures that no multiple of any column by a power of s has a bottom most star in a pivot row of any other column. This implies that it any linear combination involving more than one column has the lowest bottom most pivots and highest topmost pivots of the columns used. Thus only by scaling each column can we change the entrees of a generic map fitting a localization pattern without producing a map which no longer fits that pattern. On the other hand we may freely scale each column to set one non-zero entry to one. This also tells us that patterns with two equal pivots or pivots that differ by m + p or more will be fit by a space of dimension lower than n − p.

Given appropriate generality we can use invertible column operations to transform the normal form for U_{d,...,d,d+1,...,d+1} into a localization pattern as follows: First we allow each column to be arbitrarily scaled and thus turn all ones into stars. Next, we use column operations with constant scalars on the first block of p − r dimension (d + 1)(m + p) columns to move all the zeros below the diagonal to the bottom of the columns. We then use multiples of these columns by s to introduce p − r rows of zeros to the tops of the block or r (d + 2)(m + p)-dimensional columns. Finally we can use scalar column operations on this block to move the below diagonal elements of the normal form to the bottoms of the columns. This process is illustrated in Figure 7, and by counting diagonally in each block we see that the resulting localization pattern has top pivots [1, 2, …, p] and bottom pivots [d(m+p)+m+r+1, …, d(m+p)+m+p, (d+1)(m+p)+m+1, …, (d+1)(m+p)+m+1+r].

We thus see that set of maps which fit this localization pattern has dimension mp + q(m + p) and will account for all solutions of the problem of finding degree q maps meeting mp + q(m + p) generic m-planes at mp + q(m + p) specified s values. In analogy to the approach used in Section 3 we will proceed by successively specializing the input planes to yield problems over smaller localization patterns involving fewer conditions.

[^{1} ^{0} ^{0} ^{0} ^{0}^{0} ^{1} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{1} ^{0} ^{0}^{⋆} ^{⋆} ^{0} ^{1} ^{0}^{⋆} ^{⋆} ^{0} ^{0} ^{1}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{0} ^{0} ^{0}^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆} ] U_{0,0,1,1,1}  ⇔ ^{[^{⋆} ^{0} ^{0} ^{0} ^{0}^{0} ^{⋆} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆} ^{0} ^{0}^{⋆} ^{⋆} ^{0} ^{⋆} ^{0}^{⋆} ^{⋆} ^{0} ^{0} ^{⋆}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{0} ^{0} ^{0}^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆} ]} step 1  ⇔ ^{[^{⋆} ^{0} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆} ^{0} ^{0}^{⋆} ^{⋆} ^{0} ^{⋆} ^{0}^{⋆} ^{⋆} ^{0} ^{0} ^{⋆}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{0} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{0} ^{0} ^{0}^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆} ]} step 2  ⇔ ^{[^{⋆} ^{0} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆} ^{0} ^{0}^{⋆} ^{⋆} ^{0} ^{⋆} ^{0}^{⋆} ^{⋆} ^{0} ^{0} ^{⋆}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{0} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{0} ^{0} ^{0}^{0} ^{0} ^{0} ]} step 3  ⇔ ^{[^{⋆} ^{0} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{0} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆} ^{0} ^{0}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{0}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{0} ^{⋆} ^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{⋆} ^{⋆} ^{⋆}^{0} ^{⋆} ^{⋆}^{0} ^{0} ^{⋆}^{0} ^{0} ^{0}^{0} ^{0} ^{0} ]} [6, 7, 10, 11, 12]

Figure 7: Transforming standard form for m = 2, p = 5 and q = 3 to top level localization pattern.

When specializing the input planes, we also must specialize the values for s by fixing the interpolating points. For bottom pivots we focus on the highest-degree coefficients and move s to ∞ to select those coefficients. For top pivots the lowest-degree coefficients are specialized and we move s to 0. To deal with both situations we add an additional variable t to homogenize the polynomials. So we consider localization patterns of homogeneous polynomials and denote those by X(s, t). The special m-planes of the hypersurface Pieri case are recycled when we evaluate X(s, t) at (s, t) = (1, 0) for bottom pivots, or at (s, t) = (0, 1) for top pivots. The solutions to the problem in special position can be found in the child patterns that differ from X(s, t) in exactly one position, The analogue to Definition 3 is immediate. The main root-counting theorem follows from the correctness of the Pieri homotopies.

Theorem 17 Consider a localization pattern X(s, t) with p + n stars. For n = 0, X(s, t) counts for one solution. For n > 0, the number of maps fitting X(s, t) and meeting n general m-planes at n values for (s, t) equals the sum of the number of solution maps fitting the children of X(s, t) and meeting n − 1 general m-planes at n − 1 values for (s, t).

Note that in the definition of the Pieri homotopies we abuse notation in the sense that t denotes both the continuation parameter and the added variable to homogenize the maps. This abuse is justified for bottom pivots because we move t from 0 to 1 to move the interpolation point from its specific value (s, t) = (1, 0) at ∞ to a general value (s, t) = (s_{n}, 1). For top pivots we swap the roles of s and t to keep up with this abuse.

Definition 18 Let X(s, t) be a localization pattern and S_{X} be the special m-plane for bottom pivots at (s, t) = (1, 0). Suppose that the children Y (s, t) of X(s, t) meet n − 1 general m-planes L_{i} at (s_{i}, t_{i}), i.e.: det(Y (s_{i}, t_{i})|L_{i}) = 0, for i = 1, 2, …, n − 1. To satisfy the nth intersection condition with L_{n} at (s_{n}, t_{n}), the Pieri homotopy is defined as

H(X(s, t), s, t) = \{ \begin{matrix}det(X(s, t)|(1 − t)S_{X} + tL_{n}) = 0 \\ (s − 1)(1 − t) + (s − s_{n})t = 0 \\ det(X(s_{i}, t_{i})|L_{i}) = 0 & i = 1, 2, …, n − 1 \end{matrix} t ∈ [0, 1]. (19)

[figure: [1 2]; 1; [2 3]; 1; [3 4]; 2; [4 5]; 4; n = 0; n = 1; n = 2; n = 3; n = 4; n = 5; n = 6; n = 7; n = 8; [1 3]; 1; [2 4]; 2; [3 5]; 4; [4 6]; 8; [1 4]; 1; [2 5]; 2; [3 6]; 4; [4 7]; 8; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

Figure 8: Combinatorial root count for p = 2 = m, q = 1. The brackets at the left are the bottom pivots. The top pivots remain [1 2]. The trivial localization pattern X_{0}(s, t) corresponds to [4 7]. The dashed line marks the transition between q = 0 and q = 1. The root count is at the right.

For top pivots we swap s ↔ t and consider s_{n}^{−1} as target value for s. When we remove entries from both top and bottom, two independent s-variables are used. Theorem 17 follows from the correctness of the Pieri homotopy, proven in Lemma 19.

Lemma 19 Consider a localization pattern X(s, t) with p + n stars and n complex m-planes L_{i} in general position at the values (s_{i}, t_{i}). Suppose we are given all maps that meet L_{i} at (s_{i}, t_{i}), i = 1, 2, …, n − 1 and fit one of the children of X(s, t). Then the Pieri homotopy defines regular solution paths as t varies from 0 to 1, that start at the given maps and end at those maps that meet all n general m-planes L_{i} at (s_{i}, t_{i}) while fitting X(s, t).

Proof. Observe that in the Pieri homotopy (19) at (s, t) = (1, 0) we select in the first equation with the special m-plane S_{X} in the expansion of det(X(1, 0)|S_{X}) = 0 those stars that are indexed by the bottom pivots. So the first equation in (19) looks like

H_{1}(X(s, t), s, t) = p(X(1, 0)) + t(f(X(s, t), s, t) + O(t)),  (20)

where p(X(1, 0)) denotes the product of all pivot stars and where f(X(s, t), s, t) is a polynomial not divisible by t. Ordering the variables as (s, t, x_{ij}), the matrix of all partial derivatives of the homotopy has the following structure:

[ \begin{matrix}\frac{∂H_{1}}{∂s} & \frac{∂H_{1}}{∂t} & A \\ 1 & 1 − s_{n} & B \\ 0 & 0 & C \end{matrix} ] .  (21)

Since the n − 1 planes L_{i} are in general position, rank(C) = n − 1. So the Jacobian matrix (21) if of full rank if and only if \frac{∂H_{1}}{∂s} \frac{∂H_{1}}{∂t} ≠ 0 at (s, t) = (1, 0), We can show that f(X(1, 0), 1, 0) ≠ 0, which implies \frac{∂H_{1}}{∂t} ≠ 0. If f(X(1, 0), 1, 0) = 0, then this would imply that f(X(s, t), s, t) ≡ 0 and H_{1} would then not contain any term that is linear in t, which could only be so for very special choices of L_{n}. Hence at (s, t) = (1, 0), all solutions are regular.

To compactify our space we choose again a multi-homogenization according to the columns of the matrices. The regularity of the homotopy is maintained as t moves to 1 as L_{n} is in general position. Suppose we would have more solutions at (s, t) = (s_{n}, 1) than the number of paths we have started with. Going backwards, when in the Pieri homotopy we let t go from 1 to 0, we would arrive at solutions at (s, t) = (1, 0) that do not fit any of the child patterns of X(s, t). But any other child pattern that is not provided in the root count does not allow enough freedom to meet the general intersection conditions L_{i} at (s_{i}, t_{i}) for i = 1, 2, …, n − 1. □

6 Computational Experiments and Experiences

The Pieri homotopy algorithm is part of the module of PHCpack [43] that also provides the SAGBI homotopies. We compare with those homotopies and give comments on the organization of the code, numerical aspects, and applications. All timings reported concern a 166 MHz Pentium II processor with 64 Mb internal memory running Linux, unless indicated otherwise.

6.1 Implementation Issues

In setting up the Pieri homotopy algorithm, we restricted to the case where the input planes are all in general position. In this case, all the deformations are free from multiplicities. To solve a nongeneric, specific instance of the problem instance we first solve a generic case and then apply a cheater’s homotopy to obtain solutions to the original problem. The paradigm of cheater’s homotopy ([20], [21]) or coefficient-parameter polynomial continuation ([25], [26]) makes it straightforward to set up this homotopy. This paradigm ensures that singularities can only occur at the end of the solution paths, and only when the original problem has singular solutions.

The general intersection conditions are represented by overdetermined polynomial systems. A direct method to solve an overconstrained polynomial system of N equations in n unknowns is to multiply it by an n-by-N matrix of random complex numbers to construct a square system, as is proposed in [36]. This reduction to a square system destroys the geometric structure and creates many excess solution paths to follow. In our situation, the overdetermined polynomial systems we have to deal with are the Pieri homotopies for general intersection conditions, which are overdetermined homotopies. From the geometry we know which solution paths we have to follow so that we maintain the optimal number of solution paths, see [16, Section 4]. To control the correctness and to detect numerical failures, we evaluate the original overconstrained system at the computed end points of the paths. The complexity of Newton’s method and path-following algorithms for overdetermined systems is analyzed in [9].

The geometric intersection conditions treated in Section 4 are expressed by determinantal equations, which are a special kind of polynomial systems. Just as sparse polynomial systems allow fewer perturbations on the coefficient structure than general polynomial systems (whence they have a better numerical condition [8] and can be solved easier), we expect that the polynomial systems arising from these geometric intersection conditions are numerically easier to solve. We have done some tests on working directly with the matrix structures, but abandoned this approach because the general linear algebra operations turn out to be slower than the nested Horner schemes that are used to evaluate the expanded determinantal forms. Nevertheless, we expect computational progress from Newton’s method adapted to this specific geometric situation [11], in combination with secant methods [48].

6.2 Computational and numerical experiments

The description in [16] leads to path following in a chain-by-chain fashion as defined by Pieri trees. Contemplating the posets in Figures 3 and 4 one sees that one can avoid the tracing of many solution paths when the continuation matches the poset structure. To solve a generic complex instance encoded by (m, p) = (4, 3), the chain-by-chain Pieri algorithm takes 4 h 15 m 58 s 220 ms and has to trace 2310 solution paths. The new poset-oriented Pieri homotopies only take 1 h 7 m 20 s 160 ms (see Table 1) to trace 1663 paths. This savings are only partially explained by the reduction in the number of paths. The poset structure allows to organize the symbolic homotopy constructors in a much more economical way.

In Table 1 we summarize the computational results, when the pivoting is done in a mixed fashion, removing from both top and bottom pivots, as in the chain-by-chain original description in [16]. The real target system solved is generated taking the 4-planes osculating a rational normal curve, as prescribed in one of the Shapiro-Shapiro conjectures ([32], [39], [44]) for which all solution 3-planes are expected to be real. Dividing the total time on the last line in Table 1 by 462, we arrive at 48 s 476 ms cpu time as cost per solution.

n #paths  user cpu time
2  18  800 ms
4  72  6 s 918 ms
6  187  1 m 8 s 40 ms
8  462  8 m 27 s 460 ms
10  462  18 m 46 s 390 ms
12  462  38 m 42 s 360 ms
total 1663 1 h 7 m 20 s 160 ms
target  462 5 h 4 m 46 s 610 ms
total 2125 6 h 13 m 15 s 840 ms

Table 1: Number of paths and timings for (m, p) = (4, 3) at every even level n, up to the total resolution time for a generic complex intersection problem. The first total is added to the time needed for solving a real target instance and results in the last line.

Note that one can change basis to bring two input 4-planes into special position, which annihilates the time on stage n = 12 in Table 1. The other optimization consists in using linear algebra instead of continuation to satisfy the intersection conditions at the top level of the poset, see [16, Proposition 3.1]. But this optimization only cuts off milliseconds.

The input planes are represented by matrices of generators which are equivalent up to a transformation of basis. We have experienced that an orthonormal representation of the input planes – filtered through the QR-algorithm [14] – is responsible for considerable computational savings and an increased numerical accuracy of the solution planes. Especially for higher-dimensional problems, the difference between random and orthonormal inputs becomes significant. For instance, the case (m, p) = (5, 3) leads to a fifteen-dimensional polynomial system of cubics with 6006 solutions. A 450MHz Intel Pentium machine needs 16 h 17 m 16 s cpu time on random inputs, whereas it only takes 10 h 12 m 38 s on orthonormal input planes.

6.3 Comparison with SAGBI Homotopies

The SAGBI homotopies were proposed in [16] to compute all p-planes that meet mp given m-planes in general position. The second author implemented those homotopies to verify large instances of the Shapiro-Shapiro conjectures. See [44] for a description and [32] and [39, 41] for other tests and related work on these conjectures.

To solve a generic complex instance, encoded by (m, p) = (4, 3), the Pieri homotopy algorithm takes 1 h 7 m 20 s 160 ms (see Table 1). As reported in [44], SAGBI homotopies need for the same problem 2 h 23 m 27 s 630 ms with localization patterns that lead to polynomials of lowest degree, and 5 h 23 m 36 s 840 ms with localization patterns as used by Pieri homotopies. The common optimization of bringing two input planes into special position to diminish the dimension with two forces those localization patterns that lead to higher-degree polynomials, increasing the complexity of SAGBI homotopies.

SAGBI homotopies suffer from two drawbacks, not shared by the Pieri homotopies. Firstly, they cannot solve the more general intersection problem treated in Section 4. Secondly, a polyhedral continuation is needed to start up the SAGBI homotopies. These continuations happen in the top dimension, which makes them computationally intensive. In addition, these homotopies are both highly nonlinear in the continuation parameter, which leads to numerical instabilities as the problems get larger. Although the techniques in [12] help, there is always a lower bound that may be too high for the machine precision.

To conclude the comparison, we contrast the analytic geometry as used in the SAGBI homotopies with the intrinsic geometry of the Pieri homotopies. With the SAGBI homotopies we loose all geometric information after the transformation of the problem into a polynomial system. The Pieri homotopies use the polynomial equations merely as a means to compute and are more flexible to exploit the evolving geometry.

7 Conclusions

In this paper we developed numerical homotopy algorithms to resolve some classical problems in enumerative geometry. We share the optimism expressed in [16] that other geometric situations will have similarly nice solutions.

The Pieri homotopies arose from the question [37, 38] whether a problem of enumerative geometry can have all its solutions real. The developed software may be useful to verify instances of similar nature as the Shapiro-Shapiro conjectures. Note that for the quantum Schubert calculus a counterexample to one of the analogues was given in [40] for the case q = 1, m = 2 = p.

Lastly, a novel result in this paper is the translation of the geometric description of the dynamic pole placement problem [31], [29], into an effective algorithm with a numerical implementation. The modification to general intersection conditions, i.e.: (m + 1 − k_{i})-planes instead of m-planes is a straightforward programming exercise.

Acknowledgments. We are indebted to Frank Sottile for the many explanations that helped us through the first implementation and for the hint that Pieri homotopies exist for the quantum Schubert calculus. The explanations of Joachim Rosenthal were most helpful. We thank MSRI for the opportunity of sharing an office for one full year.

References

[1] E.L. Allgower and K. Georg. Numerical Continuation Methods, an Introduction, volume 13 of Springer Ser. in Comput. Math. Springer–Verlag, Berlin Heidelberg New York, 1990.

[2] E.L. Allgower and K. Georg. Numerical Path Following. In P.G. Ciarlet and J.L. Lions, editors, Techniques of Scientific Computing (Part 2), volume 5 of Handbook of Numerical Analysis, pages 3–203. North-Holland, 1997.

[3] S. Ariki. Generic pole assignment via dynamic feedback. SIAM J. Control and Optimization, 36(1):379–390, 1998.

[4] A. Bertram. Quantum Schubert calculus. Adv. Math., 128(2):289–305, 1997.

[5] R.W. Brockett and C.I. Byrnes. Multivariate Nyquist criteria, root loci, and pole placement: a geometric viewpoint. IEEE Trans. Automat. Control, 26:271–284, 1981.

[6] C.I. Byrnes. Pole assignment by output feedback. In H. Nijmacher and J.M. Schumacher, editors, Three Decades of Mathematical Systems Theory, volume 135 of Lecture Notes in Control and Inform. Sci., pages 13–78. Springer–Verlag, Berlin, 1989.

[7] D.A. Cox and S. Katz. Mirror Symmetry and Algebraic Geometry, volume 68 of Mathematical Surveys and Monographs. AMS, Providence, R.I., 1999.

[8] J.-P. Dedieu. Condition number analysis for sparse polynomial systems. In F. Cucker and M. Shub, editors, Foundations of Computational Mathematics, pages 75–101. Springer, 1997.

[9] J.P. Dedieu and M. Shub. Newton and predictor-corrector methods for over-determined systems of equations. IBM Technical Report, IBM Research Division, 1998. To appear in Math. Comp.

[10] D.F. Delchamps. State Space and Input-Output Linear Systems. Springer–Verlag, Berlin, 1988.

[11] A. Edelman, T. Arias, and S.T. Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl., 20(2):303–353, 1998.

[12] T. Gao, T.Y. Li, J. Verschelde, and M. Wu. Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods. To appear in Applied Math. Comput.

[13] I. Gohberg, M.A. Kaashoek, and F. van Schagen. Partially Specified Matrices and Operators: Classification, Completion, Applications, volume 79 of Operator Theory, Advances and Applications. Birkhäuser, Boston, 1995.

[14] G. Golub and C. Van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore and London, third edition, 1996.

[15] W.V.D. Hodge and D Pedoe. Methods of Algebraic Geometry, Volume 2. Cambridge University Press, 1994. Paperback reprint of the 1952 edition.

[16] B. Huber, F. Sottile, and B. Sturmfels. Numerical Schubert calculus. J. of Symbolic Computation, 26(6):767–788, 1998.

[17] T. Kailath. Linear Systems. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980.

[18] S. Kleiman and D. Laksov. Schubert calculus. American Mathematical Monthly, 79(10):1061– 1082, 1972.

[19] T.Y. Li. Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numerica, 6:399–436, 1997.

[20] T.Y. Li, T. Sauer, and J.A. Yorke. The cheater’s homotopy: an efficient procedure for solving systems of polynomial equations. SIAM J. Numer. Anal., 26(5):1241–1251, 1989.

[21] T.Y. Li and X. Wang. Nonlinear homotopies for solving deficient polynomial systems with parameters. SIAM J. Numer. Anal., 29(4):1104–1118, 1992.

[22] A. Morgan. Solving polynomial systems using continuation for engineering and scientific problems. Prentice-Hall, Englewood Cliffs, N.J., 1987.

[23] A. Morgan and A. Sommese. Computing all solutions to polynomial systems using homotopy continuation. Appl. Math. Comput., 24(2):115–138, 1987.

[24] A. Morgan and A. Sommese. A homotopy for solving general polynomial systems that respects m-homogeneous structures. Appl. Math. Comput., 24(2):101–113, 1987.

[25] A.P. Morgan and A.J. Sommese. Coefficient-parameter polynomial continuation. Appl. Math. Comput., 29(2):123–160, 1989. Errata: Appl. Math. Comput. 51:207(1992).

[26] A.P. Morgan and A.J. Sommese. Generically nonsingular polynomial continuation. In E.L. Allgower and K. Georg, editors, Computational Solution of Nonlinear Systems of Equations, pages 467–493, Providence, R.I., 1990. AMS.

[27] M. Pieri. Formule di coincidenza per le serie algebriche ∞^{n} di coppie di punti dello spazio a n dimensioni. Rend. Circ. Mat. Palermo, 5:252–268, 1891.

[28] M.S. Ravi and J. Rosenthal. A smooth compactification of the space of transfer functions with fixed McMillan degree. Acta Applicandae Mathematicae, 34:329–352, 1994.

[29] M.S. Ravi, J. Rosenthal, and X. Wang. Dynamic pole placement assignment and Schubert calculus. SIAM J. Control and Optimization, 34(3):813–832, 1996.

[30] M.S. Ravi, J. Rosenthal, and X. Wang. Degree of the generalized Plücker embedding of a quot scheme and quatum cohomology. Math. Ann., 311:11–26, 1998.

[31] J. Rosenthal. On dynamic feedback compensation and compactifications of systems. SIAM J. Control and Optimization, 32(1):279–296, 1994.

[32] J. Rosenthal and F. Sottile. Some remarks on real and complex output feedback. Systems and Control Lett., 33(2):73–80, 1998. See http://www.nd.edu/~rosen/pole for a description of computational aspects of the paper.

[33] J. Rosenthal and J. C. Willems. Open problems in the area of pole placement. In V.D. Blondel, E.D. Sontag, M. Vidyasagar, and J.C. Willems, editors, Open Problems in Mathematical Systems and Control Theory, Communication and Control Engineering Series, pages 181–191. Springer–Verlag, Berlin, 1998.

[34] H. Schubert. Kalkül der abzählenden Geometrie. Teubner, Leipzig, 1879.

[35] H. Schubert. Beziehungen zwischen den linearen Räumen auferlegbaren charakteristischen Bedingungen. Math. Ann., 38:588–602, 1891.

[36] A.J. Sommese and C.W. Wampler. Numerical algebraic geometry. In J. Renegar, M. Shub, and S. Smale, editors, The Mathematics of Numerical Analysis, volume 32 of Lectures in Applied Mathematics, pages 749–763, 1996. Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah.

[37] F. Sottile. Enumerative geometry for real varieties. In J. Kollár, R. Lazarsfeld, and D. R. Morrison, editors, Algebraic Geometry - Santa Cruz 1995 (University of California, Santa Cruz, July 1995), volume 62, Part I of Proceedings of Symposia in Pure Mathematics, pages 435–447. AMS, 1997.

[38] F. Sottile. Pieri’s formula via explicit rational equivalence. Can. J. Math., 49(6):1281–1298, 1997.

[39] F. Sottile. Real Schubert calculus: polynomial systems and a conjecture of Shapiro and Shapiro. Preprint #1998-066, MSRI, 1998. Accepted for publication in Experimental Mathematics.

[40] F. Sottile. Real rational curves in Grassmannians. Preprint #1999-025, MSRI, 1999.

[41] F. Sottile. The special Schubert calculus is real. Electronic Research Announcements of the AMS, 5:35–39, 1999. Available at http://www.ams.org/era.

[42] R.P. Stanley. Some combinatorial aspects of the Schubert calculus. In D. Foata, editor, Combinatoire et Représentation du groupe symétrique, Strasbourg, 1976, volume 579 of Lecture Notes in Mathematics, pages 217–251. Springer–Verlag, Berlin, 1977.

[43] J. Verschelde. PHCpack: A general-purpose solver for polynomial systems by homotopy continuation. Accepted for publication in ACM Trans. Math. Softw.. Paper and software available at the author’s web-pages.

[44] J. Verschelde. Numerical evidence for a conjecture in real algebraic geometry. Preprint #1998-064, MSRI, 1998. Accepted for publication in Experimental Mathematics. Paper and software available at the author’s web-pages.

[45] X Wang, M.S. Ravi, and J. Rosenthal. Algebraic and combinatorial aspects of the dynamic pole assignment problem. In U. Helmke, R. Mennicken, and J. Saurer, editors, Systems and Networks: Mathematical Theory and Applications, volume 79 of Mathematical Research, pages 547–550. Akademie Verlag, Berlin, 1994. Proc. of the International Symposium MTNS 93 held in Regensburg Germany. Vol II: Invited and contributed papers.

[46] X Wang and J. Rosenthal. A cell structure for the set of autoregressive systems. Linear Algebra and its Applications, 205–206:1203–1225, 1994.

[47] J.C. Willems. Paradigms and puzzles in the theory of dynamical systems. IEEE Transactions on Automatic Control, 36(3):259–294, 1991.

[48] J.C. Yakoubsohn. Finding zeros of analytic functions: α-theory for secant type methods. To appear in J. Complexity.

[49] H.G. Zeuthen. Lehrbuch der abzählenden Methoden der Geometrie, volume XXXIX of Lehrbücher der mathematischen Wissenschaften. Teubner, Leipzig, 1914.