×

Efficient task scheduling in the parallel result-verifying solution of nonlinear systems. (English) Zbl 1083.65051

Summary: Nonlinear systems occur in diverse applications, e.g., in the steady state analysis of chemical processes. If safety concerns require the results to be provably correct then result-verifying algorithms relying on interval arithmetic should be used for solving these systems. Since such algorithms are very computationally intensive, the coarse-grained inter-box parallelism should be exploited to make them feasible in practice.
We briefly describe our framework SONIC for the verified solution of nonlinear systems and give detailed information about its parallelization with OpenMP and MPI. Our numerical results show that the implemented parallelization schemes are indeed successful. The more sophisticated MPI implementation seems to be superior to the easy-to-implement OpenMP version and shows almost linear speed up up to a large number of processors.

MSC:

65H10 Numerical computation of solutions to systems of equations
65Y05 Parallel numerical computation
65G30 Interval and finite arithmetic
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] An Mey, D.: Two OpenMP Programming Patterns, in: An Mey, D. (ed.), Proc. EWOMP ’03, September 22–26, 2003, Aachen, Germany, Aachen, 2004, pp. 51–60.
[2] Babichev, A. B., Kashevarova, T. P., Leshchenko, A. S., and Semenov, A. L.: UniCalc: An Intelligent Solver for Mathematical Problems, in: Proc. of the East-West Conference on Artificial Intelligence: From Theory to Practice (EWAIC’93), Moscow, 1993, pp. 257–260. · Zbl 0829.65067
[3] Beelitz, T., Bischof, C. H., and Lang, B.: A Hybrid Subdivision Strategy for Result-Verifying Nonlinear Solvers, in: Proc. Applied Mathematics and Mechanics (PAMM), Vol. 4, 2004, pp. 632–633. · Zbl 1354.65114 · doi:10.1002/pamm.200410297
[4] Beelitz, T., Bischof, C. H., and Lang, B.: Intervals and OpenMP: Towards an Efficient Parallel Result-Verifying Nonlinear Solver, in: An Mey, D. (ed.), Proc. EWOMP ’03, September 22–26, 2003, Aachen, Germany, Aachen, 2003, pp. 119–125.
[5] Beelitz, T., Bischof, C. H., Lang, B., and Willems, P.: SONIC–A Framework for the Rigorous Solution of Nonlinear Problems, Preprint BUW-SC 04/7, 2004.
[6] Bischof, C. H., Lang, B., Marquardt, W., and Mönnigmann, M.: Verified Determination of Singularities in Chemical Processes, in: Krämer, W. and Wolff von Gudenberg, J. (eds): Scientific Computing, Validated Numerics, Interval Methods, Kluwer Academic/Plenum Publishers, New York, 2001, pp. 305–316. · Zbl 1395.92192
[7] GlobSol home page: http://www.mcsu.mu.edu/\(\sim\)globsol.
[8] Golubitsky, M. and Schaeffer, D. G.: Singularities and Groups in Bifurcation Theory, Volume I, Springer-Verlag, New York, 1985. · Zbl 0607.35004
[9] Hammer, R., Hocks, M., Kulisch, U., and Ratz, D.: C++ Toolbox for Verified Computing–Basic Numerical Problems, Springer-Verlag, Heidelberg, 1995. · Zbl 0828.68041
[10] Hofschuster, W. and Krämer, W.: C-XSC 2.0–A C++ Library for Extended Scientific Computing, in: Alt, R. et al. (eds): Numerical Software with Result Verification, LNCS 2991, Springer, Heidelberg, pp. 15–35. · Zbl 1126.65328
[11] Hofschuster, W., Krämer, W., Lerch, M., Tischler, G., and Wolff von Gudenberg, J.: filib-++–A Fast Interval Library Supporting Containment Computations, to appear in ACM Trans. Math. Software, 2006. · Zbl 1365.65140
[12] Intel Corporation: KAI C++ User’s Guide, 2001, http://www.kai.com/kpts/-guide.
[13] Intel Corporation: Intel C++ Compiler User’s Guide, 2003, http://developer.intel.com/software/products/compilers.
[14] Kearfott, R. B.: Rigorous Global Search: Continuous Problems, Kluwer Academic Publishers, Dordrecht, 1996. · Zbl 0876.90082
[15] Lebbah, Y., Michel, C., Rueher, M., Daney, D., and Merlet, J.-R: Efficient and Safe Global Constraints for Handling Numeric Constraint Systems, SIAM J. Numer. Anal. 42 (5) (2005), pp. 2076–2097. · Zbl 1082.65051 · doi:10.1137/S0036142903436174
[16] Message Passing Interface Forum: MPI: A Message-Passing Interface Standard, 1994, http://www.mpi-forum.org. · Zbl 0825.68198
[17] Message Passing Interface Forum: MPI-2: Extensions to the Message-Passing Interface, 1997, http://www.mpi-forum.org.
[18] Mönnigmann, M., Marquardt, W., Bischof, C. H., Beelitz, T., Lang, B., and Willems, P.: A Hybrid Approach for Efficient Robust Design of Dynamic Systems, Preprint BUW-SC 2004/9, 2004. · Zbl 1114.93034
[19] Neumaier, A.: Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, 1990. · Zbl 0715.65030
[20] Sun Microsystems: Sun Studio 9: C++ Interval Arithmetic Programming Reference, http://docs.sun.com/app/docs/doc/817–6705.
[21] Willems, P.: Symbolisch-numerische Techniken zum verifizierten Lösen nichtlinearer Gleichungs- systeme, Diplomarbeit, RWTH Aachen University, 2004.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.