Bézout number calculations for multi-homogeneous polynomial systems. (English) Zbl 0759.65023
The concept of a multi-homogeneous system of polynomials was introduced by A. Morgan and A. Sommese [Appl. Math. Comput. 24, 101-113 (1987; Zbl 0635.65057)]. The Bézout number of such a multi-homogeneous system is the largest number of nonsingular solutions the system can have. It is also the number of solution paths needed to compute all geometrically isolated solutions by means of multi-homogeneous continuation.
This paper describes an efficient algorithm for evaluating Bézout numbers for \(m\)-homogeneous polynomial systems in \(n\) variables. In comparison with a basic algorithm the number of operations for the worst case, \(m=n\), is reduced from \((n-1)n!\) to \(n2^{n-1}\). The algorithm is used to find homogenizations with a minimal Bézout number by exhaustive testing. For this certain efficiencies are introduced and it is also noted that the exhaustive search can be easily parallelized.
This paper describes an efficient algorithm for evaluating Bézout numbers for \(m\)-homogeneous polynomial systems in \(n\) variables. In comparison with a basic algorithm the number of operations for the worst case, \(m=n\), is reduced from \((n-1)n!\) to \(n2^{n-1}\). The algorithm is used to find homogenizations with a minimal Bézout number by exhaustive testing. For this certain efficiencies are introduced and it is also noted that the exhaustive search can be easily parallelized.
Reviewer: W.C.Rheinboldt (Pittsburgh)
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 26C10 | Real polynomials: location of zeros |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
Keywords:
multi-homogeneous system of polynomials; Bézout number; multi- homogeneous continuation; homogenizationsCitations:
Zbl 0635.65057References:
| [1] | A. P. Morgan, Polynomial continuation and its relationship to the symbolic reduction of polynomial systems, in Proceedings of the Workshop on the Integration of Numerical and Symbolic Computing Methods; A. P. Morgan, Polynomial continuation and its relationship to the symbolic reduction of polynomial systems, in Proceedings of the Workshop on the Integration of Numerical and Symbolic Computing Methods |
| [2] | Garcia, C. B.; Zangwill, W. I., Global Continuation Methods for Finding All Solutions to Polynomial Systems of Equations in \(N\) Variables, Center for Math. Studies in Business and Economics Report No. 7755 (1977), Univ. Chicago · Zbl 0428.90085 |
| [3] | Brunovský, P.; Meravý, P., Solving systems of equations by bounded and real homotopy, Numer. Math., 43, 397-418 (1984) · Zbl 0543.65030 |
| [4] | Chow, S. N.; Mallet-Paret, J.; Yorke, J. A., A homotopy for locating all zeros of a system of polynomials, (Peitgen, H.-O.; Walther, H. O., Functional Differential Equations and Approximation of Fixed Points, Lecture Notes in Math. No. 730 (1979), Springer-Verlag: Springer-Verlag New York) · Zbl 0427.65034 |
| [5] | Li, T. Y., On Chow, Mallet-Paret and Yorke homotopy for solving system of polynomials, Bull. Inst. Math. Acad. Sinica, 11, 433-437 (1983) · Zbl 0538.65030 |
| [6] | Morgan, A. P., A homotopy for solving polynomial systems, Appl. Math. Comput., 18, 87-92 (1986) · Zbl 0597.65046 |
| [7] | Morgan, A.; Sommese, A., A homotopy for solving general polynomial systems that respects \(m\)-homogeneous structures, Appl. Math. Comput., 24, 101-113 (1987) · Zbl 0635.65057 |
| [8] | Morgan, A.; Sommese, A., Coefficient-parameter polynomial continuation, Appl. Math. Comput., 29, 123-160 (1989) · Zbl 0664.65049 |
| [9] | Wampler, C.; Morgan, A.; Sommese, A., Numerical continuation methods for solving polynomial systems arising in kinematics, J. Mech. Design, 112, 59-68 (1990) |
| [10] | C. Wampler, A. Morgan, and A. Sommese, Complete solution of the nine-point path synthesis problem for four-bar linkages, J. Mech. Design; C. Wampler, A. Morgan, and A. Sommese, Complete solution of the nine-point path synthesis problem for four-bar linkages, J. Mech. Design |
| [11] | Verschelde, J.; Haegemans, A., The BQ-Algorithm for the Construction of a \(m\)-Homogeneous Start System, Report TW 147 (1991), Dept. Comput. Sci., Katholieke Universiteit Leuven: Dept. Comput. Sci., Katholieke Universiteit Leuven Belgium |
| [12] | (Selby, S. M., CRC Standard Mathematical Tables (1971), The Chemical Rubber Company: The Chemical Rubber Company Cleveland, Ohio) |
| [13] | Wampler, C. W.; Morgan, A. P., Solving the \(6R\) inverse position problem using a generic-case solution methodology, Mech. Mach. Theory, 26, 91-106 (1991) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
