Article

Solving Nonlinear Systems by Constraint Inversion and Interval Arithmetic

Authors:

Martine Ceberio,

Laurent GranvilliersAuthors Info & Claims

AISC '00: Revised Papers from the International Conference on Artificial Intelligence and Symbolic Computation

Pages 127 - 141

Published: 17 July 2000 Publication History

Abstract

A reliable symbolic-numeric algorithm for solving nonlinear systems over the reals is designed. The symbolic step generates a new system, where the formulas are different but the solutions are preserved, through partial factorizations of polynomial expressions and constraint inversion. The numeric step is a branch-and-prune algorithm based on interval constraint propagation to compute a set of outer approximations of the solutions. The processing of the inverted constraints by interval arithmetic provides a fast and efficient method to contract the variables' domains. A set of experiments for comparing several constraint solvers is reported.

References

[1]

Götz Alefeld and Jürgen Herzberger. Introduction to Interval Computations. Academic Press, 1983.

[2]

Philippe Aubry, Daniel Lazard, and Marc Moreno Maza. On the Theories of Triangular Sets. Journal of Symbolic Computation, 28:105-124, 1998.

[3]

FrÉdÉric Benhamou and Laurent Granvilliers. Combining Local Consistency, Symbolic Rewriting and Interval Methods. In J. Calmet, J.A. Campbell, and J. Pfalzgraf, editors, Proceedings of the 3rd International Conference on Artificial Intelligence and Symbolic Mathematical Computation, volume 1138 of LNCS, pages 144-159, Steyr, Austria, 1996. Springer-Verlag.

[4]

Dario Bini and Bernard Mourrain. Handbook of Polynomial Systems. http://www-sop.inria.fr/saga/POL/, 1996.

[5]

Bruno Buchberger. Gröbner Bases: an Algorithmic Method in Polynomial Ideal Theory. In Multidimensional Systems Theory, pages 184-232. D. Reidel Publishing Company, 1985.

[6]

John G. Cleary. Logical Arithmetic. Future Computing Systems, 2(2):125-149, 1987.

[7]

Georges Edwin Collins and Hoon Hong. Partial Cylindrical Algebraic Decomposition for Quantifier Elimination. Journal of Symbolic Computation, 12(3):299-328, 1991.

[8]

Eldon Robert Hansen. Global Optimization using Interval Analysis. Marcel Dekker, 1992.

[9]

Ralph Baker Kearfott. Some Tests of Generalized Bisection. ACM Transactions on Mathematical Software, 13(3):197-220, 1987.

[10]

Shankar Krishnan and Dinesh Manocha. Numeric-symbolic Algorithms for Evaluating One-dimensional Algebraic Sets. In Proceedings of International Symposium on Symbolic and Algebraic Computation, pages 59-67. ACM Press, 1995.

[11]

Alan K. Mackworth. Consistency in Networks of Relations. Artificial Intelligence, 8(1):99-118, 1977.

[12]

Kyoko Makino and Martin Berz. Efficient Control of the Dependency Problem based on Taylor Model Method. Reliable Computing, 5:3-12, 1999.

[13]

Ramon Edgar Moore. Interval Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1966.

[14]

Volker Stahl. Interval Methods for Bounding the Range of Polynomials and Solving Systems of Nonlinear Equations. PhD thesis, University of Linz, Austria, 1995.

[15]

Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. Texts in Applied Mathematics. Springer, 2nd edition, 1993.

[16]

Maarten Hermann Van Emden. Canonical extensions as common basis for interval constraints and interval arithmetic. In F. Benhamou, editor, Proceedings of the 6th French Conference on Logic Programming and Constraint Programming, pages 71-83. Hermès, 1997.

[17]

Pascal Van Hentenryck, David McAllester, and Deepak Kapur. Solving Polynomial Systems Using a Branch and Prune Approach. SIAM Journal on Numerical Analysis, 34(2):797-827, 1997.

[18]

Pascal Van Hentenryck, Laurent Michel, and Yves Deville. Numerica: a Modeling Language for Global Optimization. MIT Press, 1997.

[19]

Jan Verschelde. Database of Polynomial Systems. Michigan State University, USA, 1999. http://www.math.msu.edu/~jan/demo.html.

[20]

Jan Verschelde. PHCpack: A General-purpose Solver for Polynomial Systems by Homotopy Continuation. ACM Transactions on Mathematical Software, 25(2):251-276, 1999.

Cited By

Desrochers BJaulin L(2016)A minimal contractor for the polar equationEngineering Applications of Artificial Intelligence10.1016/j.engappai.2016.06.00555:C(83-92)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.engappai.2016.06.005
Goualard FHaddad HOmicini AWainwright R(2005)On considering an interval constraint solving algorithm as a free-steering nonlinear Gauss-Seidel procedureProceedings of the 2005 ACM symposium on Applied computing10.1145/1066677.1067004(1434-1438)Online publication date: 13-Mar-2005
https://dl.acm.org/doi/10.1145/1066677.1067004
Ceberio MKreinovich V(2004)Greedy algorithms for optimizing multivariate Horner schemesACM SIGSAM Bulletin10.1145/980175.98017938:1(8-15)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1145/980175.980179
Show More Cited By

Solving Nonlinear Systems by Constraint Inversion and Interval Arithmetic
1. Mathematics of computing
  1. Mathematical analysis

Recommendations

Analytic constraint solving and interval arithmetic
POPL '00: Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

In this paper we describe the syntax, semantics, and implementation of the constraint logic programming language CLP(F) and we prove that the implementation is sound. A CLP(F) constraint is a conjunction of equations and inequations in a first order ...
Resolution of nonlinear interval problems using symbolic interval arithmetic

An interval problem is a problem where the unknown variables take interval values. Such a problem can be defined by interval constraints, such as ''the interval [a,b]@?[a,b]^2''. Interval problems often appear when we want to analyze the behavior of an ...
Solving dynamic constraint optimization problems using ICHEA
ICONIP'12: Proceedings of the 19th international conference on Neural Information Processing - Volume Part III

Many real-world constrained problems have a set of predefined static constraints that can be solved by evolutionary algorithms (EAs) whereas some problems have dynamic constraints that may change over time or may be received by the problem solver at run ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AISC '00: Revised Papers from the International Conference on Artificial Intelligence and Symbolic Computation

July 2000

252 pages

ISBN:3540420711

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 July 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Desrochers BJaulin L(2016)A minimal contractor for the polar equationEngineering Applications of Artificial Intelligence10.1016/j.engappai.2016.06.00555:C(83-92)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.engappai.2016.06.005
Goualard FHaddad HOmicini AWainwright R(2005)On considering an interval constraint solving algorithm as a free-steering nonlinear Gauss-Seidel procedureProceedings of the 2005 ACM symposium on Applied computing10.1145/1066677.1067004(1434-1438)Online publication date: 13-Mar-2005
https://dl.acm.org/doi/10.1145/1066677.1067004
Ceberio MKreinovich V(2004)Greedy algorithms for optimizing multivariate Horner schemesACM SIGSAM Bulletin10.1145/980175.98017938:1(8-15)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.1145/980175.980179
Granvilliers LMonfroy EBenhamou FKaltofen EVillard G(2001)Symbolic-interval cooperation in constraint programmingProceedings of the 2001 international symposium on Symbolic and algebraic computation10.1145/384101.384123(150-166)Online publication date: 1-Jul-2001
https://dl.acm.org/doi/10.1145/384101.384123

View Options

View options

Figures

Tables

Media

View Table of Conten