TY - JOUR A1 - Alhaddad, Samer A1 - Förstner, Jens A1 - Groth, Stefan A1 - Grünewald, Daniel A1 - Grynko, Yevgen A1 - Hannig, Frank A1 - Kenter, Tobias A1 - Pfreundt, F.J. A1 - Plessl, Christian A1 - Schotte, Merlind A1 - Steinke, Thomas A1 - Teich, J. A1 - Weiser, Martin A1 - Wende, Florian T1 - The HighPerMeshes Framework for Numerical Algorithms on Unstructured Grids JF - Concurrency and Computation: Practice and Experience N2 - Solving PDEs on unstructured grids is a cornerstone of engineering and scientific computing. Heterogeneous parallel platforms, including CPUs, GPUs, and FPGAs, enable energy-efficient and computationally demanding simulations. In this article, we introduce the HPM C++-embedded DSL that bridges the abstraction gap between the mathematical formulation of mesh-based algorithms for PDE problems on the one hand and an increasing number of heterogeneous platforms with their different programming models on the other hand. Thus, the HPM DSL aims at higher productivity in the code development process for multiple target platforms. We introduce the concepts as well as the basic structure of the HPM DSL, and demonstrate its usage with three examples. The mapping of the abstract algorithmic description onto parallel hardware, including distributed memory compute clusters, is presented. A code generator and a matching back end allow the acceleration of HPM code with GPUs. Finally, the achievable performance and scalability are demonstrated for different example problems. Y1 - 2022 U6 - https://doi.org/10.1002/cpe.6616 VL - 34 IS - 14 ER - TY - JOUR A1 - Alhaddad, Samer A1 - Förstner, Jens A1 - Groth, Stefan A1 - Grünewald, Daniel A1 - Grynko, Yevgen A1 - Hannig, Frank A1 - Kenter, Tobias A1 - Pfreundt, Franz-Josef A1 - Plessl, Christian A1 - Schotte, Merlind A1 - Steinke, Thomas A1 - Teich, Jürgen A1 - Weiser, Martin A1 - Wende, Florian T1 - HighPerMeshes - A Domain-Specific Language for Numerical Algorithms on Unstructured Grids JF - Euro-Par 2020: Parallel Processing Workshops. N2 - Solving partial differential equations on unstructured grids is a cornerstone of engineering and scientific computing. Nowadays, heterogeneous parallel platforms with CPUs, GPUs, and FPGAs enable energy-efficient and computationally demanding simulations. We developed the HighPerMeshes C++-embedded Domain-Specific Language (DSL) for bridging the abstraction gap between the mathematical and algorithmic formulation of mesh-based algorithms for PDE problems on the one hand and an increasing number of heterogeneous platforms with their different parallel programming and runtime models on the other hand. Thus, the HighPerMeshes DSL aims at higher productivity in the code development process for multiple target platforms. We introduce the concepts as well as the basic structure of the HighPer-Meshes DSL, and demonstrate its usage with three examples, a Poisson and monodomain problem, respectively, solved by the continuous finite element method, and the discontinuous Galerkin method for Maxwell’s equation. The mapping of the abstract algorithmic description onto parallel hardware, including distributed memory compute clusters is presented. Finally, the achievable performance and scalability are demonstrated for a typical example problem on a multi-core CPU cluster. Y1 - 2021 U6 - https://doi.org/10.1007/978-3-030-71593-9_15 SP - 185 EP - 196 PB - Springer ER - TY - JOUR A1 - Bartels, Tinko A1 - Fisikopoulos, Vissarion A1 - Weiser, Martin T1 - Fast Floating-Point Filters for Robust Predicates JF - BIT Numerical Mathematics N2 - Geometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geographic information systems and computer-aided design. With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail. This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations. The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this. We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions. We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed. We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations. Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations. Y1 - 2023 U6 - https://doi.org/10.1007/s10543-023-00975-x VL - 63 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - We present an efficient algorithm that finds a globally optimal solution to the 2D Free Flight Trajectory Optimization Problem (aka Zermelo Navigation Problem) up to arbitrary precision in finite time. The algorithm combines a discrete and a continuous optimization phase. In the discrete phase, a set of candidate paths that densely covers the trajectory space is created on a directed auxiliary graph. Then Yen’s algorithm provides a promising set of discrete candidate paths which subsequently undergo a locally convergent refinement stage. Provided that the auxiliary graph is sufficiently dense, the method finds a path that lies within the convex domain around the global minimizer. From this starting point, the second stage will converge rapidly to the optimum. The density of the auxiliary graph depends solely on the wind field, and not on the accuracy of the solution, such that the method inherits the superior asymptotic convergence properties of the optimal control stage. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.2 VL - 106 SP - 1 EP - 13 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - Newton's Method for Global Free Flight Trajectory Optimization JF - Operations Research Forum N2 - Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91846 VL - 4 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - A Discrete-Continuous Algorithm for Free Flight Planning JF - Algorithms N2 - We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach. KW - shortest path KW - flight planning KW - free flight KW - discrete-continuous algorithm KW - optimal control KW - discrete optimization Y1 - 2020 U6 - https://doi.org/10.3390/a14010004 SN - 1438-0064 VL - 14 IS - 1 SP - 4 PB - MDPI ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Danecker, Fabian A1 - Weiser, Martin T1 - Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition. Y1 - 2023 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2023.3 VL - 115 SP - 3:1 EP - 3:6 ER - TY - JOUR A1 - Carderera, Alejandro A1 - Pokutta, Sebastian A1 - Schütte, Christof A1 - Weiser, Martin T1 - CINDy: Conditional gradient-based Identification of Non-linear Dynamics – Noise-robust recovery JF - Journal of Computational and Applied Mathematics N2 - Governing equations are essential to the study of nonlinear dynamics, often enabling the prediction of previously unseen behaviors as well as the inclusion into control strategies. The discovery of governing equations from data thus has the potential to transform data-rich fields where well-established dynamical models remain unknown. This work contributes to the recent trend in data-driven sparse identification of nonlinear dynamics of finding the best sparse fit to observational data in a large library of potential nonlinear models. We propose an efficient first-order Conditional Gradient algorithm for solving the underlying optimization problem. In comparison to the most prominent alternative algorithms, the new algorithm shows significantly improved performance on several essential issues like sparsity-induction, structure-preservation, noise robustness, and sample efficiency. We demonstrate these advantages on several dynamics from the field of synchronization, particle dynamics, and enzyme chemistry. Y1 - 2021 ER - TY - CHAP A1 - Chegini, Fatemeh A1 - Froehly, Algiane A1 - Huynh, Ngoc Mai Monica A1 - Pavarino, Luca A1 - Potse, Mark A1 - Scacchi, Simone A1 - Weiser, Martin T1 - Efficient numerical methods for simulating cardiac electrophysiology with cellular resolution T2 - 10th Int. Conf. Computational Methods for Coupled Problems in Science and Engineering 2023 N2 - The cardiac extracellular-membrane-intracellular (EMI) model enables the precise geometrical representation and resolution of aggregates of individual myocytes. As a result, it not only yields more accurate simulations of cardiac excitation compared to homogenized models but also presents the challenge of solving much larger problems. In this paper, we introduce recent advancements in three key areas: (i) the creation of artificial, yet realistic grids, (ii) efficient higher-order time stepping achieved by combining low-overhead spatial adaptivity on the algebraic level with progressive spectral deferred correction methods, and (iii) substructuring domain decomposition preconditioners tailored to address the complexities of heterogeneous problem structures. The efficiency gains of these proposed methods are demonstrated through numerical results on cardiac meshes of different sizes. Y1 - 2023 UR - https://www.scipedia.com/public/2023f U6 - https://doi.org/10.23967/c.coupled.2023.004 ER - TY - JOUR A1 - Chegini, Fatemeh A1 - Kopanicakova, Alena A1 - Krause, Rolf A1 - Weiser, Martin T1 - Efficient Identification of Scars using Heterogeneous Model Hierarchies JF - EP Europace N2 - Aims. Detection and quantification of myocardial scars are helpful both for diagnosis of heart diseases and for building personalized simulation models. Scar tissue is generally charac­terized by a different conduction of electrical excitation. We aim at estimating conductivity-related parameters from endocardial mapping data, in particular the conductivity tensor. Solving this inverse problem requires computationally expensive monodomain simulations on fine discretizations. Therefore, we aim at accelerating the estimation using a multilevel method combining electrophysiology models of different complexity, namely the mono­domain and the eikonal model. Methods. Distributed parameter estimation is performed by minimizing the misfit between simulated and measured electrical activity on the endocardial surface, subject to the mono­domain model and regularization, leading to a constrained optimization problem. We formulate this optimization problem, including the modeling of scar tissue and different regularizations, and design an efficient iterative solver. We consider monodomain grid hierarchies and monodomain-eikonal model hierarchies in a recursive multilevel trust-region method. Results. From several numerical examples, both the efficiency of the method and the estimation quality, depending on the data, are investigated. The multilevel solver is significantly faster than a comparable single level solver. Endocardial mapping data of realistic density appears to be just sufficient to provide quantitatively reasonable estimates of location, size, and shape of scars close to the endocardial surface. Conclusion. In several situations, scar reconstruction based on eikonal and monodomain models differ significantly, suggesting the use of the more accurate but more expensive monodomain model for this purpose. Still, eikonal models can be utilized to accelerate the computations considerably, enabling the use of complex electrophysiology models for estimating myocardial scars from endocardial mapping data. Y1 - 2021 U6 - https://doi.org/10.1093/europace/euaa402 VL - 23 SP - i113 EP - i122 ER -