A three-level parallelisation scheme and application to the Nelder-Mead algorithm

DOI10.3846/MMA.2020.12139MaRDI QIDQ5016267zbMATH OpenOpenAlexFDO

Authors Rima Kriauzienė, Andrej Bugajev, Raimondas Čiegis

Publication date 13 December 2021

Published in Mathematical Modelling and Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1904.05208

zbMATH Keywords

finite difference methodsload balancing and task assignmentmodel-based parallelisationmulti-level parallelisationNelder-Mead algorithmparallel optimisationSchrödinger equationWang's algorithm

Mathematics Subject Classification ID

Ginzburg-Landau equations (35Q56) Finite difference methods for initial value and initial-boundary value problems involving PDEs (65M06) Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs (65M12) Parallel numerical computation (65Y05)

Abstract: We consider a three-level parallelisation scheme. The second and third levels define a classical two-level parallelisation scheme and some load balancing algorithm is used to distribute tasks among processes. It is well-known that for many applications the efficiency of parallel algorithms of the second and third level starts to drop down after some critical parallelisation degree is reached. This weakness of the two-level template is addressed by introduction of one additional parallelisation level. As an alternative to the basic solver some new or modified algorithms are considered on this level. The idea of the proposed methodology is to increase the parallelisation degree by using less efficient algorithms in comparison with the basic solver. As an example we investigate two modified Nelder-Mead methods. For the selected application, a few partial differential equations are solved numerically on the second level, and on the third level the parallel Wang's algorithm is used to solve systems of linear equations with tridiagonal matrices. A greedy workload balancing heuristic is proposed, which is oriented to the case of a large number of available processors. The complexity estimates of the computational tasks are model-based, i.e. they use empirical computational data.

Recommendations

• A parallel implementation of the simplex function minimization routine
• The parallel downhill simplex algorithm for unconstrained optimisation
• scientific article; zbMATH DE number 802433
• scientific article; zbMATH DE number 4068628
• Direct Search Methods on Parallel Machines

Cites work

• A parallel implementation of the simplex function minimization routine
• A Parallel Method for Tridiagonal Equations
• A Simplex Method for Function Minimization
• AN IMPLEMENTATION OF A PARALLEL GENERALIZED BRANCH AND BOUND TEMPLATE
• Convergence of the Nelder--Mead Simplex Method to a Nonstationary Point
• Design of Absorbing Boundary Conditions for Schrödinger Equations in $\mathbbR$^d
• Exploiting multi-core and many-core parallelism for subspace clustering
• scientific article; zbMATH DE number 1728269 (Why is no real title available?)
• scientific article; zbMATH DE number 1274356 (Why is no real title available?)
• scientific article; zbMATH DE number 2086813 (Why is no real title available?)
• Improved scheme for selection of potentially optimal hyper-rectangles in \texttt{DIRECT}
• On compact high order finite difference schemes for linear Schrödinger problem on non-uniform meshes
• ON THE ACCURACY OF SOME ABSORBING BOUNDARY CONDITIONS FOR THE SCHRODINGER EQUATION
• Optimization by simulated annealing
• Remarks on discrete and semi-discrete transparent boundary conditions for solving the time-dependent Schrödinger equation on the half-axis
• Sequential Application of Simplex Designs in Optimisation and Evolutionary Operation
• Tabu Search—Part I
• Tabu Search—Part II
• The Nelder-Mead simplex algorithm with perturbed centroid for high-dimensional function optimization
• Two-level parallelization of a fluid mechanics algorithm exploiting hardware heterogeneity

This page was built for publication: A three-level parallelisation scheme and application to the Nelder-Mead algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5016267)