Some tests of generalized bisection

ABSTRACT

This paper addresses the task of reliably finding approximations to all solutions to a system of nonlinear equations within a region defined by bounds on each of the individual coordinates. Various forms of generalized bisection were proposed some time ago for this task. This paper systematically compares such generalized bisection algorithms to themselves, to continuation methods, and to hybrid steepest descent/quasi-Newton methods. A specific algorithm containing novel “expansion” and “exclusion” steps is fully described, and the effectiveness of these steps is evaluated. A test problem consisting of a small, high-degree polynomial system that is appropriate for generalized bisection, but very difficult for continuation methods, is presented. This problem forms part of a set of 17 test problems from published literature on the methods being compared; this test set is fully described here.

REFERENCES

• 1: ALEFELD, G., AND HERZBERGER, J. Introduction to Interval Computations. Academic Press, New York, 1983.
• 2: ALEFELD, G., AND PLATZ0DER, L. A quadratically convergent Krawczyk-like algorithm. SIAM J. Numer. Anal. 20, 1 (Feb. 1983), 210-219.
• 3: CRARY, F. The AUGMENT precompiler, Mathematics Research Center Rep. 1470, Univ. of Wisconsin, Madison, 1976.
• 4: DONGARRA, J.J. Performance of various computers using standard linear equations software in a Fortran environment. Mathematics and Computer Science Memo 23, Argonne National Lab., Argonne, Ill., 1985.
• 5: A. Eiger , K. Sikorski , F. Stenger, A bisection method for systems of nonlinear equations, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.367-377, Dec. 1984 [doi>10.1145/2701.2705]
• 6: HANSEN, E.R. Interval forms of Newton's method. Computing 20 (1978), 153-163.
• 7: HANSEN, E.R. A globally convergent interval method for computing and bounding real roots. BIT 18, 4 (1978), 415-424.
• 8: HANSEN, E. R., AND GREENBERG, R.i. An interval Newton method. Appl. Math. Cornput. 12 (1983), 89-98.
• 9: HANSEN, E. R., AND SENGUPTA, S. Bounding solutions of systems of equations using interval arithmetic. BIT 21 (1981), 203-211.
• 10: KEARFOTT, R.B. On a general technique for finding directions proceeding from bifurcation points. In Numerical Methods for Bifurcation Problems. T. Kfipper, H. D. Mittelmann, and H. Weber, Eds, International Series of Numerical Mathematics 70, Birkh~iuser, Boston, 1984, 210-218.
• 11: KEARFOTT, R.B. Abstract generalized bisection and a cost bound. Math. Comput. 49, 179 (July 1987), 187-202.
• 12: Keith Meintjes , Alexander P Morgan, A methodology for solving chemical equilibrium systems, Applied Mathematics and Computation, v.22 n.4, p.333-361, June 1987 [doi>10.1016/0096-3003(87)90076-2]
• 13: MOORE, R.E. A test for existence of solutions to nonlinear systems. SIAM J. Numer. Anal. 14, 4 {Sept. 1977), 611-615.
• 14: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 15: MOORE, R. E., AND JONES, S.T. Safe starting regions for iterative methods. SIAM J. Numer. Anal. 14, 6 (Dec. 1977), 1051-1065.
• 16: MOORE, R. E., AND QI, L. A successive interval test for nonlinear systems. SIAM J. Numer. Anal. 19, 4 (Aug. 1982), 845-850.
• 17: MOR~, J. J., GARBOW, B. S., AND HILLSTROM, K.E. User Guide for MINPACK-1. Rep. ANL- 80-74, Argonne National Labs., Argonne, Ill., 1980.
• 18: Jorge J. Moré , Burton S. Garbow , Kenneth E. Hillstrom, Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.17-41, March 1981 [doi>10.1145/355934.355936]
• 19: Alexander P. Morgan, A Method for Computing All Solutions to Systems of Polynomials Equations, ACM Transactions on Mathematical Software (TOMS), v.9 n.1, p.1-17, March 1983 [doi>10.1145/356022.356023]
• 20: MORGAN, A.P. Solving Polynomial Systems Using Continuation {or Engineering and Scientific Problems, Prentice-Hall, Englewood Cliffs, N.J., 1987.
• 21: Alexander Morgan , Vadim Shapiro, Box-bisection for solving second-degree systems and the problem of clustering, ACM Transactions on Mathematical Software (TOMS), v.13 n.2, p.152-167, June 1987 [doi>10.1145/328512.328521]
• 22: NEUMAIER, A. Interval iteration for zeros of systems of equations, BIT 25, 1 (1985), 256-273.
• 23: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 24: TSAI, L. W., AND MORGAN, A.P. Solving the kinematics of the most general six- and fivedegree-of-freedom manipulators by continuation methods. Rep. GMR-4631, General Motors Research Labs., Warren, Mich., 1984. (To be published in the ASME J. Mechanisms, Transmissions, and Automation in Design.
• 25: J. M. Yohe, Software for Interval Arithmetic: A Reasonably Portable Package, ACM Transactions on Mathematical Software (TOMS), v.5 n.1, p.50-63, March 1979 [doi>10.1145/355815.355819]

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for; Systems of equations

General Terms:
Algorithms, Performance, Theory