5.4 Polynomial eigenvalue problems
5.5.3 Modifications of specialized resultant based method
We conclude this section with a discussion of some modifications of the presented specialized resultant based method for solving systems of polynomial equations, especially its offline phase, where we transform a system of polynomial equations to PEP (5.44).
The specialized resultant based method, which was presented in this section and which uses hidden variable resultants and polynomial eigenvalue problems, doesn’t work for all systems of polynomial equations. It is because the Modified Macaulay based method for transforming a system of polynomial equations to PEP (5.44) doesn’t result for all systems in their polyno-mial eigenvalue formulations. However, this Modified Macaulay based method is very simple, intuitive an we found it working for most of the problems discussed later in the text.
In this subsection we present some alternative methods that can be used to transform the initial system of polynomial equations to PEP (5.44).
The first method is only a small modification of the Modified Macaulay based method pre-sented in Section 5.5.1. As we have already mentioned, the Modified Macaulay based method from Section 5.5.1 may sometimes generate less linearly independent polynomial equations than monomials in these equations (after hiding one variable in the coefficient field). However, this may not always be a problem. It is because it may happen that between these polynomial equa-tions there existimonomials which are contained only in j < ipolynomials. Therefore after removing these j polynomials we will remove less polynomials than monomials. If we are lucky then after removing them we will obtain as many or more polynomials than monomials contained in these polynomials, and therefore we can formulate these equations as PEP (5.44).
This removing of polynomials is exactly what is done in Algorithm 12 used in the second step of the presented offline phase. Therefore, sometimes, even if we do not obtain a polynomial eigenvalue formulation in the first step of the offline phase, we can continue with the second step, i.e. with the removing of unnecessary polynomials, and we can still obtain PEP (5.44).
If we still do not obtain a polynomial eigenvalue formulation of the initial system of polyno-mial equations we can increase the degreedof generated polynomials and try if this helps.
We end this section with a method for transforming a system of polynomial equations to PEP (5.56) that is somewhat more complicated than the , but that is general and works for all systems of polynomial equations.
In the Modified Macaulay based method from Section 5.5.1 we generate new polynomials only by multiplying initial polynomials by monomials of some degree. In this way we are not able to generate all polynomials from the ideal.
Therefore, to generate polynomials from the ideal, we can use a method which is similar to the one used to generate polynomials in the specialized Gr¨obner basis method presented in Section 4.4.3. In Section 4.4.3 we have presented two different strategies for generating polynomials from the ideal, i.e. the single elimination and the multiple elimination strategy. For the purpose of the specialized resultant based method it is better to use the multiple elimination strategy. It is because using multiple elimination strategy, the number of generated monomials grows slower than in the case of a single G-J elimination and that is what we want.
The multiple elimination strategy starts with the initial polynomials (5.55) and then systemat-ically generates new polynomials from the ideal by multiplying all new generated polynomials
of degree< dby all individual variables and reducing them each time by G-J elimination. After each G-J elimination, we can check if we already have a polynomial eigenvalue formulation. If no new polynomials of degree< d were generated and no polynomial eigenvalue formulation was obtained, then we increase the degreed.
By checking if we already have a polynomial eigenvalue formulation we mean checking if there existsipolynomials containingj≤imonomials between already generated polynomials.
We can do this either by the removing procedure presented in the previous section 5.5.1 or directly by trying all subsets of the generated polynomials. This verification is not expensive, since it needs to be done only once in the offline phase, and we do not need to know coefficients of the generated polynomials.
6 problems solvers
“Everything should be made as simple as possible, but not simpler.”
Albert Einstein
6.1 Introduction
Algebraic solvers based on Gr¨obner bases have been used recently to solve many computer vision problems [134, 132, 135, 136]. These Gr¨obner basis solvers were mostly designed for particular problems and in general consisted of three key steps.
In the first step of these solvers [134, 132, 135, 136], the particular problem was solved using a computer algebra system, e.g. Macaulay 2 or Maple, for several usually random coefficients from a finite field of the input systemF representing considered instances of this particular problem. This was done using a general technique for solving systems of polynomial equations by finding a Gr¨obner basis of the ideal generated by the initial polynomialsF [39]. In this phase, the basic parameters of the considered instances of the problem were also identified, such as how many solutions the problem has, and how “hard” is it to obtain the Gr¨obner basis, and which leading monomials it contains. This procedure was usually automatic and relied on general algorithms of algebraic geometry such as Buchberger’s algorithm [18] or F4 algorithm [49].
In the second step, a special elimination procedure, a special “elimination template”, similar to an admissible Elimination trace presented in Section 4.4.3, was in all these solvers designed.
This elimination procedure determined which polynomials from the ideal should be added to the initial polynomial equations and how they should be eliminated to obtain a complete Gr¨obner basis or at least all polynomials needed for constructing a multiplication matrix and thus solving the initial equations.
The goal of this step was to obtain a computationally efficient and numerically robust proce-dure for solving all systems in the form of the “representing system”F. Until now, this step has been mainly manual, requiring to trace a path toward a Gr¨obner basis for some coefficient from a finite field, checking redundancies and possible numerical pitfalls, and writing down a program in a procedural language such as Matlab or C.
In the last step, an efficient solver for solving all considered instances of the particular prob-lem, i.e. all systems of polynomial equations in the form of the input system, was created accord-ing to the constructed “elimination template”. The template was used to create a multiplication matrix (4.44). The solutions to the original problem were obtained numerically as eigenvalues or eigenvectors of this matrix.
The first and the third step are standard and well understood and are in fact very similar in all these solvers including all our solvers presented in this thesis.
It is the second step which involves considerable amount of craft and which makes the process of solver generating rather complex and virtually impenetrable for a non-specialist. Moreover, for some problems it isn’t clear how their “elimination templates” were generated and therefore non-specialists often use them as black boxes, they often are not able to reimplement them, improve them, or create similar solvers for their own new problems.
On the other hand, the method for generating admissible Elimination traces presented in Sec-tion 4.4.3 can be easily automated and used also by non-specialists and without any knowledge of algebraic geometry. Therefore, in this chapter we present an automatic generator of admis-sible Elimination traces for Gr¨obner basis solvers, or in fact a generator of efficient specific Gr¨obner basis solvers for systems of polynomial equations in the form of some input systemF.
We have to accept that there is no hope to obtain an efficient and robust solver for completely general systems of polynomial equations since the general problem is known to be EXPSPACE complete [82]. On the other hand, many camera geometry problems share the property that the Elimination trace associated with their solution is the same for all interesting configurations of coefficients of the particular problem, i.e. all interesting instances of the problem are in the form of one “representing system”F, see Definition 20. Moreover, this Elimination trace is usually quite simple and can be efficiently implemented.
Consider, for instance, the classical 5-point relative pose problem, i.e. the problem of esti-mating the essential matrix from five image point correspondences [112, 132]. In general, an admissible Elimination trace used to solve this 5-point problem depends on actual image coordi-nates measured. Fortunately, for “non-degenerate” image correspondences, i.e. for those which are not collinear or coincide and which lead to a finite number of essential matrices, the Elimi-nation trace is always the same, see Example 21. Therefore, it is enough to find an admissible Elimination trace for one particular “non-degenerate” configuration of coefficients and then use the same trace for all “non-degenerate” configurations of coefficients, i.e. all “non-degenerate”
instances of the 5-point problem. Elimination traces for “degenerate” configurations of coeffi-cients may be very different and there may be very many of them. However, in practice we do not need to consider them.
In this chapter we propose an automatic generator that is based on the specialized Gr¨obner basis method presented in Section 4.4 and that searches for an admissible Elimination trace for a given system of polynomial equationsF. Using this admissible Elimination trace the automatic generator produces an efficient solver for all instances of the input problem that would lead to the same Elimination trace, i.e. all systems of polynomial equations in the form of the input systemF. There is a number of valid traces, i.e. valid paths, the generator can find. The choice of the particular trace, is determined by the particular coefficients ofF.
The input to our automatic generator is a system of polynomial equationsF with concrete coefficients fromZp. A particular choice of coefficients determines the Elimination trace and the set of “consistent” instances ofF for which this trace is admissible, see Definition 21. For many problems, the interesting “regular” solutions can be obtained with almost any, i.e. random, choice of coefficients of the “representing system”F. Therefore, we use random values from Zp as default coefficients.
The output of the automatic generator is the Matlab or Maple code that returns solutions of all systems of polynomial equations in the form of the input systemF, with concrete coefficients fromQ. During the online computations, only the resulting solver is called.
Next we describe all steps of the automatic generator in more detail and in Chapter 7 we demonstrate that this automatic generator constructs efficient and numerically stable solvers that are comparable or better than known manually constructed solvers in terms of computational time, space requirements, and numerical stability.