Search

Various iterative eigenvalue solvers have been developed to compute parts of the spectrum for a large sparse matrix, including the power method, Krylov subspace methods, contour integral methods, and preconditioned solvers such as the so called LOBPCG method. All of these solvers rely on random matrices to determine, e.g., starting vectors that have, with high probability, a non-negligible overlap with the eigenvectors of interest. For this purpose, a safe and common choice are unstructured Gaussian random matrices. In this work, we investigate the use of random Khatri-Rao products in eigenvalue solvers. On the one hand, we establish a novel subspace embedding property that provides theoretical justification for the use of such structured random matrices. On the other hand, we highlight the potential algorithmic benefits when solving eigenvalue problems with Kronecker product structure, as they arise frequently from the discretization of eigenvalue problems for differential operators on tensor product domains. In particular, we consider the use of random Khatri-Rao products within a contour integral method and LOBPCG. Numerical experiments indicate that the gains for the contour integral method strongly depend on the ability to efficiently and accurately solve (shifted) matrix equations with low-rank right-hand side. The flexibility of LOBPCG to directly employ preconditioners makes it easier to benefit from Khatri-Rao product structure, at the expense of having less theoretical justification.

In this paper we consider a constrained parabolic optimal control problem. The cost functional is quadratic and it combines the distance of the trajectory of the system from the desired evolution profile together with the cost of a control. The constraint is given by a term measuring the distance between the final state and the desired state towards which the solution should be steered. The control enters the system through the initial condition. We present a geometric analysis of this problem and provide a closed-form expression for the solution. This approach allows us to present the sensitivity analysis of this problem based on the resolvent estimates for the generator of the system. The numerical implementation is performed by exploring efficient rational Krylov approximation techniques that allow us to approximate a complex function of an operator by a series of linear problems. Our method does not depend on the actual choice of discretization. The main approximation task is to construct an efficient rational approximation of a generalized exponential function. It is well known that this class of functions allows exponentially convergent rational approximations, which, combined with the sensitivity analysis of the closed form solution, allows us to present a robust numerical method. Several case studies are presented to illustrate our results., Comment: 25 pages, 7 figures

We present a perturbed subspace iteration algorithm to approximate the lowermost eigenvalue cluster of an elliptic eigenvalue problem. As a prototype, we consider the Laplace eigenvalue problem posed in a polygonal domain. The algorithm is motivated by the analysis of inexact (perturbed) inverse iteration algorithms in numerical linear algebra. We couple the perturbed inverse iteration approach with mesh refinement strategy based on residual estimators. We demonstrate our approach on model problems in two and three dimensions., Comment: 30 pages, 15 figures

We propose an a posteriori error estimator for high-order $p$- or $hp$-finite element discretizations of selfadjoint linear elliptic eigenvalue problems that is appropriate for estimating the error in the approximation of an eigenvalue cluster and the corresponding invariant subspace. The estimator is based on the computation of approximate error functions in a space that complements the one in which the approximate eigenvectors were computed. These error functions are used to construct estimates of collective measures of error, such as the Hausdorff distance between the true and approximate clusters of eigenvalues, and the subspace gap between the corresponding true and approximate invariant subspaces. Numerical experiments demonstrate the practical effectivity of the approach.

We consider computing eigenspaces of an elliptic self-adjoint operator depending on a countable number of parameters in an affine fashion. The eigenspaces of interest are assumed to be isolated in the sense that the corresponding eigenvalues are separated from the rest of the spectrum for all values of the parameters. We show that such eigenspaces can in fact be extended to complex-analytic functions of the parameters and quantify this analytic dependence in way that leads to convergence of sparse polynomial approximations. A stochastic collocation method on an anisoptropic sparse grid in the parameter domain is proposed for computing a basis for the eigenspace of interest. The convergence of this method is verified in a series of numerical examples based on the eigenvalue problem of a stochastic diffusion operator.

A filtered subspace iteration for computing a cluster of eigenvalues and its accompanying eigenspace, known as "FEAST", has gained considerable attention in recent years. This work studies issues that arise when FEAST is applied to compute part of the spectrum of an unbounded partial differential operator. Specifically, when the resolvent of the partial differential operator is approximated by the discontinuous Petrov Galerkin (DPG) method, it is shown that there is no spectral pollution. The theory also provides bounds on the discretization errors in the spectral approximations. Numerical experiments for simple operators illustrate the theory and also indicate the value of the algorithm beyond the confines of the theoretical assumptions. The utility of the algorithm is illustrated by applying it to compute guided transverse core modes of a realistic optical fiber.

A new model description for the numerical simulation of elastic stents is proposed. Based on the new formulation an inf-sup inequality for the finite element discretization is proved and the proof of the inf-sup inequality for the continuous problem is simplified. The new formulation also leads to faster simulation times despite an increased number of variables. The techniques also simplify the analysis and numerical solution of the evolution problem describing the movement of the stent under external forces. The results are illustrated via numerical examples.

We obtain sufficient conditions that ensure block diagonalization (by a direct rotation) of sign-indefinite symmetric sesquilinear forms as well as the associated operators that are semi-bounded neither from below nor from above. In the semi-bounded case, we refine the obtained results and, as an example, revisit the block Stokes Operator from fluid dynamics., Comment: 21 pages

We consider filtered subspace iteration for approximating a cluster of eigenvalues (and its associated eigenspace) of a (possibly unbounded) selfadjoint operator in a Hilbert space. The algorithm is motivated by a quadrature approximation of an operator-valued contour integral of the resolvent. Resolvents on infinite dimensional spaces are discretized in computable finite-dimensional spaces before the algorithm is applied. This study focuses on how such discretizations result in errors in the eigenspace approximations computed by the algorithm. The computed eigenspace is then used to obtain approximations of the eigenvalue cluster. Bounds for the Hausdorff distance between the computed and exact eigenvalue clusters are obtained in terms of the discretization parameters within an abstract framework. A realization of the proposed approach for a model second-order elliptic operator using a standard finite element discretization of the resolvent is described. Some numerical experiments are conducted to gauge the sharpness of the theoretical estimates.

We show that the generalized Reynolds number (in fluid dynamics) introduced by Ladyzhenskaya is closely related to the rotation of the positive spectral subspace of the Stokes block-operator in the underlying Hilbert space. We also explicitly evaluate the bottom of the negative spectrum of the Stokes operator and prove a sharp inequality relating the distance from the bottom of its spectrum to the origin and the length of the first positive gap., Comment: 19 pages, 2 figures

In this paper we formulate and analyze the mixed formulation of the one-dimensional equilibrium model of elastic stents. The model is based on the curved rod model for the inextensible and ushearable struts and is formulated in the weak form in \v{C}ani\'{c} and Tamba\v{c}a, 2012. It is given by a system of ordinary differential equations at the graph structure. In order to numerically treat the model using finite element method the mixed formulation is plead for. We obtain equivalence of the weak and the mixed formulation by proving the Babuska--Brezzi condition for the stent structure.

We present reliable a-posteriori error estimates for $hp$-adaptive finite element approximations of eigenvalue/eigenvector problems. Starting from our earlier work on $h$ adaptive finite element approximations we show a way to obtain reliable and efficient a-posteriori estimates in the $hp$-setting. At the core of our analysis is the reduction of the problem on the analysis of the associated boundary value problem. We start from the analysis of Wohlmuth and Melenk and combine this with our a-posteriori estimation framework to obtain eigenvalue/eigenvector approximation bounds., Comment: submitted

We revisit the relative perturbation theory for invariant subspaces of positive definite matrix pairs. As a prototype model problem for our results we consider parameter dependent families of eigenvalue problems. We show that new estimates are a natural way to obtain sharp --- as functions of the parameter indexing the family of matrix pairs --- estimates for the rotation of spectral subspaces., Comment: submitted for a review

A version of the Davis-Kahan Tan $2\Theta$ theorem [SIAM J. Numer. Anal. \textbf{7} (1970), 1 -- 46] for not necessarily semibounded linear operators defined by quadratic forms is proven. This theorem generalizes a recent result by Motovilov and Selin [Integr. Equat. Oper. Theory \textbf{56} (2006), 511 -- 542].

The first and second representation theorems for sign-indefinite, not necessarily semi-bounded quadratic forms are revisited. New straightforward proofs of these theorems are given. A number of necessary and sufficient conditions ensuring the second representation theorem to hold is proved. A new simple and explicit example of a self-adjoint operator for which the second representation theorem does not hold is also provided., Comment: This work is supported in part by the Deutsche Forschungsgemeinschaft

We prove optimal convergence estimates for eigenvalues and eigenvectors of a class of singular/stiff perturbed problems. Our profs are constructive in nature and use (elementary) techniques which are of current interest in computational Linear Algebra to obtain estimates even for eigenvalues which are in gaps of the essential spectrum. Further, we also identify a class of "regular" stiff perturbations with (provably) good asymptotic properties. The Arch Model from the theory of elasticity is presented as a prototype for this class of perturbations. We also show that we are able to study model problems which do not satisfy this regularity assumption by presenting a study of a Schroedinger operator with singular obstacle potential., Comment: The paper is in review since February 2008

We give both lower and upper estimates for eigenvalues of unbounded positive definite operators in an arbitrary Hilbert space. We show scaling robust relative eigenvalue estimates for these operators in analogy to such estimates of current interest in Numerical Linear Algebra. Only simple matrix theoretic tools like Schur complements have been used. As prototypes for the strength of our method we discuss a singularly perturbed Schroedinger operator and study convergence estimates for finite element approximations. The estimates can be viewed as a natural quadratic form version of the celebrated Temple--Kato inequality., Comment: submitted to SIAM Journal on Numerical Analysis (a major revision of the paper)

We use a ``weakly formulated'' Sylvester equation $$A^{1/2}TM^{-1/2}-A^{-1/2}TM^{1/2}=F$$ to obtain new bounds for the rotation of spectral subspaces of a nonnegative selfadjoint operator in a Hilbert space. Our bound extends the known results of Davis and Kahan. Another application is a bound for the square root of a positive selfadjoint operator which extends the known rule: ``The relative error in the square root is bounded by the one half of the relative error in the radicand''. Both bounds are illustrated on differential operators which are defined via quadratic forms., Comment: 26 pages, submitted to Integral Equations and Operator Theory

In this article we further develop a perturbation approach to the Rayleigh--Ritz approximations from our earlier work. We both sharpen the estimates and extend the applicability of the theory to nonnegative definite operators . The perturbation argument enables us to solve two problems in one go: We determine which part of the spectrum of the operator is being approximated by the Ritz values and compute the approximation estimates. We also present a Temple--Kato like inequality which --unlike the original Temple--Kato inequality-- applies to any test vectors from the quadratic form domain of the operator., Comment: 28 pages and 1 figure