1,721,011 research outputs found
Numerical periodic orbits of neutral delay differential equations
No full textThis paper deals with the long-time behaviour of numerical solutions of neutral delay differential equations that have stable hyperbolic periodic orbits.
It is shown that Runge-Kutta discretizations of such equations have attractive invariant closed curves which approximate the periodic orbit with the full order of the method, in spite of the lack of a finite-time smoothing
property of the flow
Low-rank dynamics for computing extremal points of real pseudospectra
No full textWe consider the real eps-pseudospectrum of a real square matrix, which is the set of eigenvalues of all real matrices that are eps-close to the given matrix, where closeness is measured in
either the 2-norm or the Frobenius norm. We characterize extremal points and compare the situation
with that for the complex eps-pseudospectrum. We present differential equations for rank-1 and rank-2 matrices for the computation of the real pseudospectral abscissa and radius. Discretizations of
the differential equations yield algorithms that are fast and well suited for sparse large matrices.
Based on these low-rank differential equations, we further obtain an algorithm for drawing boundary
sections of the real pseudospectrum with respect to both the 2-norm and the Frobenius norm
Erratum/Addendum: Differential Equations for Roaming Pseudospectra: Paths to Extremal Points and Boundary Tracking
No full text. We correct an error that incurred in our paper published in SIAM J. Numer. Anal.
49 (2011), pp. 1194–1209, and give new algorithms for tracking the boundary of the pseudospectrum which are suitable for large, sparse matrices
Computing extremal points of symplectic pseudospectra and solving symplectic matrix nearness problems.
No full textWe study differential equations that lead to extremal points in symplectic pseudospectra. In a two-level approach, where on the inner level we compute extremizers of the symplectic \eps-pseudospectrum for a given \eps and on the outer level we optimize over \eps,
this is used to solve symplectic matrix nearness problems such as the following:
For a symplectic matrix with eigenvalues of unit modulus, we aim to determine the nearest complex symplectic matrix such that some or all eigenvalues leave the complex unit circle. Conversely, for a symplectic matrix with all eigenvalues lying off the unit circle, we consider the problem of computing the nearest symplectic matrix that has an eigenvalue on the unit circle
Low rank ODEs for Hamiltonian matrix nearness problems
No full textFor a Hamiltonian matrix with purely imaginary
eigenvalues, we aim to determine the nearest
Hamiltonian matrix such that some or all eigenvalues leave the imaginary
axis.
Conversely, for a Hamiltonian matrix with all eigenvalues lying off
the imaginary axis, we look for a nearest Hamiltonian matrix that has
a pair of imaginary eigenvalues. The Hamiltonian matrices can be allowed to be complex or restricted to be real. Such Hamiltonian matrix nearness
problems are motivated by applications such as the analysis of passive
control systems. They
are closely related to the problem of determining extremal
points of Hamiltonian pseudospectra. We obtain a characterization of
optimal perturbations, which turn out to be of low rank and are
attractive stationary points of low-rank differential equations that
we derive. We use a two-level approach, where in the inner level we determine extremal points of the Hamiltonian \eps-pseudospectrum for a given \eps by following the low-rank differential equations into a stationary point, and on the outer level we optimize for~\eps. This permits us to give fast algorithms - exhibiting quadratic convergence - for solving the considered Hamiltonian matrix
nearness problems
Measuring the stability of spectral clustering
No full textAs an indicator of the stability of spectral clustering of an undirected weighted graph into k clusters, the kth spectral gap of the graph Laplacian is often considered. The kth spectral gap is characterized in this paper as an unstructured distance to ambiguity, namely as the minimal distance of the Laplacian to arbitrary symmetric matrices with vanishing kth spectral gap. As a conceptually more appropriate measure of stability, the structured distance to ambiguity of the k-clustering is introduced as the minimal distance of the Laplacian to Laplacians of graphs with the same vertices and edges but with weights that are perturbed such that the kth spectral gap vanishes. To compute a solution to this matrix nearness problem, a two-level iterative algorithm is proposed that uses a constrained gradient system of matrix differential equations in the inner iteration and a one-dimensional optimization of the perturbation size in the outer iteration. The structured and unstructured distances to ambiguity are compared on some example graphs. The numerical experiments show, in particular, that selecting the number k of clusters according to the criterion of maximal stability can lead to different results for the structured and unstructured stability indicators
Graph partitioning using matrix differential equations
No full textGiven a connected undirected weighted graph, we are concerned with problems related to partitioning the graph. First of all we look for the closest disconnected graph (the minimum cut problem), here with respect to the Euclidean norm. We are interested in the case of constrained minimum cut problems, where constraints include cardinality or membership requirements, which leads to NP-hard combinatorial optimization problems. These problems are restated as matrix nearness problems for the weight matrix of the graph. A key element in the solution of these matrix nearness problems is the use of a constrained gradient system of matrix differential equations
Constrained graph partitioning via matrix differential equations
No full textA novel algorithmic approach is presented for the problem of partitioning a connected undirected weighted graph under constraints such as cardinality or membership requirements or must-link and cannot-link constraints. Such constrained problems can be NP-hard combinatorial optimization problems. They are restated as matrix nearness problems for the weight matrix of the graph, where the objective is to minimize the distance between the given weight matrix and perturbed weight matrices for which a functional of an eigenvalue and eigenvector of the graph Laplacian takes its minimal value. A key element in the numerical solution of these matrix nearness problems is the use of a gradient system of matrix differential equations for the functional
- …
