Refine
Year of publication
Language
- English (97)
Keywords
- optimal control (11)
- differential-algebraic equation (4)
- finite elements (4)
- metastability (4)
- trajectory storage (4)
- Lyapunov exponent (3)
- Sacker-Sell spectrum (3)
- exponential dichotomy (3)
- geodesic finite elements (3)
- rare events (3)
We propose a generalization of the Structured Doubling Algorithm (SDA) to compute invariant subspaces
of structured matrix pencils
that arise in the context of solving linear quadratic optimal control problems.
The new algorithm is
designed to attain better accuracy when the classical Riccati equation approach for the solution of the optimal control problem is not well suited because
the stable and unstable invariant subspaces are not well separated (due to eigenvalues near or on the imaginary
axis) or in the case when the Riccati solution does not exist at all. We analyze the convergence
of the method and compare the new method with the classical SDA algorithm as well as some recent structured QR-methods.
This paper presents concepts and implementation of the finite element toolbox Kaskade 7, a flexible C++ code for solving elliptic and parabolic PDE systems. Issues such as problem formulation, assembly and adaptivity are discussed at the example of optimal control problems. Trajectory compression for parabolic optimization problems is considered as a case study.
Deflated and augmented Krylov subspace methods: Basic Facts and a Breakdown-free deflated MINRES
(2011)
In this paper we consider deflation and augmentation techniques for accelerating
the convergence of Krylov subspace methods for the solution of nonsingular linear
algebraic systems. The two techniques are conceptually different from
preconditioning. Deflation "removes" certain parts from the operator, while
augmentation adds a subspace to the Krylov subspace. Both approaches have been
used in a variety of methods and settings. For Krylov subspace methods that
satisfy a (Petrov-) Galerkin condition we show that augmentation can in general
be achieved implicitly by projecting the residuals appropriately and correcting
the approximate solutions in a final step. In this context, we analyze known
methods to deflate CG, GMRes and MinRes. Our analysis reveals that the recently
proposed RMinRes method can break down. We show how such breakdowns can be
avoided by choosing a special initial guess, and we derive a breakdown-free
deflated MinRes method. In numerical experiments we study the properties of
different variants of MinRes analyzed in this paper.
One of the most challenging problems in dynamic concurrent multiscale
simulations is the reflectionless transfer of physical quantities between the
different scales. In particular, when coupling molecular dynamics and finite
element discretizations in solid body mechanics, often spurious wave reflections
are introduced by the applied coupling technique. The reflected waves are
typically of high frequency and are arguably of little importance in the domain
where the finite element discretization drives the simulation.
In this work, we provide an analysis of this phenomenon.
Based on the gained
insight, we derive a new coupling approach, which neatly separates high and low
frequency waves. Whereas low frequency waves are permitted to
bridge the scales, high frequency waves can be removed by applying damping techniques without affecting the coupled share of the solution. As a consequence, our new method almost completely eliminates unphysical wave reflections and deals in a consistent way with waves of arbitrary frequencies. The separation of
wavelengths is achieved by employing a discrete $L^2$-projection, which acts as a
low pass filter. Our coupling constraints enforce matching in the range of this projection. With respect to the numerical realization this approach
has the advantage of a small number of constraints, which is computationally
efficient. Numerical results in one and two dimensions confirm our theoretical
findings and illustrate the performance of our new weak coupling approach.
We investigate optimal elliptic
regularity (within the scale of Sobolev spaces) of anisotropic
div--grad operators in three dimensions at a multi-material vertex on
the Neumann boundary part of a polyhedral spatial domain. The
gradient of a solution to the corresponding elliptic PDE (in a
neighbourhood of the vertex) is integrable to an index greater than
three.
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 the mechanical coupling of a geometrically exact Cosserat rod to a linear elastic continuum. The coupling conditions are formulated in the nonlinear rod configuration space. We describe a Dirichlet--Neumann algorithm for the coupled system, and use it to simulate the static stresses in a human knee joint, where the Cosserat rods are models for the ligaments.
In optimal control problems with nonlinear time-dependent 3D PDEs, full 4D discretizations are usually prohibitive due to the storage requirement. For this reason gradient and Newton type methods working on the reduced functional are often employed. The computation of the reduced gradient requires one solve of the state equation forward in time, and one backward solve of the adjoint equation. The state enters into the adjoint equation, again requiring the storage of a full 4D data set. We propose a lossy compression algorithm using an inexact but cheap predictor for the state data, with additional entropy coding of prediction errors. As the data is used inside a discretized, iterative algorithm, lossy compression
maintaining a certain error bound turns out to be sufficient.
We introduce geodesic finite elements as a conforming way to discretize partial differential equations for functions $v : \Omega \to M$, where $\Omega$ is an open subset of $\R^d$ and $M$ is a Riemannian manifold. These geodesic finite elements naturally generalize standard first-order
finite elements for Euclidean spaces. They also generalize the geodesic finite elements proposed for $d=1$ by the author. Our formulation is equivariant under isometries of $M$, and hence preserves objectivity of continuous problem formulations. We concentrate on partial differential equations that can be formulated as minimization problems. Discretization leads to algebraic minimization problems on product manifolds $M^n$. These can be solved efficiently
using a Riemannian trust-region method. We propose a monotone multigrid method to solve the constrained inner problems with linear multigrid speed. As an example we numerically compute harmonic maps from a domain in $\R^3$
to $S^2$.
Logical modeling of biological regulatory networks gives rise to a representation of the system's dynamics as a so-called state transition graph. Analysis of such a graph in its entirety allows for a comprehensive understanding of the functionalities and behavior of the modeled system. However, the size of the vertex set of the graph is exponential in the number of the network components making analysis costly, motivating development of reduction methods. In this paper, we present results allowing for a complete description of an asynchronous state transition graph of a Thomas network solely based on the analysis of the subgraph induced by certain extremal states. Utilizing this notion, we compare the behavior of a simple multi-valued network and a corresponding Boolean network and analyze the conservation of dynamical properties between them. Understanding the relation between such coarser and finer models is a necessary step towards meaningful network reduction as well as model refinement methods.
Mathematical modeling often helps to provide a systems perspective on gene regulatory networks. In particular, qualitative approaches are useful when detailed kinetic information is lacking. Multiple methods have been developed that implement qualitative information in different ways, e.g., in purely discrete or hybrid discrete/continuous models. In this paper, we compare the discrete asynchronous logical modeling formalism for gene regulatory networks due to R. Thomas with piecewise affine differential equation models.
We provide a local characterization of the qualitative dynamics of a piecewise affine differential equation model using the discrete dynamics of a corresponding Thomas model. Based on this result, we investigate the consistency of higher-level dynamical properties such as attractor characteristics and reachability. We show that although the two approaches are based on equivalent information, the resulting qualitative dynamics are different. In particular, the dynamics of the piecewise affine differential equation model is not a simple refinement of the dynamics of the Thomas model.
The authors propose a recycling MINRES scheme for a solution of subsequent self-adjoint linear systems as appearing, for example, in the Newton process for solving nonlinear equations. Ritz vectors are automatically extracted from one MINRES run and then used for self-adjoint deflation in the next. The method is designed to work with a preconditioner and arbitrary inner products. Numerical experiments with nonlinear Schrödinger equations indicate a substantial decrease in computation time when recycling is used.
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 pole condition approach for deriving transparent boundary conditions is extended to the time-dependent, two-dimensional case. Non-physical modes of the solution are identified by the position of poles of the solution's spatial Laplace transform in the complex plane. By requiring the Laplace transform to be analytic on some
problem dependent complex half-plane, these modes can be
suppressed. The resulting algorithm computes a finite number of coefficients of a series expansion of the Laplace transform, thereby providing an approximation to the exact boundary condition. The resulting error decays super-algebraically with the number of coefficients, so relatively few additional degrees of freedom are
sufficient to reduce the error to the level of the discretization error in the interior of the computational domain. The approach shows good results for the Schroedinger and the drift-diffusion equation
but, in contrast to the one-dimensional case, exhibits instabilities for the wave and Klein-Gordon equation. Numerical examples are shown that demonstrate the good performance in the former and the instabilities in the latter case.
Flux variability analysis (FVA) is an important tool to further analyze the results obtained by flux balance analysis (FBA) on genome-scale metabolic networks. Standard FVA may predict unbounded fluxes through some reactions in the network even if the nutrient uptake rate is bounded. These fluxes violate the second law of thermodynamics. They may be eliminated by extending flux variability analysis with thermodynamic constraints.
We present a new algorithm for efficient flux variability (and flux balance) analysis with thermodynamic constraints, suitable for analyzing genome-scale metabolic networks. We first show that flux balance analysis with thermodynamic constraints is NP-hard. Then we derive a theoretical tractability result, which can be applied to metabolic networks in practice. We use this result to develop a new constraint programming algorithm Fast-tFVA for fast flux variability analysis with thermodynamic constraints (tFVA). Computational comparisons with previous methods demonstrate the efficiency of the new method. For tFVA, a speed-up of factor 30-300 is achieved.
In an analysis of genome-scale metabolic networks in the BioModels database, we found that in 485 out of 716 networks additional irreversible or fixed reactions could be detected.
This article describes Fortran 77 subroutines for computing eigenvalues and invariant subspaces
of Hamiltonian and skew-Hamiltonian matrices. The implemented algorithms are based on orthogonal
symplectic decompositions, implying numerical backward stability as well as symmetry
preservation for the computed eigenvalues. These algorithms are supplemented with balancing and
block algorithms, which can lead to considerable accuracy and performance improvements. As a
by-product, an efficient implementation for computing symplectic QR decompositions is provided.
We demonstrate the usefulness of the subroutines for several, practically relevant examples.
Stewart's recently introduced Krylov-Schur algorithm
is a modification of the implicitly restarted Arnoldi algorithm which
employs reordered Schur decompositions to perform restarts and de-
ations in a numerically reliable manner. This paper describes a variant
of the Krylov-Schur algorithm suitable for addressing eigenvalue
problems associated with products of large and sparse matrices. It
performs restarts and de
ations via reordered periodic Schur decompositions
and, by taking the product structure into account, it is
capable to achieve qualitatively better approximations to the eigenvalues
of small magnitude.
The role of larger bulges in the QR algorithm is controversial. Large bulges are infamous
for having a strong, negative influence on the convergence of the implicit shifted QR algorithm.
This paper provides a new explanation of this shift blurring effect by connecting the computation of
the first column of the shift polynomial to the notoriously ill-conditioned pole placement problem.
To avoid shift blurring, modern variants of the QR algorithm employ chains of tightly coupled tiny
bulges instead of one large bulge. It turns out that larger bulges still play a positive role in these
variants; a slight increase of the bulge sizes often results in considerable performance improvements.
We investigate the condition number for a complex eigenvalue of a real matrix under
real perturbations. Based on an explicit formula, it is shown that this number is never
smaller than 1/
p
2 times the corresponding condition number with respect to complex
perturbations. This result can be generalized to the condition number of an arbitrary
complex-valued function under real perturbations. This extends to related condition
numbers.