Refine
Year of publication
Document Type
- Article (55)
- ZIB-Report (42)
- In Proceedings (11)
- In Collection (9)
- Book (4)
- Book chapter (3)
- Report (1)
Is part of the Bibliography
- no (125)
Keywords
- optimal control (14)
- interior point methods in function space (5)
- trajectory storage (4)
- discretization error (3)
- finite elements (3)
- lossy compression (3)
- Newton-CG (2)
- complementarity functions (2)
- compression (2)
- finite element method (2)
Institute
- Numerical Mathematics (125) (remove)
A primal interior point method for control constrained optimal control problems with PDE constraints is considered. Pointwise elimination of the control leads to a homotopy in the remaining state and dual variables, which is addressed by a short step pathfollowing method. The algorithm is applied to the continuous, infinite dimensional problem, where discretization is performed only in the innermost loop when solving linear equations. The a priori elimination of the least regular control permits to obtain the required accuracy with comparable coarse meshes. Convergence of the method and discretization errors are studied, and the method is illustrated at two numerical examples.
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.
We consider a linear iterative solver for large scale linearly constrained quadratic minimization problems that arise, for example, in optimization with PDEs. By a primal-dual projection (PDP) iteration, which can be interpreted and analysed as a gradient method on a quotient space, the given problem can be solved by computing sulutions for a sequence of constrained surrogate problems, projections onto the feasible subspaces, and Lagrange multiplier updates. As a major application we consider a class of optimization problems with PDEs, where PDP can be applied together with a projected cg method using a block triangular constraint preconditioner. Numerical experiments show reliable and competitive performance for an optimal control problem in elasticity.
Adaptation of antenna profiles for control of MR guided hyperthermia (HT) in a hybrid MR-HT system
(2007)
In an aging society where the number of joint replacements rises, it is important to also increase the longevity of implants.
In particular hip implants have a lifetime of at most 15 years. This derives primarily from
pain due to implant migration, wear, inflammation, and dislocation, which is affected by
the positioning of the implant during the surgery. Current joint replacement practice uses
2D software tools and relies on the experience of surgeons. Especially the 2D tools fail to
take the patients’ natural range of motion as well as stress distribution in the 3D joint
induced by different daily motions into account.
Optimizing the hip joint implant position for all possible parametrized motions under the
constraint of a contact problem is prohibitively expensive as there are too many motions
and every position change demands a recalculation of the contact problem. For the
reduction of the computational effort, we use adaptive refinement on the parameter
domain coupled with the interpolation method of Kriging. A coarse initial grid is to be
locally refined using goal-oriented error estimation, reducing locally high variances. This
approach will be combined with multi-grid optimization such that numerical errors are
reduced.
Adaptive Gaussian Process Regression for Efficient Building of Surrogate Models in Inverse Problems
(2023)
In a task where many similar inverse problems must be solved, evaluating costly simulations is impractical. Therefore, replacing the model y with a surrogate model y(s) that can be evaluated quickly leads to a significant speedup. The approximation quality of the surrogate model depends strongly on the number, position, and accuracy of the sample points. With an additional finite computational budget, this leads to a problem of (computer) experimental design. In contrast to the selection of sample points, the trade-off between accuracy and effort has hardly been studied systematically. We therefore propose an adaptive algorithm to find an optimal design in terms of
position and accuracy. Pursuing a sequential design by incrementally appending the computational budget leads to a convex and constrained optimization problem. As a surrogate, we construct a Gaussian process regression model. We measure the global approximation error in terms of its impact on the accuracy of the identified parameter and aim for a uniform absolute tolerance, assuming that y(s) is computed by finite element calculations. A priori error estimates and a coarse estimate of computational effort relate the expected improvement of the surrogate model error to computational effort, resulting in the most efficient combination of sample point and evaluation tolerance. We also allow for improving the accuracy of already existing sample points by continuing previously truncated finite element solution procedures.
The paper extends affine conjugate Newton methods from convex to nonconvex minimization, with particular emphasis on PDE problems originating from compressible hyperelasticity. Based on well-known schemes from finite dimensional nonlinear optimization, three different algorithmic variants are worked out in a function space setting, which permits an adaptive multilevel finite element implementation. These algorithms are tested on two well-known 3D test problems and a real-life example from surgical operation planning.
An affine invariant convergence analysis for inexact augmented Lagrangian-SQP methods is presented. The theory is used for the construction of an accuracy matching between iteration errors and truncation errors, which arise from the inexact linear system solves. The theoretical investigations are illustrated numerically by an optimal control problem for the Burgers equation.
We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery.
We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery.
We consider a shape implant design problem that arises in the context of facial surgery.
We introduce a reformulation as an optimal control problem, where the control acts
as a boundary force. The state is modelled as a minimizer of a polyconvex
hyperelastic energy functional. We show existence of optimal solutions and
derive - on a formal level - first order optimality conditions. Finally, preliminary numerical results
are presented.
We consider a shape implant design problem that arises in the context of facial surgery.
We introduce a reformulation as an optimal control problem, where the control acts
as a boundary force. The state is modelled as a minimizer of a polyconvex
hyperelastic energy functional. We show existence of optimal solutions and
derive - on a formal level - first order optimality conditions. Finally, preliminary numerical results
are presented.
The paper presents a new affine invariant theory on asymptotic mesh independence of Newton's method in nonlinear PDEs. Compared to earlier attempts, the new approach is both much simpler and more natural from the algorithmic point of view. The theory is exemplified at collocation methods for ODE boundary value problems and at finite element methods for elliptic PDE problems.
Temperature based death time estimation is based either on simple phenomenological models of corpse cooling or on detailed physical heat transfer models. The latter are much more complex, but allow a higher accuracy of death time estimation as in principle all relevant cooling mechanisms can be taken into account. Here, a complete work flow for finite element based cooling simulation models is presented.
The following steps are demonstrated on CT-phantoms:
• CT-scan
• Segmentation of the CT images for thermodynamically relevant features of individual
geometries
• Conversion of the segmentation result into a Finite Element (FE) simulation model
• Computation of the model cooling curve
• Calculation of the cooling time
For the first time in FE-based cooling time estimation the steps from the CT image over segmentation to FE model generation are semi-automatically performed. The cooling time calculation results are compared to cooling measurements performed on the phantoms under controlled conditions. In this context, the method is validated using different CTphantoms. Some of the CT phantoms thermodynamic material parameters had to be experimentally determined via independent experiments. Moreover the impact of geometry and material parameter uncertainties on the estimated cooling time is investigated by a sensitivity analysis.
We consider an optimal control problem from hyperthermia treatment planning and its barrier regularization. We derive basic results, which lay the groundwork for the computation of optimal solutions via an interior point path-following method. Further, we report on a numerical implementation of such a method and its performance at an example problem.
We consider an optimal control problem from hyperthermia treatment planning and its barrier regularization. We derive basic results, which lay the groundwork for the computation of optimal solutions via an interior point path-following method. Further, we report on a numerical implementation of such a method and its performance at an example problem.
CINDy: Conditional gradient-based Identification of Non-linear Dynamics – Noise-robust recovery
(2021)
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.
Solvers for partial differential equations (PDEs) are one of the cornerstones of computational science. For large problems, they involve huge amounts of data that need to be stored and transmitted on all levels of the memory hierarchy. Often, bandwidth is the limiting factor due to the relatively small arithmetic intensity, and increasingly due to the growing disparity between computing power and bandwidth. Consequently, data compression techniques have been investigated and tailored towards the specific requirements of PDE solvers over the recent decades. This paper surveys data compression challenges and discusses examples of corresponding solution approaches for PDE problems, covering all levels of the memory hierarchy from mass storage up to the main memory. We illustrate concepts for particular methods, with examples, and give references to alternatives.
Container Adaptors
(1999)
The C++ standard template library has many useful containers for data. The standard library includes two adpators, queue, and stack. The authors have extended this model along the lines of relational database semantics. Sometimes the analogy is striking, and we will point it out occasionally. An adaptor allows the standard algorithms to be used on a subset or modification of the data without having to copy the data elements into a new container. The authors provide many useful adaptors which can be used together to produce interesting views of data in a container.
Pulse thermography is a non-destructive testing method based on infrared imaging of transient thermal patterns. Heating the surface of the structure under test for a short period of time generates a non-stationary temperature distribution and thus a thermal contrast between the defect and the sound material. Due to measurement noise, preprocessing of the experimental data is necessary, before reconstruction algorithms can be applied. We propose a decomposition of the measured temperature into Green's function solutions to eliminate noise.
Pulse thermography is a non-destructive testing method based on infrared imaging of transient thermal patterns. Heating the surface of the structure under test for a short period of time generates a non-stationary temperature distribution and thus a thermal contrast between the defect and the sound material. Due to measurement noise, preprocessing of the experimental data is necessary, before reconstruction algorithms can be applied. We propose a decomposition of the measured temperature into Green's function solutions to eliminate noise.
The biodomain model of cardioelectric excitation consists of a reaction‐diffusion equation, an elliptic algebraic constraint, and a set of pointwise ODEs. Fast reaction enforces small time steps, such that for common mesh sizes the reaction‐diffusion equation is easily solved implicitly due to a dominating mass matrix. In contrast, the elliptic constraint does not benefit from small time steps and requires a comparably expensive solution. We propose a delayed residual compensation that improves the solution of the elliptic constraint and thus alleviates the need for long iteration times.
Pulse thermography of concrete structures is used in civil engineering for detecting voids, honeycombing and delamination. The physical situation is readily modeled by Fourier's law. Despite the simplicity of the PDE structure, quantitatively realistic numerical 3D simulation faces two major obstacles. First, the short heating pulse induces a thin boundary layer at the heated surface which encapsulates all information and therefore has to be resolved faithfully. Even with adaptive mesh refinement techniques, obtaining useful accuracies requires an unsatisfactorily fine discretization. Second, bulk material parameters and boundary conditions are barely known exactly. We address both issues by a semi-analytic reformulation of the heat transport problem and by parameter identification. Numerical results are compared with measurements of test specimens.
Pulse thermography of concrete structures is used in civil engineering for detecting voids, honeycombing and delamination. The physical situation is readily modeled by Fourier's law. Despite the simplicity of the PDE structure, quantitatively realistic numerical 3D simulation faces two major obstacles. First, the short heating pulse induces a thin boundary layer at the heated surface which encapsulates all information and therefore has to be resolved faithfully. Even with adaptive mesh refinement techniques, obtaining useful accuracies requires an unsatisfactorily fine discretization. Second, bulk material parameters and boundary conditions are barely known exactly. We address both issues by a semi-analytic reformulation of the heat transport problem and by parameter identification. Numerical results are compared with measurements of test specimens.
We consider Large Deformation Diffeomorphic Metric Mapping of general $m$-currents. After stating an optimization algorithm in the function space of admissable morph generating velocity fields, two innovative aspects in this framework are presented and numerically investigated: First, we spatially discretize the velocity field with conforming adaptive finite elements and discuss advantages of this new approach. Second, we directly compute the temporal evolution of discrete $m$-current attributes.
We consider Large Deformation Diffeomorphic Metric Mapping of general $m$-currents. After stating an optimization algorithm in the function space of admissable morph generating velocity fields, two innovative aspects in this framework are presented and numerically investigated: First, we spatially discretize the velocity field with conforming adaptive finite elements and discuss advantages of this new approach. Second, we directly compute the temporal evolution of discrete $m$-current attributes.
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 characterized 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 monodomain 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 monodomain 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.
Efficient numerical methods for simulating cardiac electrophysiology with cellular resolution
(2023)
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.
Cardiac electrograms are an important tool to study the spread of excitation waves inside the heart, which in turn underlie muscle contraction. Electrograms can be used to analyse the dynamics of these waves, e.g. in fibrotic tissue. In computational models, these analyses can be done with greater detail than during minimally invasive in vivo procedures. Whilst homogenised models have been used to study electrogram genesis, such analyses have not yet been done in cellularly resolved models. Such high resolution may be required to develop a thorough understanding of the mechanisms behind abnormal excitation patterns leading to arrhythmias. In this study, we derived electrograms from an excitation propagation simulation in the Extracellular, Membrane, Intracellular (EMI) model, which represents these three domains explicitly in the mesh. We studied the effects of the microstructural excitation dynamics on electrogram genesis and morphology. We found that electrograms are sensitive to the myocyte alignment and connectivity, which translates into micro-fractionations in the electrograms.
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.
Spectral deferred correction methods for solving stiff ODEs are known to converge rapidly towards the collocation limit solution on equidistant grids, but show a much less favourable contraction on non-equidistant grids such as
Radau-IIa points. We interprete SDC methods as fixed point iterations for the collocation system and propose new DIRK-type sweeps for stiff problems based on purely linear algebraic considerations. Good convergence is recovered also
on non-equidistant grids. The properties of different variants are explored on a couple of numerical examples.
Spectral deferred correction methods for solving stiff ODEs are known to converge rapidly towards the collocation limit solution on equidistant grids, but show a much less favourable contraction on non-equidistant grids such as
Radau-IIa points. We interprete SDC methods as fixed point iterations for the collocation system and propose new DIRK-type sweeps for stiff problems based on purely linear algebraic considerations. Good convergence is recovered also
on non-equidistant grids. The properties of different variants are explored on a couple of numerical examples.
We consider Large Deformation Diffeomorphic Metric Mapping of general $m$-currents. After stating an optimization algorithm in the function space of admissable morph generating velocity fields, two innovative aspects in this framework are presented and numerically investigated: First, we spatially discretize the velocity field with conforming adaptive finite elements and discuss advantages of this new approach. Second, we directly compute the temporal evolution of discrete $m$-current attributes.
A primal-dual interior point method for optimal control problems with PDE constraints is considered. The algorithm is directly applied to the infinite dimensional problem. Existence and convergence of the central path are analyzed. Numerical results from an inexact continuation method applied to a model problem are shown.
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.
The growing discrepancy between CPU computing power and memory bandwidth drives more and more numerical algorithms into a bandwidth-
bound regime. One example is the overlapping Schwarz smoother, a highly effective building block for iterative multigrid solution of elliptic equations with higher order finite elements. Two options of reducing the required
memory bandwidth are sparsity exploiting storage layouts and representing matrix entries with reduced precision in floating point or fixed point
format. We investigate the impact of several options on storage demand and contraction rate, both analytically in the context of subspace correction methods and numerically at an example of solid mechanics. Both perspectives agree on the favourite scheme: fixed point representation of Cholesky factors in nested dissection storage.