多项式优化的数值—符号混合算法
|
摘要
多项式优化是全局优化中的一个基本而重要的研究对象,很多源于控制理论、信号处理、计算机模拟等领域的问题都可以归结为多项式优化问题。数值算法和符号算法是两类求解多项式优化问题的方法。
符号算法处理的对象是抽象的数学符号与代数概念,计算是基于整数运算的,因此没有误差。但也正是因为没有舍入,方法的计算量特别是存储量很大,导致对于大规模的问题有本质性的困难。数值算法能够求解规模较大的问题,但是也面临着数值稳定性等棘手的问题。为了能够有效的发挥数值算法和符号算法各自的优点,数值-符号混合算法是受到关注的研究热点之一。Hanzon和Jibetean提出了一类求解多项式优化问题的混合算法,称之为矩阵算法。对于优化目标多项式,通过一阶条件将优化问题转化为多项式方程组并加入高次的项作为扰动,从而很容易计算出相应的Gr(o|¨)bner基,任何多项式均可以由这组基线性表示。这里线性表示的系数矩阵称为相伴矩阵,进而将问题转化为求解相伴矩阵的特征值和特征向量的问题。
在Hanzon-Jibetean算法中,相伴矩阵起到了核心的作用,但通常矩阵的规模非常大。本文提出了一类针对相伴矩阵的混合算法–改进矩阵算法。我们在一阶条件引出的多项式方程组与加入的高次扰动项之间建立匹配模型,通过优化两者之间的匹配关系,获得规模最小化的相伴矩阵,使得算法中相伴矩阵的规模明显降低,从而有效提升了算法的效率。
在此基础之上,本文又针对求解多项式优化驻点的一阶条件,给出了一类矩阵收缩算法,即加入一个新的变量和一个新的多项式方程,从而使得算法只需计算对应于新增添变量的特征值,即可求得该多项式的驻点。这一改进对于多项式优化问题提供了更进一步的支撑,使得运算效率得到大幅度的提高。
最后,本文给出了上述改进矩阵算法的一个应用,将其应用于多项式同伦系统,这一应用在一定程度上使得同伦跟踪系统的奇异解得以减少,也使得整个同伦跟踪算法更加有效。
The multivariate polynomial optimization is an important problem in the globaloptimization. It has applications in many areas of science and engineering, such ascontrol theory and signal processing. Numerical algorithm and symbolic algorithm arethe fundamental approaches for this problem.
Symbolic algorithm deals with mathematical symbols and algebra objects withouterror. However, this kind of method often leads to heavy duty of computation when thescale of the problem is large. Numerical algorithm, on the other hand, can solve largerproblem in general. It also faces problems, such as stability. Therefore numerical-symbolic hybrid method would be a natural consideration in order to take the advan-tages of both these two methods. Hanzon and Jibetean proposed matrix method, whichtransforms the optimization of multivariate polynomial to a polynomial system of equa-tions through the first order condition. The method can easily generate the Gr(o|¨)bnerbasis by adding high order leading terms, so that any polynomial can be represented bythese basis. Here the representing coefficient matrix is called associated matrix. Thenone can get the critical points of the objective polynomial through computing eigenval-ues and eigenvectors of the associated matrix.
Associated matrix plays an important role in Hanzon-Jibetean method. However,the scale of associated matrix is often large. In this dissertation we propose a newhybrid method, which is named as improved matrix method. We establish a matchingmodel between the added high order leading terms and polynomial equations arisingfrom the first order conditions. By optimizing this matching, we can get the minimalscale of the associated matrix, which would make the scale of the associated matrixsmaller and the algorithm more efficient.
At the same time, we propose a new matrix contractive algorithm by adding a newvariable and a new equation to the original first order conditions. In this method, weget the critical points of the objective polynomial through computing the eigenvalue ofthe new added variable only once. By this improvement, we can make the polynomialoptimization much faster.
As an application, we apply the improved matrix methods to constructing the startsystem for the homotopy method. Numerical results show that our new start systemsreduce the number of singular solutions in the homotopy continuation procedure.
符号算法处理的对象是抽象的数学符号与代数概念,计算是基于整数运算的,因此没有误差。但也正是因为没有舍入,方法的计算量特别是存储量很大,导致对于大规模的问题有本质性的困难。数值算法能够求解规模较大的问题,但是也面临着数值稳定性等棘手的问题。为了能够有效的发挥数值算法和符号算法各自的优点,数值-符号混合算法是受到关注的研究热点之一。Hanzon和Jibetean提出了一类求解多项式优化问题的混合算法,称之为矩阵算法。对于优化目标多项式,通过一阶条件将优化问题转化为多项式方程组并加入高次的项作为扰动,从而很容易计算出相应的Gr(o|¨)bner基,任何多项式均可以由这组基线性表示。这里线性表示的系数矩阵称为相伴矩阵,进而将问题转化为求解相伴矩阵的特征值和特征向量的问题。
在Hanzon-Jibetean算法中,相伴矩阵起到了核心的作用,但通常矩阵的规模非常大。本文提出了一类针对相伴矩阵的混合算法–改进矩阵算法。我们在一阶条件引出的多项式方程组与加入的高次扰动项之间建立匹配模型,通过优化两者之间的匹配关系,获得规模最小化的相伴矩阵,使得算法中相伴矩阵的规模明显降低,从而有效提升了算法的效率。
在此基础之上,本文又针对求解多项式优化驻点的一阶条件,给出了一类矩阵收缩算法,即加入一个新的变量和一个新的多项式方程,从而使得算法只需计算对应于新增添变量的特征值,即可求得该多项式的驻点。这一改进对于多项式优化问题提供了更进一步的支撑,使得运算效率得到大幅度的提高。
最后,本文给出了上述改进矩阵算法的一个应用,将其应用于多项式同伦系统,这一应用在一定程度上使得同伦跟踪系统的奇异解得以减少,也使得整个同伦跟踪算法更加有效。
The multivariate polynomial optimization is an important problem in the globaloptimization. It has applications in many areas of science and engineering, such ascontrol theory and signal processing. Numerical algorithm and symbolic algorithm arethe fundamental approaches for this problem.
Symbolic algorithm deals with mathematical symbols and algebra objects withouterror. However, this kind of method often leads to heavy duty of computation when thescale of the problem is large. Numerical algorithm, on the other hand, can solve largerproblem in general. It also faces problems, such as stability. Therefore numerical-symbolic hybrid method would be a natural consideration in order to take the advan-tages of both these two methods. Hanzon and Jibetean proposed matrix method, whichtransforms the optimization of multivariate polynomial to a polynomial system of equa-tions through the first order condition. The method can easily generate the Gr(o|¨)bnerbasis by adding high order leading terms, so that any polynomial can be represented bythese basis. Here the representing coefficient matrix is called associated matrix. Thenone can get the critical points of the objective polynomial through computing eigenval-ues and eigenvectors of the associated matrix.
Associated matrix plays an important role in Hanzon-Jibetean method. However,the scale of associated matrix is often large. In this dissertation we propose a newhybrid method, which is named as improved matrix method. We establish a matchingmodel between the added high order leading terms and polynomial equations arisingfrom the first order conditions. By optimizing this matching, we can get the minimalscale of the associated matrix, which would make the scale of the associated matrixsmaller and the algorithm more efficient.
At the same time, we propose a new matrix contractive algorithm by adding a newvariable and a new equation to the original first order conditions. In this method, weget the critical points of the objective polynomial through computing the eigenvalue ofthe new added variable only once. By this improvement, we can make the polynomialoptimization much faster.
As an application, we apply the improved matrix methods to constructing the startsystem for the homotopy method. Numerical results show that our new start systemsreduce the number of singular solutions in the homotopy continuation procedure.
引文
[1] H.Hironaka. Resolution of Singularities of an Algebraic Variety over a Field of CharacteristicZero. Ann. Math. 1964, 79:109-326.
[2] B.Buchberger. An algorithm for finding a basis for the residue class ring of a zero-dimensionalpolynomial ideal. Univ. Innsbruck, 1965.
[3] B.Buchberger. A criterion for detecting unnecessary reductions in the construction of Gro¨bnerbases. Springer-Verlag, 1979.
[4] B.Buchberger. A note on the complexity of constructing Gro¨bner bases. EURO-CAL’83,Springer, 1983, LNCS,137-145.
[5] B.Buchberger. What can Gro¨bner bases do for computational geometry and robotics. Work-shop on Geometric Reasoning,Oxford, England, 1986.
[6] D.Cox, J.Little, D.O’Shea. Ideals, varieties and algorithms. Springer, New York(2nd edi-tion),1997.
[7] Gel’fand, I. M., Kapranov, M. M., and Zelevinsky, A. V., Discriminants. Resultants and Mul-tidimensional Determinants. Birkhauser Boston Inc., Cambridge, 1994.
[8] D.Lazard. Systems of Algebraic Equations (algorithms and complexity), Computational Al-gebraic Geometry and Commutative Algebra. Cambridge University Press,london,2002.
[9] D.N.Bernshtein. The Number of roots of a system of equations. Functional Anal.Appl.,1975,9:183-185.
[10] L.Robbiano. Term orderings on the polynomial ring. EUROCAL,1985,204:513-517.
[11] Watson,L. T., Sosonkina, M., Melville, R. C., Morgan, A. P., and Walker, H. F. HOMPACK90:A suite of Fortran 90 codes for globally convergent homotopy algorithms.ACM Trans. Math.Softw,1997,23(4):514–549.
[12] V.Weispfenning. Canonical comprehensive Gro¨bner bases.J.Symb.Comp.,2003, 36: 669-683.
[13] A.P.Morgan. Solving polynomial systems using continuation for engineering and scientificproblems . Prentice-Hall, Englewood Cliffs, N.J., 1987.
[14] C.Traverso. Hilbert functions and the Buchberger algorithm. J.Symb.Comp.,1996,22:355-376.
[15] S.Collart, M.Kalkbrener, D.Mall. Converting bases with the Gro¨bner walk. J.Symb.Comp.,1997,24:465-469.
[16] Q.N.TRAN.A Symbolic-Numerical Method for Finding a Real Solution of an Arbitrary Sys-tem of Nonlinear Algebraic Equations. J.Symb.Comp.,1998,26:739-760.
[17] Q.N.TRAN. A Fast Algorithm for Gro¨bner Basis Conversion and its Applications.J.Symb.Comp.,2000,30:451-467.
[18] J.C.Faugere. A new efficient algorithm for computing Gro¨bner bases (F4).Journal of Pure andApplied Algebra, 1999,139:61-88.
[19] J.C.Faugere. Computing Gro¨bner Basis without reduction to zero (F5).ACM,2002.
[20] F.J.Drexler. Eine methode zur berechnung samtlicher losungen von polynomgleichungssyste-men. Numer.Math.,1977,29:45-58.
[21] B.Huber, B.Sturmfels. Bernshtein’s theorem in affine space. Discrete Comput. Geom.,1997,7:137-141.
[22] T.Y.Li,On Chow. Mallet-Paret and Yorke Homotopy for solving systems of polynomials. Bul-letin of the Institute of Mathematics. Acad. Sin.,1983,11:433-437.
[23] T.Y.Li. Solving polynomial system. The Mathematical Intelligence,1987,9:33-39.
[24] S.N.Chow, J.Mallet-Paret, J.A.Yorke. Homotopy method for locating all zeros of a system ofpolynomials, In H.O.Peitgen and H.O.Walther, editors, Functional differential equations andapproximation of fixed points. Lecture Notes in Mathematics, 1979,730:77-88.
[25] T.Y.Li. Solving polynomial systems by the homotopy continuation method. Handbook of Nu-merical Analysis,2003,11.
[26] A.P.Morgan. Polynomial continuation and its relationship to the symbolic reduction of poly-nomial systems. Workshop on the integration of numerical and symbolic computing methods,Saratoga Springs, New York,1991.
[27] Watson, L. T., Billups, S. C., and Morgan, A. P. ALGORITHM 652: HOMPACK: Asuite of codes for globally convergent homotopy algorithms.ACM Trans. Math. Softw,1987,13(3):281–310.
[28] J.Verschelde. Homotopy continuation methods for solving polynomial systems. KatholiekeUniversiteit Leuven,1996.
[29] T.A.Gao, T.Y.Li, X.S.Wang. Finding isolated zeros of polynomial systems in Cn with stablemixed volumes. J. Symbolic Comput.,1999, 28:187-211.
[30] T.Y.Li, X.Li. Finding mixed cells in the mixed volume computation.Comput.Math.,2001,1:161-181.
[31] Morgan, A. P., Sommese. A homotopy for solvig general polynomial systems that respectm-homogeneous structures. Appl. Math.Comput.,1987,24:115–138.
[32] A.P.Morgan, A.J.Sommese. A homotopy for solving general polynomial systems that respectm-homogeneous structures. Appl. Math. Comp.,1989,24:115-138.
[33] A.P.Morgan, A.J.Sommese. Mathematical reduction of a heart dipole model. J. Appl.Mat.Comp.,1989,27:407-410.
[34] B.Hanzon, D.Jibetean. Global minimization of a multivariate polynomial using matrix meth-ods. Journal of Global Optimization,2003,27: 1-23.
[35] D.Cox, J.Little, D.O’Shea. Using algebraic geometry.Springer-Verlag, New York,1998.
[36]刘木兰. Gro¨bner基理论及其应用.科学出版社,2000.
[37] B.Buchberger. Gro¨bner bases: An algorithmic method in polynomial ideal theory. Recenttrends in Multidimensional systems theory,Rcidel Publ. Company, 1985,Chapter 6.
[38] R.Corless, P.Gianni, B.Trager. A reordered Schur factorization method for zero dimensionalpolynomial systems with multiple roots. In Proc. Intern. Symp. Symbolic and Algebraic Com-putation (ISSAC’97) ACM Press, New York, 1997, 13:133–140.
[39] T.Takeshima,Risa/Asir. Fujitsu Laboratories Limited, Version 950831, Available fromftp://endeavor.fujitsu.co.jp/pub/isis/asir,1996.
[40] J.C.Faugere, C.Traverso, P.Gianni, D.Lazard, T.Mora. Efficient computation of zero-dimensional Gro¨bner bases by change of ordering. J.Symb.Comp., 1993,6:29-344.
[41] S.Olafsson, L. Shi.Ordinal comparison via the nested-partitions method. Discrete Event Dy-namic System: Theory and Application,2002,12:211-239.
[42] J.Verschelde.Algorithm 795, PHCpack, A general-purpose solver for polynomial systems byhomotopy continuation. ACM Transactions on Mathematical Software,1999,25:251 - 276.
[43] J.Verschelde, K.Gatermann, R.Cools.Mixed-volume computation by dynamic lifting appliedto polynomial systems solving. Discrete Comput. Geom .,1996,16:69-112.
[44] J.Verschelde, M.Beckers, A.Haegemans.A new start system for solving deficient polynomialsystems using continuation. Appl. Math. Comput.,1991,44:3-25.
[45] J.Verschelde, P.Verlinden, R.Cools.Homotopies exploiting Newton polytopes for solvingsparse polynomial systems. SIAM J. Numer. Anal.,1994,31:915-930.
[46] J.Verschelde, R.Cools.Nonlinear reduction for solving deficient polynomial systems by con-tinuation methods. Numer. Math.,1992,63:263-282.
[47] J. Verschelde. PHCPACK: A general-purse solver for polynomial systems by homotopy con-tinuation. ACM Tran.Math.Softw,1999,25(1):251-27.
[48] Li, T.-Y. and Wang, X. Nonlinear homotopies for solving deficient polynomial systems withparameters. SIAM J. Numer. Anal.,1992,29(4):1104–1118.
[49] Li, T.-Y. and Wang, X. Solving deficient polynomial systems with homotopies which keep thesubschemes at infinity invariant. Math. Comput.,1991,56(194):693–710.
[50] Maria, S., Layne, T. W., and David, E. S. Note on the end game in homotopy zero curvetracking. ACM Tran.Math.Softw,1996,22(3):281-287.
[51] Morgan, A. P., Sommese, A. J., and Wampler, C W. Computing singular solutions to nonlinearanalytic systems.Numer. Math.,1991,8:69–684.
[52] Morgan, A. P., Sommese, A. J., and Wampler, C W. Computing singular solutions to polyno-mial systems.Adv. Appl. Math.,1992,13(3):305–327.
[53] A.Y.Uteshev, T.M.Cherkasov.Polynomial optimization problem. DokladyMathematics,1998,58:46–48.
[54] A.Dickenstein, N.Fitchas, M.Giusti, C.Sessa.The membership problem for unmixed polyno-mial ideals is solvable in single exponential time. Discrete Applied Mathematics,1991,33:73–94.
[55] A.Friezea, M.Jerrum.An analysis of a Monte Carlo algorithm for estimating the permanent.Combinatorica,1995,15:67-83.
[56] A.Giovini, T.Mora, G.Niesi, L.Robbiano, C.Traverso. One sugar cube, please, or Selectionstrategies in the Buchberger Algorithm. (ISSAC’91) Watt, S.M., New York,1991.
[57] A.P.Morgan, A.J.Sommese.Coefficient-Parameter PolynomialContinuation.J.Appl.Math.Comp.,1989,9:123-160.
[58] B.Barkee, D.C.Can, J.Ecks, T.Moriarty, R.F.Ree.Why You Cannot Even Hope to Use Gro¨bnerBases in Public-Key Cryptography. Journal of Symbolic Computations,1994,8:497-501.
[59] B.Char, K.Geddes, G.Gonnet,B.Leong,M.Monagan,S.Watt.Maple V Library Reference Man-ual. Springer, Berlin,1991.
[60] B.Huber, B.Sturmfels.A polyhedral method for solving sparse polynomial systems. Math.Comp.,1995,64:1541-1555.
[61] C.B.Garcia, W.I.Zangwill.Finding all solutions to polynomial systems and other systems ofequations. Math.Programming.,1979,16:159-176.
[62] C.Traverso.Gro¨bner Engine. Rel. 2.0, http://janet.dm.unipi.it/posson/demo.html,1997.
[63] C.Traverso.The PoSSo test suite examples. Available athttp://www.inria.fr/saga/POL/index.html,1993.
[64] C.V.Nelsen, B.C.Hodgkin.Determination of magnitudes, directions, and locations of two in-dependent dipoles in a circular conducting region from boundary potential measurements’.IEEE Trans. Biomed. Engrg.,1981,28:17-823.
[65] C.W.Wampler.Bezout number calculations for multi-homogeneous polynomial Systems.Appl. Math. Comput.,1992,51:2-3.
[66] Cannon, J.The Magma Computational Algebra System 2.http://www.maths.usyd.edu.au:8000/u/magma/, 1998.
[67] Didier Bondyfalat, Bernard Mourrain, Victor Y.Pan. Controlled Iterative methods for solvingpolynomial systems. (ISSAC’98) ACM Press, New York,1998,252–259.
[68] D. Jibetean. Global optimization of rational multivariate functions. Technical Report PNA-R0120, CWI, Amsterdam,2001.
[69] D.Lazard.Gro¨bner bases, Gaussian elimination and resolutions of systems of algebraic equa-tions. EUROCAL 83,Springer L.N. Comp.Sci.,1983,162.
[70] E.L.Allgower, K.Georg.Numerical continuation methods.Springer Series in Comput.Math.,springer-verlag,1990, 13.
[71] F.Boulier.A new criterion to avoid useless critical pairs in Buchberger’s algorithm. month 7,2001.
[72] G.Delic, G.G.Cash.The permanent of 0,1 matrices and Kallman’s algorithm. ComputerPhysics Communication,2000,124:315-329.
[73] G.Attardi, C.Traverso.Homogeneous parallel algorithm. J.Symb.Comp.,1996.
[74] G.M.Bergman.The Diamond Lemma for Ring Theory. Adv.Math.,1978,29:178-218.
[75] G.M.Greuel, G.Pfister, H.Schoenemann.SINGULAR 1.0.2,http://www.mathematik.unikl.de/zca/Singular/Welcome.html,1997.
[76] Gerdt, V.P.Involutive Polynomial Bases. PoSSo on Software Paris, 1995.
[77] Huber, B.and Verschelde. Polyhedral end games for polynomial continuation.Num.Alg.,1998,8(1):91–108.
[78] H.J.Stetter. Matrix eigenproblems are at the heart of polynomials systems solving. SIGSAMBulletin,1996,30:22–25.
[79] H.Liang, F. Bai.A partially structure-preserving algorithm for the permanents of adjacencymatrices of fullerenes. Computer Physics Communications,2004.
[80] H.Liang, F. Bai, L.Shi.Computing the optimal partition of variables in multi-homogeneoushomotopy methods. Appl.Math.Comput.,2005,63:825-840.
[81] H.Liang, L.Shi, F.Ba i, X.Liu.Random path method with pivoting for computing permanentsof matrices. Appl. Math. Comput.,2006,7.
[82] H.Liang, S.Huang, F.Bai.Hybrid Algorithms for Computing Permanents of Sparse Matrices.Appl. math. comput.,2006,172:708-716 .
[83] H.Liang, X.Liu, F.Bai.An optimization problem in multi-homogeneous homotopy method.Optimization Methods and Software,2004,19:361-369.
[84] H.Liang, F.Bai.A new upper bound for permanent of (0,1)-matrices. Linear Algebra and itsApplications,2004,277:291-295.
[85] H.M.Moller, H.J.Stetter. Multivariate polynomial equations with multiple zeros solved by ma-trix eigenproblems. Numer.Math.,1995,70:311-329.
[86] H.Minc.Upper bound for permanents of (0,1)-matrices. Bull. Amer. Math. Soc.,1963,69:789-791.
[87] H.Minc.Permanents. Encyclopedia Math. Appl.,1978,6.
[88] J.B.Lasserre. Global optimization with polynomials and the problem of moments. SIAM Jour-nal on Optimization,2001,11(3):796–817.
[89] J.C.Faugere.On line documentation of Gb. Available on the WEB http://posso.lip6.fr/jcf/.
[90] J.C.Faugere.How my computer find all the solutions of cyclic 9. Lecture Notes Series onComputing,2001,9.
[91] J.C.Faugere.Changing the ordering of Gro¨bner Bases with LLL: Case of Two Variables. IS-SAC’03,ACM.,2003.
[92] K.Hagglof, P.O.Lindberg, L.Stevenson. Computing global minima to polynomial optimizationproblems using Grobner bases. Journal of Global Optimization,1995,7(2):115–125.
[93] M.Kalkbrener.On the complexity of Gro¨bner bases conversion. J.Symb.Comp.,1999,28:265-274.
[94] Cash G G. A fast computer algorithm for finding the permanent of adjacency matrices. J.Math. Chem.,1995, 18:115-119.
[95] Cash G G. A simple means of computing the Kekule structure count for toroidal polyhexfullerenes. J. Chem. Inf. Comput. Sci. 1998, 38:58-61.
[96] Cash G G. Permanents of adjacency matrices of fullerenes. Polycyclic Aromatic Compounds,1997, 12:61-69.
[97] L.Robbiano.On the Theory of Graded Structures. J. Symb. Comp.,1986,2:139-170.
[98] L.Shi, S.Olafsson.Nested partitions method for global optimization. OperationResearch,2000,48:390-407.
[99] L.Shi, S.Olafsson.Stopping rules for the stochastic nested partitions method. Methodologyand Computing in Applied Probability,2000,2:37-58.
[100] L.Valliant.The complexity of computing the permanent. Theoret. Comput. Sci.,1979,8:189-201.
[101] Li, T.-Y. and Wang, X. The BKK root count in Cn. Math. Comput.,1991,65(216):1477–1484.
[102] M.Jerrum, A.Sinclair, E.Vigoda.A polynomial-time approximation algorithm for the perma-nent of a matrix with non-negative entries. ECCC, Report No.79.,2000.
[103] Morgan, A. P., Sommese, A. J., and Wampler, C. W. A power series method for computingsingular solutions to nonlinear analytic systems. Numer. Math.,1992,63:391–409.
[104] Morgan, A. P., Sommese. Computing all solutions to polynomial systems using homotopycontinuation. Appl. Math.Comput.,1987,24(2):101–113.
[105] N.Karmarkar, R.M.Karp, R.Lipton, L.Lovasz, M.Luby.A Monte Carlo algorithm for estimat-ing the permanent. SIAM J. Comput.,1993,22:284-293.
[106] N.Z.Shor, P.I.Stetsyuk. The use of a modification of the r-algorithm for finding the globalminimum of polynomial functions. Cybernetics and Systems Analysis,1997,33:482-497.
[107] N.Z.Shor. A class of global minimum bounds of polynomial functions.Cybernetics,1987,3(6):731-734.
[108] P.A.Parrilo.Semidenite programming relaxations for semialgebraic problems. Available athttp://www.cds.caltech.edu/ pablo/pubs.htm,2001.
[109] P.Conti, C.Traverso.Buchberger Algorithm and Integer Programming. The 9th Inter-national Symposium, on Applied Algebra, Algebraic Algorithms and Error-CorrectingCodes,1991,5:130 - 139.
[110] R.C.Mittal, A Al-Kurdi.Efficient computation of the permanent of a sparse matrix. Int.J.Comput. Math.,2001,77:189-199.
[111] R.Gebauer, H.M.Moller.On an installation of Buchberger’s algorithm. J. SymbolicComput.,1998,6:275–286.
[112] R.Kallman.A method for finding permanents of 0,1 matrices. Math. Comput.,1982,57:167-170.
[113] T.Becker, V.Weispfenning. Gro¨bner Bases, a Computationnal Approach to Commutative Al-gebra, Graduate Texts in Mathematics. Springer-Verlag, New York,1993.
[114] T.J.Li, F.Bai. Minimizing multi-homogeneous Be′zout number by a local search method.Math. Comp.,2000,70:767-787.
[115] T.Li, Z.J. Lin, F. Bai. Heuristic methods for computing the minimizing multi-homogeneousBe′zout number. Appl.Math. Comput.,2003,46:237-256.
[116] T.Mora, L.Robbiano.The Gro¨bner fan of an ideal. J.Symb.Comp.,1998,6:183-208.
[117] V.Weispfenning. Comprehensive Gro¨bner bases.J.Symb.Comp.,1992, 14:1-29.
[118]蔡大用,白峰杉.现代科学计算.科学出版社,2000.
[119]邢文训,谢金星.现代优化计算方法.清华大学出版社,1999.
[120]谢金星,邢文训.网络优化.清华大学出版社,2000.
[2] B.Buchberger. An algorithm for finding a basis for the residue class ring of a zero-dimensionalpolynomial ideal. Univ. Innsbruck, 1965.
[3] B.Buchberger. A criterion for detecting unnecessary reductions in the construction of Gro¨bnerbases. Springer-Verlag, 1979.
[4] B.Buchberger. A note on the complexity of constructing Gro¨bner bases. EURO-CAL’83,Springer, 1983, LNCS,137-145.
[5] B.Buchberger. What can Gro¨bner bases do for computational geometry and robotics. Work-shop on Geometric Reasoning,Oxford, England, 1986.
[6] D.Cox, J.Little, D.O’Shea. Ideals, varieties and algorithms. Springer, New York(2nd edi-tion),1997.
[7] Gel’fand, I. M., Kapranov, M. M., and Zelevinsky, A. V., Discriminants. Resultants and Mul-tidimensional Determinants. Birkhauser Boston Inc., Cambridge, 1994.
[8] D.Lazard. Systems of Algebraic Equations (algorithms and complexity), Computational Al-gebraic Geometry and Commutative Algebra. Cambridge University Press,london,2002.
[9] D.N.Bernshtein. The Number of roots of a system of equations. Functional Anal.Appl.,1975,9:183-185.
[10] L.Robbiano. Term orderings on the polynomial ring. EUROCAL,1985,204:513-517.
[11] Watson,L. T., Sosonkina, M., Melville, R. C., Morgan, A. P., and Walker, H. F. HOMPACK90:A suite of Fortran 90 codes for globally convergent homotopy algorithms.ACM Trans. Math.Softw,1997,23(4):514–549.
[12] V.Weispfenning. Canonical comprehensive Gro¨bner bases.J.Symb.Comp.,2003, 36: 669-683.
[13] A.P.Morgan. Solving polynomial systems using continuation for engineering and scientificproblems . Prentice-Hall, Englewood Cliffs, N.J., 1987.
[14] C.Traverso. Hilbert functions and the Buchberger algorithm. J.Symb.Comp.,1996,22:355-376.
[15] S.Collart, M.Kalkbrener, D.Mall. Converting bases with the Gro¨bner walk. J.Symb.Comp.,1997,24:465-469.
[16] Q.N.TRAN.A Symbolic-Numerical Method for Finding a Real Solution of an Arbitrary Sys-tem of Nonlinear Algebraic Equations. J.Symb.Comp.,1998,26:739-760.
[17] Q.N.TRAN. A Fast Algorithm for Gro¨bner Basis Conversion and its Applications.J.Symb.Comp.,2000,30:451-467.
[18] J.C.Faugere. A new efficient algorithm for computing Gro¨bner bases (F4).Journal of Pure andApplied Algebra, 1999,139:61-88.
[19] J.C.Faugere. Computing Gro¨bner Basis without reduction to zero (F5).ACM,2002.
[20] F.J.Drexler. Eine methode zur berechnung samtlicher losungen von polynomgleichungssyste-men. Numer.Math.,1977,29:45-58.
[21] B.Huber, B.Sturmfels. Bernshtein’s theorem in affine space. Discrete Comput. Geom.,1997,7:137-141.
[22] T.Y.Li,On Chow. Mallet-Paret and Yorke Homotopy for solving systems of polynomials. Bul-letin of the Institute of Mathematics. Acad. Sin.,1983,11:433-437.
[23] T.Y.Li. Solving polynomial system. The Mathematical Intelligence,1987,9:33-39.
[24] S.N.Chow, J.Mallet-Paret, J.A.Yorke. Homotopy method for locating all zeros of a system ofpolynomials, In H.O.Peitgen and H.O.Walther, editors, Functional differential equations andapproximation of fixed points. Lecture Notes in Mathematics, 1979,730:77-88.
[25] T.Y.Li. Solving polynomial systems by the homotopy continuation method. Handbook of Nu-merical Analysis,2003,11.
[26] A.P.Morgan. Polynomial continuation and its relationship to the symbolic reduction of poly-nomial systems. Workshop on the integration of numerical and symbolic computing methods,Saratoga Springs, New York,1991.
[27] Watson, L. T., Billups, S. C., and Morgan, A. P. ALGORITHM 652: HOMPACK: Asuite of codes for globally convergent homotopy algorithms.ACM Trans. Math. Softw,1987,13(3):281–310.
[28] J.Verschelde. Homotopy continuation methods for solving polynomial systems. KatholiekeUniversiteit Leuven,1996.
[29] T.A.Gao, T.Y.Li, X.S.Wang. Finding isolated zeros of polynomial systems in Cn with stablemixed volumes. J. Symbolic Comput.,1999, 28:187-211.
[30] T.Y.Li, X.Li. Finding mixed cells in the mixed volume computation.Comput.Math.,2001,1:161-181.
[31] Morgan, A. P., Sommese. A homotopy for solvig general polynomial systems that respectm-homogeneous structures. Appl. Math.Comput.,1987,24:115–138.
[32] A.P.Morgan, A.J.Sommese. A homotopy for solving general polynomial systems that respectm-homogeneous structures. Appl. Math. Comp.,1989,24:115-138.
[33] A.P.Morgan, A.J.Sommese. Mathematical reduction of a heart dipole model. J. Appl.Mat.Comp.,1989,27:407-410.
[34] B.Hanzon, D.Jibetean. Global minimization of a multivariate polynomial using matrix meth-ods. Journal of Global Optimization,2003,27: 1-23.
[35] D.Cox, J.Little, D.O’Shea. Using algebraic geometry.Springer-Verlag, New York,1998.
[36]刘木兰. Gro¨bner基理论及其应用.科学出版社,2000.
[37] B.Buchberger. Gro¨bner bases: An algorithmic method in polynomial ideal theory. Recenttrends in Multidimensional systems theory,Rcidel Publ. Company, 1985,Chapter 6.
[38] R.Corless, P.Gianni, B.Trager. A reordered Schur factorization method for zero dimensionalpolynomial systems with multiple roots. In Proc. Intern. Symp. Symbolic and Algebraic Com-putation (ISSAC’97) ACM Press, New York, 1997, 13:133–140.
[39] T.Takeshima,Risa/Asir. Fujitsu Laboratories Limited, Version 950831, Available fromftp://endeavor.fujitsu.co.jp/pub/isis/asir,1996.
[40] J.C.Faugere, C.Traverso, P.Gianni, D.Lazard, T.Mora. Efficient computation of zero-dimensional Gro¨bner bases by change of ordering. J.Symb.Comp., 1993,6:29-344.
[41] S.Olafsson, L. Shi.Ordinal comparison via the nested-partitions method. Discrete Event Dy-namic System: Theory and Application,2002,12:211-239.
[42] J.Verschelde.Algorithm 795, PHCpack, A general-purpose solver for polynomial systems byhomotopy continuation. ACM Transactions on Mathematical Software,1999,25:251 - 276.
[43] J.Verschelde, K.Gatermann, R.Cools.Mixed-volume computation by dynamic lifting appliedto polynomial systems solving. Discrete Comput. Geom .,1996,16:69-112.
[44] J.Verschelde, M.Beckers, A.Haegemans.A new start system for solving deficient polynomialsystems using continuation. Appl. Math. Comput.,1991,44:3-25.
[45] J.Verschelde, P.Verlinden, R.Cools.Homotopies exploiting Newton polytopes for solvingsparse polynomial systems. SIAM J. Numer. Anal.,1994,31:915-930.
[46] J.Verschelde, R.Cools.Nonlinear reduction for solving deficient polynomial systems by con-tinuation methods. Numer. Math.,1992,63:263-282.
[47] J. Verschelde. PHCPACK: A general-purse solver for polynomial systems by homotopy con-tinuation. ACM Tran.Math.Softw,1999,25(1):251-27.
[48] Li, T.-Y. and Wang, X. Nonlinear homotopies for solving deficient polynomial systems withparameters. SIAM J. Numer. Anal.,1992,29(4):1104–1118.
[49] Li, T.-Y. and Wang, X. Solving deficient polynomial systems with homotopies which keep thesubschemes at infinity invariant. Math. Comput.,1991,56(194):693–710.
[50] Maria, S., Layne, T. W., and David, E. S. Note on the end game in homotopy zero curvetracking. ACM Tran.Math.Softw,1996,22(3):281-287.
[51] Morgan, A. P., Sommese, A. J., and Wampler, C W. Computing singular solutions to nonlinearanalytic systems.Numer. Math.,1991,8:69–684.
[52] Morgan, A. P., Sommese, A. J., and Wampler, C W. Computing singular solutions to polyno-mial systems.Adv. Appl. Math.,1992,13(3):305–327.
[53] A.Y.Uteshev, T.M.Cherkasov.Polynomial optimization problem. DokladyMathematics,1998,58:46–48.
[54] A.Dickenstein, N.Fitchas, M.Giusti, C.Sessa.The membership problem for unmixed polyno-mial ideals is solvable in single exponential time. Discrete Applied Mathematics,1991,33:73–94.
[55] A.Friezea, M.Jerrum.An analysis of a Monte Carlo algorithm for estimating the permanent.Combinatorica,1995,15:67-83.
[56] A.Giovini, T.Mora, G.Niesi, L.Robbiano, C.Traverso. One sugar cube, please, or Selectionstrategies in the Buchberger Algorithm. (ISSAC’91) Watt, S.M., New York,1991.
[57] A.P.Morgan, A.J.Sommese.Coefficient-Parameter PolynomialContinuation.J.Appl.Math.Comp.,1989,9:123-160.
[58] B.Barkee, D.C.Can, J.Ecks, T.Moriarty, R.F.Ree.Why You Cannot Even Hope to Use Gro¨bnerBases in Public-Key Cryptography. Journal of Symbolic Computations,1994,8:497-501.
[59] B.Char, K.Geddes, G.Gonnet,B.Leong,M.Monagan,S.Watt.Maple V Library Reference Man-ual. Springer, Berlin,1991.
[60] B.Huber, B.Sturmfels.A polyhedral method for solving sparse polynomial systems. Math.Comp.,1995,64:1541-1555.
[61] C.B.Garcia, W.I.Zangwill.Finding all solutions to polynomial systems and other systems ofequations. Math.Programming.,1979,16:159-176.
[62] C.Traverso.Gro¨bner Engine. Rel. 2.0, http://janet.dm.unipi.it/posson/demo.html,1997.
[63] C.Traverso.The PoSSo test suite examples. Available athttp://www.inria.fr/saga/POL/index.html,1993.
[64] C.V.Nelsen, B.C.Hodgkin.Determination of magnitudes, directions, and locations of two in-dependent dipoles in a circular conducting region from boundary potential measurements’.IEEE Trans. Biomed. Engrg.,1981,28:17-823.
[65] C.W.Wampler.Bezout number calculations for multi-homogeneous polynomial Systems.Appl. Math. Comput.,1992,51:2-3.
[66] Cannon, J.The Magma Computational Algebra System 2.http://www.maths.usyd.edu.au:8000/u/magma/, 1998.
[67] Didier Bondyfalat, Bernard Mourrain, Victor Y.Pan. Controlled Iterative methods for solvingpolynomial systems. (ISSAC’98) ACM Press, New York,1998,252–259.
[68] D. Jibetean. Global optimization of rational multivariate functions. Technical Report PNA-R0120, CWI, Amsterdam,2001.
[69] D.Lazard.Gro¨bner bases, Gaussian elimination and resolutions of systems of algebraic equa-tions. EUROCAL 83,Springer L.N. Comp.Sci.,1983,162.
[70] E.L.Allgower, K.Georg.Numerical continuation methods.Springer Series in Comput.Math.,springer-verlag,1990, 13.
[71] F.Boulier.A new criterion to avoid useless critical pairs in Buchberger’s algorithm. month 7,2001.
[72] G.Delic, G.G.Cash.The permanent of 0,1 matrices and Kallman’s algorithm. ComputerPhysics Communication,2000,124:315-329.
[73] G.Attardi, C.Traverso.Homogeneous parallel algorithm. J.Symb.Comp.,1996.
[74] G.M.Bergman.The Diamond Lemma for Ring Theory. Adv.Math.,1978,29:178-218.
[75] G.M.Greuel, G.Pfister, H.Schoenemann.SINGULAR 1.0.2,http://www.mathematik.unikl.de/zca/Singular/Welcome.html,1997.
[76] Gerdt, V.P.Involutive Polynomial Bases. PoSSo on Software Paris, 1995.
[77] Huber, B.and Verschelde. Polyhedral end games for polynomial continuation.Num.Alg.,1998,8(1):91–108.
[78] H.J.Stetter. Matrix eigenproblems are at the heart of polynomials systems solving. SIGSAMBulletin,1996,30:22–25.
[79] H.Liang, F. Bai.A partially structure-preserving algorithm for the permanents of adjacencymatrices of fullerenes. Computer Physics Communications,2004.
[80] H.Liang, F. Bai, L.Shi.Computing the optimal partition of variables in multi-homogeneoushomotopy methods. Appl.Math.Comput.,2005,63:825-840.
[81] H.Liang, L.Shi, F.Ba i, X.Liu.Random path method with pivoting for computing permanentsof matrices. Appl. Math. Comput.,2006,7.
[82] H.Liang, S.Huang, F.Bai.Hybrid Algorithms for Computing Permanents of Sparse Matrices.Appl. math. comput.,2006,172:708-716 .
[83] H.Liang, X.Liu, F.Bai.An optimization problem in multi-homogeneous homotopy method.Optimization Methods and Software,2004,19:361-369.
[84] H.Liang, F.Bai.A new upper bound for permanent of (0,1)-matrices. Linear Algebra and itsApplications,2004,277:291-295.
[85] H.M.Moller, H.J.Stetter. Multivariate polynomial equations with multiple zeros solved by ma-trix eigenproblems. Numer.Math.,1995,70:311-329.
[86] H.Minc.Upper bound for permanents of (0,1)-matrices. Bull. Amer. Math. Soc.,1963,69:789-791.
[87] H.Minc.Permanents. Encyclopedia Math. Appl.,1978,6.
[88] J.B.Lasserre. Global optimization with polynomials and the problem of moments. SIAM Jour-nal on Optimization,2001,11(3):796–817.
[89] J.C.Faugere.On line documentation of Gb. Available on the WEB http://posso.lip6.fr/jcf/.
[90] J.C.Faugere.How my computer find all the solutions of cyclic 9. Lecture Notes Series onComputing,2001,9.
[91] J.C.Faugere.Changing the ordering of Gro¨bner Bases with LLL: Case of Two Variables. IS-SAC’03,ACM.,2003.
[92] K.Hagglof, P.O.Lindberg, L.Stevenson. Computing global minima to polynomial optimizationproblems using Grobner bases. Journal of Global Optimization,1995,7(2):115–125.
[93] M.Kalkbrener.On the complexity of Gro¨bner bases conversion. J.Symb.Comp.,1999,28:265-274.
[94] Cash G G. A fast computer algorithm for finding the permanent of adjacency matrices. J.Math. Chem.,1995, 18:115-119.
[95] Cash G G. A simple means of computing the Kekule structure count for toroidal polyhexfullerenes. J. Chem. Inf. Comput. Sci. 1998, 38:58-61.
[96] Cash G G. Permanents of adjacency matrices of fullerenes. Polycyclic Aromatic Compounds,1997, 12:61-69.
[97] L.Robbiano.On the Theory of Graded Structures. J. Symb. Comp.,1986,2:139-170.
[98] L.Shi, S.Olafsson.Nested partitions method for global optimization. OperationResearch,2000,48:390-407.
[99] L.Shi, S.Olafsson.Stopping rules for the stochastic nested partitions method. Methodologyand Computing in Applied Probability,2000,2:37-58.
[100] L.Valliant.The complexity of computing the permanent. Theoret. Comput. Sci.,1979,8:189-201.
[101] Li, T.-Y. and Wang, X. The BKK root count in Cn. Math. Comput.,1991,65(216):1477–1484.
[102] M.Jerrum, A.Sinclair, E.Vigoda.A polynomial-time approximation algorithm for the perma-nent of a matrix with non-negative entries. ECCC, Report No.79.,2000.
[103] Morgan, A. P., Sommese, A. J., and Wampler, C. W. A power series method for computingsingular solutions to nonlinear analytic systems. Numer. Math.,1992,63:391–409.
[104] Morgan, A. P., Sommese. Computing all solutions to polynomial systems using homotopycontinuation. Appl. Math.Comput.,1987,24(2):101–113.
[105] N.Karmarkar, R.M.Karp, R.Lipton, L.Lovasz, M.Luby.A Monte Carlo algorithm for estimat-ing the permanent. SIAM J. Comput.,1993,22:284-293.
[106] N.Z.Shor, P.I.Stetsyuk. The use of a modification of the r-algorithm for finding the globalminimum of polynomial functions. Cybernetics and Systems Analysis,1997,33:482-497.
[107] N.Z.Shor. A class of global minimum bounds of polynomial functions.Cybernetics,1987,3(6):731-734.
[108] P.A.Parrilo.Semidenite programming relaxations for semialgebraic problems. Available athttp://www.cds.caltech.edu/ pablo/pubs.htm,2001.
[109] P.Conti, C.Traverso.Buchberger Algorithm and Integer Programming. The 9th Inter-national Symposium, on Applied Algebra, Algebraic Algorithms and Error-CorrectingCodes,1991,5:130 - 139.
[110] R.C.Mittal, A Al-Kurdi.Efficient computation of the permanent of a sparse matrix. Int.J.Comput. Math.,2001,77:189-199.
[111] R.Gebauer, H.M.Moller.On an installation of Buchberger’s algorithm. J. SymbolicComput.,1998,6:275–286.
[112] R.Kallman.A method for finding permanents of 0,1 matrices. Math. Comput.,1982,57:167-170.
[113] T.Becker, V.Weispfenning. Gro¨bner Bases, a Computationnal Approach to Commutative Al-gebra, Graduate Texts in Mathematics. Springer-Verlag, New York,1993.
[114] T.J.Li, F.Bai. Minimizing multi-homogeneous Be′zout number by a local search method.Math. Comp.,2000,70:767-787.
[115] T.Li, Z.J. Lin, F. Bai. Heuristic methods for computing the minimizing multi-homogeneousBe′zout number. Appl.Math. Comput.,2003,46:237-256.
[116] T.Mora, L.Robbiano.The Gro¨bner fan of an ideal. J.Symb.Comp.,1998,6:183-208.
[117] V.Weispfenning. Comprehensive Gro¨bner bases.J.Symb.Comp.,1992, 14:1-29.
[118]蔡大用,白峰杉.现代科学计算.科学出版社,2000.
[119]邢文训,谢金星.现代优化计算方法.清华大学出版社,1999.
[120]谢金星,邢文训.网络优化.清华大学出版社,2000.