Algorithm 795

ACM Transactions on Mathematical Software - Tập 25 Số 2 - Trang 251-276 - 1999
Jan Verschelde1
1Mathematical Sciences Research Institute, Berkeley, CA

Tóm tắt

Polynomial systems occur in a wide variety of application domains. Homotopy continuation methods are reliable and powerful methods to compute numerically approximations to all isolated complex solutions. During the last decade considerable progress has been accomplished on exploiting structure in a polynomial system, in particular its sparsity. In this article the structure and design of the software package PHC is described. The main program operates in several modes, is menu driven, and is file oriented. This package features great variety of root-counting methods among its tools. The outline of one black-box solver is sketched, and a report is given on its performance on a large database of test problems. The software has been developed on four different machine architectures. Its portability is ensured by the gnu-ada compiler.

Từ khóa


Tài liệu tham khảo

ADA CORE TECHNOLOGIES. 1997. GNAT user's guide: The GNU Ada 95 compiler. Ada Core Technologies New York NY. Available at http://www.gnat.com. ADA CORE TECHNOLOGIES. 1997. GNAT user's guide: The GNU Ada 95 compiler. Ada Core Technologies New York NY. Available at http://www.gnat.com.

10.1007/BF00129645

10.1145/120694.120708

BELLIDO A. M., 1992, Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems, Num. Alg., 6, 3

10.1007/BF01075595

BINI D. AND MOURRAIN B. 1998. Polynomial test suite http://www-sop.inria.fr/saga/POL/. BINI D. AND MOURRAIN B. 1998. Polynomial test suite http://www-sop.inria.fr/saga/POL/.

10.1016/S0747-7171(08)80153-8

BJ RCK G., Analysis, Algebra and Computers in Mathematical Research

BLUM L. CUCKER F. SHUB M. AND SMALL S. 1997. Complexity and Real Computation. Springer-Verlag New York NY. BLUM L. CUCKER F. SHUB M. AND SMALL S. 1997. Complexity and Real Computation. Springer-Verlag New York NY.

10.1016/S0747-7171(86)80014-1

BOON S., 1992, Solving systems of equations, Sci. Math. Num-Analysis. Newsgroup Article 3529.

10.1145/120694.120707

10.1137/0609043

COHN H., 1988, An explicit modular equation in two variables for Q{sqrt(3)}, Math. Comput., 50, 557

LITTLE J., 1998, Springer Graduate Texts in Mathematics, 185

EMIRIS I. Z. 1994. Sparse elimination and applications in kinematics. Ph.D. Dissertation. Computer Science Department University of California at Berkeley Berkeley CA. Available at http://www.inria.fr/saga/emiris. EMIRIS I. Z. 1994. Sparse elimination and applications in kinematics. Ph.D. Dissertation. Computer Science Department University of California at Berkeley Berkeley CA. Available at http://www.inria.fr/saga/emiris.

EMIRIS I. Z. 1997. A general solver based on sparse resultants: Numerical issues and kinematic applications. Rapport de recherche no. 3110. INRIA Rennes France. Available via anonymous ftp to ftp.inria.fr. EMIRIS I. Z. 1997. A general solver based on sparse resultants: Numerical issues and kinematic applications. Rapport de recherche no. 3110. INRIA Rennes France. Available via anonymous ftp to ftp.inria.fr.

EMIRIS I. Z., Encyclopedia of Computer Science and Technology

10.1006/jsco.1995.1041

10.1016/S0166-218X(99)00003-7

10.5555/93023.93041

10.1006/jsco.1998.0272

GAREY M. AND JOHNSON D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York NY. GAREY M. AND JOHNSON D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York NY.

10.1145/96877.96907

GEL'FAND I. M. KAPRANOV M. M. AND ZELEVINSKY A.V. 1994. Discriminants Resultants and Multidimensional Determinants. Birkh user Boston Inc. Cambridge MA. GEL'FAND I. M. KAPRANOV M. M. AND ZELEVINSKY A.V. 1994. Discriminants Resultants and Multidimensional Determinants. Birkh user Boston Inc. Cambridge MA.

GIORDANO T. 1996. Impl mention distribu e du calcul du volume mixte. Master's Thesis. University of Nice Sophia-Antipolis France. GIORDANO T. 1996. Impl mention distribu e du calcul du volume mixte. Master's Thesis. University of Nice Sophia-Antipolis France.

HARIMOTO S., 1989, The granularity of homotopy algorithms for polynomial systems of equations. In Parallel Processing for Scientific Computing, G. Rodrique, Ed. SIAM, Philadelphia, PA, 115

HUBER B. 1995. Pelican manual. Availabe via http://www.mrsi.org/people/members/birk. HUBER B. 1995. Pelican manual. Availabe via http://www.mrsi.org/people/members/birk.

HUBER B. T. 1996. Solving sparse polynomial systems. Ph.D. Dissertation. Cornell University Ithaca NY. Available at http://www.msri.org/people/members/birk. HUBER B. T. 1996. Solving sparse polynomial systems. Ph.D. Dissertation. Cornell University Ithaca NY. Available at http://www.msri.org/people/members/birk.

10.2307/2153370

10.1007/BF02770870

10.1023/A:1019163811284

10.1006/jsco.1998.0239

KHOVANSKII A., 1991, Translations of Mathematical Monographs, 88

10.1080/00029890.1972.11993188

10.1007/BF01075534

10.1007/BF03023953

10.1017/S0962492900002749

10.1007/BF01390706

10.1090/S0025-5718-1991-1066835-2

10.1137/0729067

10.1090/S0025-5718-96-00778-8

10.1137/0724032

10.1007/BF01400351

10.1137/0726069

LI T.-Y., 1996, Eds. Lectures in Applied Mathematics, 32

MALAJOVICH G. 1996. pss 2.beta polynomial system solver. (Software). Available at http://www.labma.ufrj.br:80/gregorio. MALAJOVICH G. 1996. pss 2.beta polynomial system solver. (Software). Available at http://www.labma.ufrj.br:80/gregorio.

THE FRISCO CONSORTIUM. 1996. FRISCO--A framework for integrated symbolic/numeric computation. Available at http://www.nag.co.uk/projects/FRISCO.html. THE FRISCO CONSORTIUM. 1996. FRISCO--A framework for integrated symbolic/numeric computation. Available at http://www.nag.co.uk/projects/FRISCO.html.

THE PISA TEAM OF PoSSo. 1993. PoSSo home page. http://janet.dm.unipi.it/. THE PISA TEAM OF PoSSo. 1993. PoSSo home page. http://janet.dm.unipi.it/.

10.1145/78928.78930

10.1137/0714072

10.1145/355934.355936

MORGAN A. P. 1987. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall Inc. Upper Saddle River NJ. MORGAN A. P. 1987. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall Inc. Upper Saddle River NJ.

10.1145/328512.328521

10.1016/0096-3003(87)90064-6

10.1016/0096-3003(87)90063-4

10.1016/0096-3003(89)90099-4

10.1115/1.2912644

10.1007/BF01385648

10.1016/0196-8858(92)90014-N

10.1007/BF01385867

10.1137/0732061

10.1145/63522.64124

10.1145/164081.164120

MOURRAIN B. 1996. The handbook of polynomial systems. Available via http://www.inria.fr/ saga/POL/index.html. MOURRAIN B. 1996. The handbook of polynomial systems. Available via http://www.inria.fr/ saga/POL/index.html.

10.1006/jsco.1997.0191

10.1109/TBME.1981.324681

10.1137/0149109

10.1137/S036301299325270X

10.1016/0304-3975(93)00062-A

ROJAS J. M., 1997, Rio de Janeiro, 369

10.1016/S0022-4049(98)00023-1

10.1006/jcom.1996.0009

10.1016/S0167-6911(97)00122-9

ROSENTHAL J., Open Problems in Mathematical Systems and Control Theory

SCHRANS S., 1990, Generalized Virasoro constructions for SU(3), Nuc. Phy., 345, 2

10.1145/232826.232843

SOTTILE F., Algebraic Geometry--Santa Cruz 1995: Part I of Proceedings of Symposia in Pure Mathematics, J. Koll r

STROUD A. H. AND SECREST D. 1966. Gaussian Quadrature Formulas. Prentice-Hall Series in Automatic Computation. Prentice-Hall Englewood Cliffs NJ. STROUD A. H. AND SECREST D. 1966. Gaussian Quadrature Formulas. Prentice-Hall Series in Automatic Computation. Prentice-Hall Englewood Cliffs NJ.

10.1023/A:1022497624378

10.1080/00029890.1998.12004987

SWELDENS W. 1994. The construction and application of wavelets in numerical analysis. Ph.D. Dissertation. Department of Computer Science Katholieke Universiteit Leuven Leuven Belgium. SWELDENS W. 1994. The construction and application of wavelets in numerical analysis. Ph.D. Dissertation. Department of Computer Science Katholieke Universiteit Leuven Leuven Belgium.

10.1145/216578.216583

TRAVERSO C. 1993. The PoSSo test suite examples. Available at http://www.inria.fr/saga/ POL/index.html. TRAVERSO C. 1993. The PoSSo test suite examples. Available at http://www.inria.fr/saga/ POL/index.html.

10.1137/S0036142995281504

VERSCHELDE J. 1990. Oplossen van stelsels veeltermvergelijkingen met behulp van continueringsmethodes. Bachelor's Thesis. Department of Computer Science Katholieke Universiteit Leuven Leuven Belgium. VERSCHELDE J. 1990. Oplossen van stelsels veeltermvergelijkingen met behulp van continueringsmethodes. Bachelor's Thesis. Department of Computer Science Katholieke Universiteit Leuven Leuven Belgium.

VERSCHELDE J., 1995, Proceedings of the PoSSo Workshop on Software

VERSCHELDE J. 1996. Homotopy continuation methods for solving polynomial systems. Ph.D. Dissertation. Department of Computer Science Katholieke Universiteit Leuven Leuven Belgium. VERSCHELDE J. 1996. Homotopy continuation methods for solving polynomial systems. Ph.D. Dissertation. Department of Computer Science Katholieke Universiteit Leuven Leuven Belgium.

VERSCHELDE J., 1998, Numerical evidence for a conjecture in real algebraic geometry, Preprint, 1998

10.1007/BF01385861

VERSCHELDE J., 1993, An Ada workbench for homotopy continuation for solving polynomial systems, Ada Belg. Newslett., 2, 23

10.1007/BF01202036

10.1016/0377-0427(94)90329-8

VERSCHELDE J., 1996, Polynomial homotopy continuation, a portable Ada software package, Ada Belg. Newslett., 4, 59

10.1006/aama.1995.1005

10.1137/0730028

10.1016/0096-3003(91)90059-V

10.1007/BF02711134

10.1137/0731049

10.1145/281508.281626

WAMPLER C.W., 1992, Bezout number calculations for multi-homogeneous polynomial systems, Appl. Math. Comput., 51, 2

WAMPLER C.W., 1996, Proceedings of the 1996 ASME Design Engineering Technical Conference

10.1016/0094-114X(91)90024-X

10.1137/1028157

10.1145/29380.214343

10.1145/279232.279235

WISE S., 1998, POLSYS PLP: A partitioned linear product homotopy code for solving polynomial systems of equations.

WRIGHT A. H. 1985. Finding all solutions to a system of polynomial equations. Math. Comput. 44 (Jan. 1985) 125-133. WRIGHT A. H. 1985. Finding all solutions to a system of polynomial equations. Math. Comput. 44 (Jan. 1985) 125-133.