Abstract
The paper summarizes author’s investigations in tuning a multithreaded interval branch-and-prune algorithm for nonlinear systems and presents the developed solver. New results for using the box-consistency enforcing operator and a new variant of the initial exclusion phase are presented. Also, a new heuristic to choose the coordinate for bisection is considered. Extensive numerical experiments are analyzed to provide the satisfying version of the algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C++ extended scientific computing library. http://www.xsc.de (2013)
Intel Threading Building Blocks. http://www.threadingbuildingblocks.org (2013)
OpenBLAS library. http://xianyi.github.com/OpenBLAS/ (2013)
Difficult benchmark problems. http://www-sop.inria.fr/coprin/logiciels/ALIAS/Benches/node6.html (2014)
GNU linear programming kit. http://www.gnu.org/software/glpk/ (2014)
Non-polynomial nonlinear system benchmarks. https://www-sop.inria.fr/coprin/logiciels/ALIAS/Benches/node2.html (2014)
Realpaver. nonlinear constraint solving & rigorous global optimization. http://pagesperso.lina.univ-nantes.fr/info/perso/permanents/granvil/realpaver/ (2014)
Sobol sequence generator. http://web.maths.unsw.edu.au/fkuo/sobol/ (2014)
Beelitz, T., Bischof, C.H., Lang, B.: A hybrid subdivision strategy for result-verifying nonlinear solvers. Tech. Rep. 04/8, Bergische Universitiät Wuppertal (2004)
Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F.: Revising hull and box consistency. In: International Conference on Logic Programming, pp 230–244. The MIT Press (1999)
Benhamou, F., McAllester, D., Hentenryck, P.V.: CLP(intervals) revisited. In: Logic Programming, Proceedings of the 1994 International Symposium, pp 124–138. The MIT Press (1994)
van Emden, M.H.: Computing functional and relational box consistency by structured propagation in atomic constraint systems. arXiv:preprintcs/0106008 (2001)
Goldsztejn, A., Jaulin, L.: Inner and outer approximations of existentially quantified equality constraints. Lect. Notes Comput. Sci. 4204, 198–212 (2006)
Goualard, F.: On considering an interval constraint solving algorithm as a free-steering nonlinear Gauss-Seidel procedure. In: Proceedings of the 2005 ACM Symposium on Applied Computing, SAC ’05, pp.1434–1438, ACM, New York, NY, USA (2005). doi:10.1145/1066677.1067004
Goualard, F., Jermann, C.: A reinforcement learning approach to interval constraint propagation. Constraints 13(1-2), 206–226 (2008)
Granvilliers, L., Benhamou, F.: Progress in the solving of a circuit design problem. J. Glob. Optim. 20(2), 155–168 (2001)
Granvilliers, L., Benhamou, F.: Algorithm 852: Realpaver: an interval solver using constraint satisfaction techniques. ACM Trans. Math. Softw. (TOMS) 32(1), 138–156 (2006)
Hansen, E., Walster, W.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (2004)
Ishii, D., Goldsztejn, A., Jermann, C.: Interval-based projection method for under-constrained numerical systems. Constraints 17(4), 432–460 (2012)
Kearfott, R.B.: Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht (1996)
Kolev, L.V.: An improved interval linearization for solving nonlinear problems. Numeri. Algorithm. 37(1-4), 213–224 (2004)
Kubica, B.J.: Intel TBB as a tool for parallelization of an interval solver of nonlinear equations systems. Tech. Rep. 09-02, ICCE WUT (2009)
Kubica, B.J.: Performance inversion of interval Newton narrowing operators. Prace Naukowe Politechniki Warszawskiej. Elektronika 169, 111–119 (2009). KAEiOG 2009 Proceedings
Kubica, B.J.: Shared-memory parallelization of an interval equations systems solver – comparison of toos. Prace Naukowe Politechniki Warszawskiej. Elektronika 169, 121–128 (2009). KAEiOG, 2009 Proceedings
Kubica, B.J.: Interval methods for solving underdetermined nonlinear equations systems. Reliable Computing 15, 207–217 (2011). SCAN 2008 Proceedings
Kubica, B.J.: Exclusion regions in the interval solver of underdetemined nonlinear systems. Tech. Rep. 12-01, ICCE WUT (2012)
Kubica, B.J.: Tuning the multithreaded interval method for solving underdetermined systems of nonlinear equations. Lect. Notes Comput. Sci. 7204, 467–476 (2012). PPAM 2011 Proceedings
Kubica, B.J.: Excluding regions using Sobol sequences in an interval branch-and-prune method for nonlinear systems. Reliab. Comput. 19(4), 385–397 (2014). SCAN 2012 Proceedings
Kubica, B.J.: Using quadratic approximations in an interval method for solving underdetermined and well-determined nonlinear systems. Lect. Notes Comput. Sci. 8385, 623–633 (2014). PPAM 2013 Proceedings
Kubica, B.J., Woźniak, A.: Using the second-order information in Pareto-set computations of a multi-criteria problem. Lect. Notes Comput. Sci. 7134, 137–147 (2012). PARA 2010 Proceedings
Meyn, K.H.: Solution of underdetermined nonlinear equations by stationary iteration methods. Numer. Math. 42, 161–172 (1983)
Neumaier, A.: The enclosure of solutions of parameter-dependent systems of equations. In: Reliability in Computing, pp. 269–286. Academic Press (1988)
Puget, J.F., Hentenryck, P.V.: A constraint satisfaction approach to a circuit design problem. J. Glob. Optim. 13(1), 75–93 (1998)
Ratschek, H., Rokne, J.: Experiments using interval analysis for solving a circuit design problem. J. Glob. Optim. 3(4), 501–518 (1993)
Rheinboldt, W.C.: Computation of critical boundaries on equilibrium manifolds. SIAM J. Numer. Anal. 19, 653–669 (1982)
Shary, S.P.: An interval linear tolerance problem. Autom. Remote. Control. 65, 1653–1666 (2004)
Shary, S.P.: Finite-dimensional Interval Analysis. XYZ. Electronic book (in Russian). (accessed 2014.05.15) (2013). http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
About this article
Cite this article
Kubica, B.J. Presentation of a highly tuned multithreaded interval solver for underdetermined and well-determined nonlinear systems. Numer Algor 70, 929–963 (2015). https://doi.org/10.1007/s11075-015-9980-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-015-9980-y