Search

A new approach to solving eigenvalue optimization problems for large structured matrices is proposed and studied. The class of optimization problems considered is related to computing structured pseudospectra and their extremal points, and to structured matrix nearness problems such as computing the distance to instability or to singularity under structured perturbations. The perturbation structure can be a general linear structure. We focus on the practically important cases of large matrices with a given sparsity pattern and on perturbation matrices with given range and corange. It is known that analogous eigenvalue optimization for unstructured complex matrices favorably works with rank-1 matrices. The novelty of the present paper is that structured eigenvalue optimization can still be performed with rank-1 matrices, which yields a significant reduction of storage and in some cases of the computational cost. Optimizers are shown to be rank-1 matrices orthogonally projected onto the given structure. This is used in the numerical algorithms. The numerical approach comes in two different versions. If the rank-1 matrices projected onto the structure form a manifold and if the orthogonal projection onto the corresponding tangent spaces is known and computationally inexpensive, as is the case for matrices with given range and corange, then the method relies on a gradient system on this manifold. Otherwise, in particular for matrices with a given sparsity pattern, the method relies on the orthogonal projection of the free gradient onto the tangent space of the manifold of complex rank-1 matrices. The solution of this rank-1 system is then projected onto the structure. It is shown that there is a bijective correspondence between the stationary points of the gradient system on the structure space and of the rank-1 system. Near a local minimizer the rank-1 tangent projection is very close to the identity map, and so the computationally favorable rank-1 projected system behaves locally like the gradient system. Numerical experiments illustrate the two approaches for large matrices with a given sparsity pattern and for perturbation matrices with given range and corange. [ABSTRACT FROM AUTHOR]

In a recent paper, Rostami [SIAM J. Sci. Comput, 37 (2015), pp. S447-S471] has presented an interesting algorithm for the computation of the real pseudospectral abscissa and the real stability radius (aka the distance to instability) of a square matrix A ∈ ℝn,n in the spectral norm. The method is particularly well suited for large sparse matrices. The algorithm to compute the stability radius is based on the alternation of an iterative method in the rank-2 manifold of real matrices and a Lyapunov inverse iteration. The algorithm shows quadratic convergence in all experiments, but this peculiar property is only conjectured. In this paper, we provide a rigorous proof and propose a modification which replaces the Lyapunov inverse iteration and speeds up the method. Moreover, we interpret the algorithm to compute the real ε-pseudospectral abscissa as a nonstandard discretization of the ODE-based method given in Guglielmi and Lubich [SIAM J. Matrix Anal. Appl., 34 (2013), pp. 40-66]. Several numerical illustrations comparing the modified algorithm with that proposed by Rostami conclude the paper. [ABSTRACT FROM AUTHOR]

For 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 $$\varepsilon $$ -pseudospectrum for a given $$\varepsilon $$ by following the low-rank differential equations into a stationary point, and on the outer level we optimize for $$\varepsilon $$ . This permits us to give fast algorithms-exhibiting quadratic convergence-for solving the considered Hamiltonian matrix nearness problems. [ABSTRACT FROM AUTHOR]

We 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 e-pseudospectrum for a given e and on the outer level we optimize over e, 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. [ABSTRACT FROM AUTHOR]

The H∞ norm of a transfer matrix function for a control system is the reciprocal of the largest value of ε such that the associated ε-spectral value set is contained in the stability region for the dynamical system (the left half-plane in the continuous-time case and the unit disk in the discrete-time case). After deriving some fundamental properties of spectral value sets, particularly the intricate relationship between the singular vectors of the transfer matrix and the eigenvectors of the corresponding perturbed system matrix, we extend an algorithm recently introduced by Guglielmi and Overton [SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1166-1192] for approximating the maximal real part or modulus of points in a matrix pseudospectrum to spectral value sets, characterizing its fixed points. We then introduce a Newton-bisection method to approximate the H∞ norm, for which each step requires optimization of the real part or the modulus over an ε-spectral value set. Although the algorithm is guaranteed only to find lower bounds on the H∞ norm, it typically finds good approximations in cases where we can test this. It is much faster than the standard Boyd--Balakrishnan--Bruinsma--Steinbuch algorithm to compute the H∞ norm when the system matrices are large and sparse and the number of inputs and outputs is small. The main work required by the algorithm is the computation of the spectral abscissa or radius of a sequence of matrices that are rank-one perturbations of a sparse matrix. [ABSTRACT FROM AUTHOR]

We consider the real ε-pseudospectrum of a real square matrix, which is the set of eigenvalues of all real matrices that are ε-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 ε-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. [ABSTRACT FROM AUTHOR]

The ε-pseudospectral abscissa and radius of an n x n matrix are, respectively, the maximal real part and the maximal modulus of points in its ε-pseudospectrum, defined using the spectral norm. Existing techniques compute these quantities accurately, but the cost is multiple singular value decompositions and eigenvalue decompositions of order n, making them impractical when n is large. We present new algorithms based on computing only the spectral abscissa or radius of a sequence of matrices, generating a sequence of lower bounds for the pseudospectral abscissa or radius. We characterize fixed points of the iterations, and we discuss conditions under which the sequence of lower bounds converges to local maximizers of the real part or modulus over the pseudospectrum, proving a locally linear rate of convergence for ε sufficiently small. The convergence results depend on a perturbation theorem for the normalized eigenprojection of a matrix as well as a characterization of the group inverse (reduced resolvent) of a singular matrix defined by a rank-one perturbation. The total cost of the algorithms is typically only a constant times the cost of computing the spectral abscissa or radius, where the value of this constant usually increases with ε, and may be less than 10 in many practical cases of interest. [ABSTRACT FROM AUTHOR]

When studying the ε-pseudospectrum of a matrix, one is often interested in computing the extremal points having maximum real part or modulus. This is a crucial step, for example, when computing the distance to instability of a stable system. Using the property that the pseudospectrum is determined via perturbations by rank-l matrices, we derive differential equations on the manifold of normalized rank-1 matrices whose solutions tend to the critical rank-1 perturbations associated wit h the extremal points of (locally) maximum real part and modulus. This approach also allows us to track the boundary contour of the pseudospcctrum in a neighborhood of the extremal points. The technique we propose is related to an idea recently developed by Gugliehmi and Overton, who derived discrete dynamical systems instead of the continuous ones we present. The method turns out to be fast in comparison with those previously proposed in the literature and appears to be promising in dealing with large sparse problems. [ABSTRACT FROM AUTHOR]