Search

In this paper, we propose a two-level block preconditioned Jacobi--Davidson (BPJD) method for efficiently solving discrete eigenvalue problems resulting from finite element approximations of 2mth (m= 1, 2) order symmetric elliptic eigenvalue problems. Our method works effectively to compute the first several eigenpairs, including both multiple and clustered eigenvalues with corresponding eigenfunctions, particularly. The method is highly parallelizable by constructing a new and efficient preconditioner using an overlapping domain decomposition (DD). It only requires computing a couple of small scale parallel subproblems and a quite small scale eigenvalue problem per iteration. Our theoretical analysis reveals that the convergence rate of the method is bounded by c(H)(1 C\delta 2m 1 H2m 1)2, where H is the diameter of subdomains and\delta is the overlapping size among subdomains. The constant C is independent of the mesh size h and the internal gaps among the target eigenvalues, demonstrating that our method is optimal and cluster robust. Meanwhile, the H-dependent constant c(H) decreases monotonically to 1, as H\rightarrow 0, which means that more subdomains lead to the better convergence rate. Numerical results supporting our theory are given. [ABSTRACT FROM AUTHOR]

This paper is concerned with the principal spectral theory of time-periodic cooperative systems with nonlocal dispersal and Neumann boundary condition. First we present a sufficient condition for the existence of principal eigenvalues by using the theory of resolvent positive operators with their perturbations. Then we establish the monotonicity of principal eigenvalues with respect to the frequency and investigate the limiting properties of principal eigenvalues as the frequency tends to zero or infinity. We also study the effects of dispersal rates and dispersal ranges on the principal eigenvalues, and the difficulty is that principal eigenvalues of time-periodic cooperative systems with Neumann boundary conditions are not monotone with respect to the domain. Finally, we apply our theory to a man-environment-man epidemic model and consider the impacts of dispersal rates, frequency, and dispersal ranges on the basic reproduction number and positive time-periodic solutions. [ABSTRACT FROM AUTHOR]

In this paper, a novel mixed spectral-Galerkin method is proposed and studied for a Maxwell transmission eigenvalue problem in a spherical domain. The method utilizes vector spherical harmonics to achieve dimension reduction. By introducing an auxiliary vector function, the original problem is rewritten as an equivalent fourth-order coupled linear eigensystem, which is further decomposed into a sequence of one-dimensional fourth-order decoupled transverse-electric (TE) and transverse-magnetic (TM) modes. Based on compact embedding theory and the spectral approximation property of compact operators, error estimates for both eigenvalue and eigenfunction approximations are established for the TE mode. For the TM mode, an efficient essential polar condition and a high-order polynomial approximation method are designed to cope with the singularity and complexity caused by the coupled boundary conditions. Numerical experiments are presented to demonstrate the efficiency and robustness of our algorithm. [ABSTRACT FROM AUTHOR]

This paper develops a class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized dimension reduction ("sketching") to accelerate standard subspace projection methods, such as GMRES and Rayleigh-Ritz. This modification makes it possible to incorporate nontraditional bases for the approximation subspace that are easier to construct. When the basis is numerically full rank, the new algorithms have accuracy similar to classic methods but run faster and may use less storage. For model problems, numerical experiments show large advantages over the optimized MATLAB routines, including a 70x speedup over gmres and a 10x speedup over eigs. [ABSTRACT FROM AUTHOR]

In this paper we study the (nonlocal) torsional rigidity in the ambient space of random walk spaces. We get the relation of the (nonlocal) torsional rigidity of a set Ω with the spectral m-heat content of Ω, which gives rise to a complete description of the nonlocal torsional rigidity of Ω by using uniquely probability terms involving the set Ω, and we recover the first eigenvalue of the nonlocal Laplacian with homogeneous Dirichlet boundary conditions by a limit formula using these probability terms. For the random walk in Rλγ associated with a nonsingular kernel, we get a nonlocal version of the Saint-Venant inequality, and, under rescaling, we recover the classical Saint-Venant inequality. We also study the nonlocal p-torsional rigidity and its relation with the nonlocal Cheeger constants, and we prove a nonlocal version of the P61ya-Makai-type inequalities. We relate the torsional rigidity given here for weighted graphs with the torsional rigidity on metric graphs. [ABSTRACT FROM AUTHOR]

This paper is concerned with the stability of the ball for a class of isoperimetric problems under a convexity constraint. Considering the problem of minimizing P + εR among convex subsets of R of fixed volume, where P is the perimeter functional, R is a perturbative term, and ε > 0 is a small parameter, the stability of the ball for this perturbed isoperimetric problem means that the ball is the unique (local, up to translation) minimizer for any £ sufficiently small. We investigate independently two specific cases where Ω H> R(Ω) is an energy arising from PDE theory, namely, the capacity and the first Dirichlet eigenvalue of a domain Ω C Rλ. While in both cases stability fails among all shapes, in the first case we prove the (nonshaιp>) stability of the ball among convex shapes, by building an appropriate competitor for the capacity of a perturbation of the ball. In the second case we prove the sharp stability of the ball among convex shapes by providing the optimal range of ε such that stability holds, relying on the selection principle technique and a regularity theory under convexity constraint. [ABSTRACT FROM AUTHOR]

Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest A in a larger unitary transformation U that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of A, which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB. [ABSTRACT FROM AUTHOR]

This paper concerns a class of monotone eigenvalue problems with eigenvector nonlinearities (mNEPv). The mNEPv is encountered in applications such as the computation of joint numerical radius of matrices, best rank-one approximation of third-order partial-symmetric tensors, and distance to singularity for dissipative Hamiltonian differential-algebraic equations. We first present a variational characterization of the mNEPv. Based on the variational characterization, we provide a geometric interpretation of the self-consistent field (SCF) iterations for solving the mNEPv, prove the global convergence of the SCF, and devise an accelerated SCF. Numerical examples demonstrate theoretical properties and computational efficiency of the SCF and its acceleration. [ABSTRACT FROM AUTHOR]

The elastic potential is a valuable modeling tool for many applications, including medical imaging. One reason for this is that the energy and its Gateaux derivative, the elastic operator, have strong coupling properties. Although these properties are desirable from a modeling perspective, they are not advantageous from a computational or operator decomposition perspective. In this paper, we show that the elastic operator can be spectrally decomposed despite its coupling property when equipped with sliding boundary conditions. Moreover, we present a discretization that is fully compatible with this spectral decomposition. In particular, for image registration problems, this decomposition opens new possibilities for multispectral solution techniques and fine-tuned operator-based regularization. [ABSTRACT FROM AUTHOR]

The cross-product matrix-based CJ-FEAST SVDsolver proposed previously by the authors is shown to compute the left singular vector possibly much less accurately than the right singular vector and may be numerically backward unstable when a desired singular value is small. In this paper, an alternative augmented matrix-based CJ-FEAST SVDsolver is proposed to compute the singular triplets of a large matrix A with the singular values in an interval [a, b] contained in the singular spectrum. The new CJ-FEAST SVDsolver is a subspace iteration applied to an approximate spectral projector of the augmented matrix [0, AT; A, 0] associated with the eigenvalues in [a, b], and it constructs approximate left and right singular subspaces independently, onto which A is projected to obtain the Ritz approximations to the desired singular triplets. Compact estimates are given for the accuracy of the approximate spectral projector constructed by the Chebyshev--Jackson series expansion in terms of series degree, and a number of convergence results are established. The new solver is proved to be always numerically backward stable. A convergence comparison of the cross-product-based and augmented matrix-based CJ-FEAST SVDsolvers is made, and a generalpurpose choice strategy between the two solvers is proposed for the robustness and overall efficiency. Numerical experiments confirm all the results and meanwhile demonstrate that the proposed solver is more robust and substantially more efficient than the corresponding contour integral-based versions that exploit the trapezoidal rule and the Gauss--Legendre quadrature to construct an approximate spectral projector. [ABSTRACT FROM AUTHOR]

In this paper, we prove a logarithmic conjugation theorem on finitely connected tori. The theorem states that a harmonic function can be written as the real part of a function whose derivative is analytic and a finite sum of terms involving the logarithm of the modulus of a modified Weierstrass sigma function. We implement the method using arbitrary precision and use the result to find approximate solutions to the Laplace problem and the Steklov eigenvalue problem. Using a posteriori estimation, we show that the solution of the Laplace problem on a torus with a few holes has error less than 10-100 using a few hundred degrees of freedom and the Steklov eigenvalues have similar error. [ABSTRACT FROM AUTHOR]

This paper studies system theoretic properties of the class of difference inclusions of convex processes. We will develop a framework considering eigenvalues and eigenvectors, weakly and strongly invariant cones, and a decomposition of convex processes. This framework will lead to characterizations of reachability, stabilizability, and (null-)controllability for nonstrict convex processes in terms of spectral properties. These characterizations generalize all previously known results regarding, for instance, linear processes and specific classes of nonstrict convex processes. [ABSTRACT FROM AUTHOR]

In this paper, we consider an inverse interaction scattering problem of recovering an interface between the fluid and piezoelectric solid from acoustic measurements. First, the wellposedness of the interaction model is shown in associated function spaces by the variational method. Then new uniqueness results are proved for the inverse problem by taking far-field data at one fixed frequency, based on a uniform a priori estimate of the solutions of the interaction model. With these results, the factorization method is then justified to reconstruct the shape and location of the interface between the fluid and piezoelectric solid. Finally, we investigate an associated interior transmission eigenvalue problem, and show that the set of interior transmission eigenvalues is at most discrete and with no finite accumulation point under a natural assumption on physical coefficients. [ABSTRACT FROM AUTHOR]

For a regular polyhedron (or polygon) centered at the origin, the coordinates of the vertices are eigenvectors of the graph Laplacian for the skeleton of that polyhedron (or polygon) associated with the first nontrivial eigenvalue. In this paper, we generalize this relationship. For a given graph, we study the eigenvalue optimization problem of maximizing the first nontrivial eigenvalue of the graph Laplacian over nonnegative edge weights. We show that the spectral realization of the graph using the eigenvectors corresponding to the solution of this problem, under certain assumptions, is a centered, unit-distance graph realization that has maximal total variance. This result gives a new method for generating unit-distance graph realizations and is based on convex duality. A drawback of this method is that the dimension of the realization is given by the multiplicity of the extremal eigenvalue, which is typically unknown prior to solving the eigenvalue optimization problem. Our results are illustrated with a number of examples. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to analyze a mixed method for linear elasticity eigenvalue problem, which approximates numerically the stress, displacement, and rotation, by piecewise (k+1), k and (k+1)-th degree polynomial functions (k=1), respectively. The numerical eigenfunction of stress is symmetric. By the discrete H1-stability of numerical displacement, we prove an O(hk+2) approximation to the L²-orthogonal projection of the eigenspace of exact displacement for the eigenvalue problem, with proper regularity assumption. Thus via postprocessing, we obtain a better approximation to the eigenspace of exact displacement for the eigenproblem than conventional methods. We also prove that numerical approximation to the eigenfunction of stress is locking free with respect to Poisson ratio. We introduce a hybridization to reduce the mixed method to a condensed eigenproblem and prove an O(h²) initial approximation (independent of the inverse of the elasticity operator) of the eigenvalue for the nonlinear eigenproblem by using the discrete H1-stability of numerical displacement, while only an O(h) approximation can be obtained if we use the traditional inf-sup condition. Finally, we report some numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, the eigenvalue embedding problem of the damped vibroacoustic system with no-spillover (EEP-VA) is considered, which is to update the original system to a new damped vibroacoustic system such that some eigenvalues are replaced by newly given or measured ones, while the remaining eigenvalues and associated eigenvectors are kept unchanged. We provide a spectral decomposition of the damped vibroacoustic system and further give a set of parametric solutions to the EEP-VA. Moreover, our method can also be extended to the case of the undamped vibroacoustic system. Exploiting the freedoms of the parametric matrices in the solution, the modifications on the coefficient matrices can be minimized. Numerical experiments illustrate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The eigenvalue decomposition (EVD) of (a batch of) Hermitian matrices of order two has a role in many numerical algorithms, of which the one-sided Jacobi method for the singular value decomposition (SVD) is the prime example. In this paper the batched EVD is vectorized with a vector-friendly data layout and the AVX-512 SIMD instructions of Intel CPUs, alongside other key components of a real and a complex OpenMP-parallel Jacobi-type SVD method, inspired by the sequential xGESVJ routines from LAPACK. These vectorized building blocks should be portable to other platforms that support similar vector operations. Unconditional numerical reproducibility is guaranteed for the batched EVD, sequential or threaded, and for the column transformations, which are, like the scaled dot-products, presently sequential but can be threaded if nested parallelism is desired. No avoidable overflow of the results can occur with the proposed EVD or the whole SVD. The measured accuracy of the proposed EVD often surpasses that of the xLAEV2 routines from LAPACK. While the batched EVD outperforms the matching sequence of xLAEV2 calls, speedup of the parallel SVD is modest but can be improved and is already beneficial with enough threads. Regardless of their number, the proposed SVD method gives identical results but of a somewhat lower accuracy than xGESVJ. [ABSTRACT FROM AUTHOR]

The spectral bundle method proposed by Helmberg and Rendl [SIAM J. Optim., 10 (2000), pp. 673-696] is well established for solving large-scale semidefinite programs (SDPs) thanks to its low per iteration computational complexity and strong practical performance. In this paper, we revisit this classic method showing that it achieves sublinear convergence rates in terms of both primal and dual SDPs under merely strong duality, complementing previous guarantees on primal-dual convergence. Moreover, we show that the method speeds up to linear convergence if (1) structurally the SDP admits strict complementarity and (2) algorithmically the bundle method captures the rank of the optimal solutions. Such complementary and low-rank structure is prevalent in many modern and classical applications. The linear convergence result is established via an eigenvalue approximation lemma which might be of independent interest. Numerically, we confirm our theoretical findings that the spectral bundle method, for modern and classical applications, speeds up under these conditions. Finally, we show that the spectral bundle method combined with a recent matrix sketching technique is able to solve an SDP with billions of decision variables in a matter of minutes. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of nonsmooth sum-of-ratios fractional optimization problems with block structure. This model class is ubiquitous and encompasses several important nonsmooth optimization problems in the literature. We first propose an inertial proximal block coordinate method for solving this class of problems by exploiting the underlying structure. The global convergence of our method is guaranteed under the Kurdyka-Łojasiewicz (KL) property and some mild assumptions. We then identify the explicit exponents of the KL property for three important structured fractional optimization problems. In particular, for the sparse generalized eigenvalue problem with either cardinality regularization or sparsity constraint, we show that the KL exponents are 1/2, and so the proposed method exhibits a linear convergence rate. Finally, we illustrate our theoretical results with both analytic and simulated numerical examples. [ABSTRACT FROM AUTHOR]

For the Helmholtz equation posed in the exterior of a Dirichlet obstacle, we prove that if there exists a family of quasimodes (as is the case when the exterior of the obstacle has stable trapped rays), then there exist near-zero eigenvalues of the standard variational formulation of the exterior Dirichlet problem (recall that this formulation involves truncating the exterior domain and applying the exterior Dirichlet-to-Neumann map on the truncation boundary). Our motivation for proving this result is that (a) the finite-element method for computing approximations to solutions of the Helmholtz equation is based on the standard variational formulation, and (b) the location of eigenvalues, and especially near-zero ones, plays a key role in understanding how iterative solvers such as the generalized minimum residual method (GMRES) behave when used to solve linear systems, in particular those arising from the finite-element method. The result proved in this paper is thus the first step towards rigorously understanding how GMRES behaves when applied to discretizations of high-frequency Helmholtz problems under strong trapping (the subject of the companion paper [P. Marchand et al., Adv. Comput. Math., to appear]). [ABSTRACT FROM AUTHOR]

This paper develops a new storage-optimal algorithm that provably solves almost all semidefinite programs (SDPs). This method is particularly effective for weakly constrained SDPs under appropriate regularity conditions. The key idea is to formulate an approximate complementarity principle: Given an approximate solution to the dual SDP, the primal SDP has an approximate solution whose range is contained in the eigenspace with small eigenvalues of the dual slack matrix. For weakly constrained SDPs, this eigenspace has very low dimension, so this observation significantly reduces the search space for the primal solution. This result suggests an algorithmic strategy that can be implemented with minimal storage: (1) solve the dual SDP approximately; (2) compress the primal SDP to the eigenspace with small eigenvalues of the dual slack matrix; (3) solve the compressed primal SDP. The paper also provides numerical experiments showing that this approach is successful for a range of interesting large-scale SDPs. [ABSTRACT FROM AUTHOR]

This paper describes a set of rational filtering algorithms to compute a few eigenvalues (and associated eigenvectors) of non-Hermitian matrix pencils. Our interest lies in computing eigenvalues located inside a given disk, and the proposed algorithms approximate these eigenvalues and associated eigenvectors by harmonic Rayleigh--Ritz projections on subspaces built by computing range spaces of rational matrix functions through randomized range finders. These rational matrix functions are designed so that directions associated with nonsought eigenvalues are dampened to (approximately) zero. Variants based on matrix partitionings are introduced to further reduce the overall complexity of the proposed framework. Compared with existing eigenvalue solvers based on rational matrix functions, the proposed technique requires no estimation of the number of eigenvalues located inside the disk. Several theoretical and practical issues are discussed, and the competitiveness of the proposed framework is demonstrated via numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, based on a domain decomposition method, we shall propose a two-level preconditioned Helmholtz subspace iterative (PHSI) method for solving algebraic eigenvalue problems resulting from edge element approximation of Maxwell eigenvalue problems. The two-level PHSI method may compute simple eigenpairs, multiple eigenpairs, and clustered eigenpairs. It is very efficient and robust for solving Maxwell eigenvalue problems since the method reduces solutions of fine eigenvalue problems to a series of solutions of parallel preconditioned systems and Helmholtz projected systems. After solving a small dimensional eigenvalue problem in a trial subspace, we finally get the total error reduction of the first several discrete eigenvalues as γ=c(H)ρ0(α,δ/H), where α is a positive parameter, δ is the overlapping size among subdomains, and H is the diameter of subdomains. The positive number ρ0(α,δ/H)(<1) is independent of the mesh size h and internal gaps among the first several Maxwell eigenvalues, i.e., the method is optimal corresponding to the degrees of freedom and cluster robust. The number ρ0(α,δ/H) increases with α increasing, and decreases with δH increasing. The H -dependent constant c(H) decreases monotonically to 1 as H→0, which means the more the number of subdomains, the better the convergence rate. Numerical results supporting our theory are given. [ABSTRACT FROM AUTHOR]

In this paper, we consider the Newton-Schur method in Hilbert space and obtain quadratic convergence. For the symmetric elliptic eigenvalue problem discretized by the standard finite element method and nonoverlapping domain decomposition method, we use the Steklov-Poincaré operator to reduce the eigenvalue problem on the domain Ω into the nonlinear eigenvalue subproblem on Γ, which is the union of subdomain boundaries. We prove that the convergence rate for the Newton-Schur method is ∈N ≤ C∈7#178;, where the constant C is independent of the fine mesh size h and coarse mesh size H, and ∈N and ∈ are errors after and before one iteration step, respectively. For one specific inner product on Γ, a sharper convergence rate is obtained, and we can prove that ∈N ≤ C H²(1 + ln(H/h))²∈². Numerical experiments confirm our theoretical analysis. [ABSTRACT FROM AUTHOR]

We study nonconvex homogeneous quadratically constrained quadratic optimization with m(∈ {1, 2}) constraints, denoted by (QQm). (QQ2) contains (QQ1), the trust region subproblem (TRS) and its generalization (GTRS), and the ellipsoid regularized total least squares problem as special cases. It is known that there is a necessary and sufficient optimality condition for the global minimizer of (QQ2). In this paper, we first show that any local minimizer of (QQ1) is globally optimal. Unlike its special case (TRS) with at most one local nonglobal minimizer, (QQ2) may have infinitely many local nonglobal minimizers. At any local nonglobal minimizer of (QQ2), both the linear independence constraint qualification and the strict complementary slackness condition hold, and the Hessian of the Lagrangian has exactly one negative eigenvalue. As the main contribution, we prove that the standard second-order sufficient optimality condition for any strict local nonglobal minimizer of (QQ2) remains necessary. It turns out that finding all local nonglobal minimizers of (GTRS) or proving the nonexistence can be done in polynomial time. More applications and the impossibility of extending our main result are discussed. [ABSTRACT FROM AUTHOR]

n the article "A Rational QZ Method" by D. Camps, K. Meerbergen, and R. Vande-bril [SIAM J. Matrix Anal. Appl., 40 (2019), pp. 943--972], we introduced rational QZ (RQZ) methods. Our theoretical examinations revealed that the convergence of the RQZ method is governed by rational subspace iteration, thereby generalizing the classical QZ method, whose convergence relieson polynomial subspace iteration. Moreover the RQZ method operates on a pencil more general than Hessenberg---upper triangular, namely, a Hessenberg pencil, which is a pencil consisting of two Hessenberg matrices. However, the RQZ method can only be made competitive to advanced QZ implementations by using crucial add-ons such as small bulge multi shift sweeps, aggressive early deflation, and optimal packing. In this paper we develop these techniques for the RQZ method.In the numerical experiments we compare the results with state-of-the-art routines for the generalized eigenvalue problem and show that the presented method is competitive in terms of speed and accuracy. [ABSTRACT FROM AUTHOR]

We obtain the generic complete eigenstructures of complex Hermitian n times n matrix pencils with rank at most r (with r leq n). To do this, we prove that the set of such pencils is the union of a finite number of bundle closures, where each bundle is the set of complex Hermitian n times n pencils with the same complete eigenstructure (up to the specific values of the distinct finite eigenvalues). We also obtain the explicit number of such bundles and their codimension. The cases r =n, corresponding to general Hermitian pencils, and r < n exhibit surprising differences, since for r < n the generic complete eigenstructures can contain only real eigenvalues, while for r = n they can contain real and nonreal eigenvalues. Moreover, we will see that the sign characteristic of the real eigenvalues plays a relevant role for determining the generic eigenstructures. [ABSTRACT FROM AUTHOR]

This paper introduces bootstrap multigrid methods for solving eigenvalue problems arising from the discretization of partial differential equations. Inspired by the full bootstrap algebraic multigrid setup algorithm that includes an AMG eigensolver, we illustrate how the algorithm can be simplified for the case of a discretized partial differential equation, thereby developing a bootstrap geometric multigrid (BMG) approach. We illustrate numerically the efficacy of the BMG method for (1) recovering eigenvalues having large multiplicity, (2) computing interior eigenvalues, and (3) approximating shifted indefinite eigenvalue problems. Numerical experiments are presented to illustrate the basic components and ideas behind the success of the overall bootstrap multigrid approach. For completeness, we present a simplified error analysis of a two-grid bootstrap algorithm for the Laplace-Beltrami eigenvalue problem. [ABSTRACT FROM AUTHOR]

This work is the second part of a previous paper which was devoted to scalar problems. Here we study the shape derivative of eigenvalue problems of elasticity theory for various kinds of boundary conditions, that is Dirichlet, Neumann, Robin, and Wentzell boundary conditions. We also study the case of composite materials, having in mind applications in the sensitivity analysis of mechanical devices manufactured by additive printing. The main idea, which rests on the computation of the derivative of a minimum with respect to a parameter, was successfully applied in the scalar case in the first part of this paper and is here extended to more interesting situations in the vectorial case (linear elasticity), with applications in additive manufacturing. These computations for eigenvalues in the elasticity problem for generalized boundary conditions and for composite elastic structures constitute the main novelty of this paper. The results obtained here also show the efficiency of this method for such calculations whereas the methods used previously even for classical clamped or transmission boundary conditions are more lengthy or are based on various simplifying assumptions, such as the simplicity of the eigenvalue or the existence of a shape derivative. [ABSTRACT FROM AUTHOR]

In this paper, we establish the discreteness of transmission eigenvalues for Maxwell's equations. More precisely, we show that the spectrum of the transmission eigenvalue problem is discrete if the electromagnetic parameters 𝝴, 𝝻, ꏁ, Ȗ in the equations characterizing the inhomogeneity and background are smooth in some neighborhood of the boundary and isotropic on the boundary, and satisfy the conditions 𝝴 = ꏁ, 𝝻 = Ȗ, and 𝝴 / Ȗ ҂ꏁ/Ȗ on the boundary. These are quite general assumptions on the coefficients, which are easy to check. To our knowledge, our paper is the first to establish discreteness of transmission eigenvalues for Maxwell's equations without assuming any restrictions on the sign combination of the contrasts 𝝴 - ꏁ and 𝝻 - Ȗ near the boundary and allowing for all the electromagnetic parameters to be inhomogeneous and anisotropic, except for on the boundary where they are isotropic but not necessarily constant as is often assumed in the literature. [ABSTRACT FROM AUTHOR]

In this paper we introduce the notion of eventually periodic switching signal. We prove that if a family of linear vector fields satisfies a mild finite time controllability condition, and for each initial state there exists a time-dependent switching signal which asymptotically drives the system to the origin (possibly allowing different signals for different initial states), then the same goal can be achieved by means of an eventually periodic switching signal. This enables us to considerably reduce the dependence of the control law on the initial state. In this sense, the problem addressed in this paper can be reviewed as a switched system theory version of the classical problem of investigating whether, or to what extent, a nonlinear asymptotically controllable system admits stabilizing feedback laws. [ABSTRACT FROM AUTHOR]

This paper proposes a parallel domain decomposition Rayleigh--Ritz projection scheme to compute a selected number of eigenvalues (and, optionally, associated eigenvectors) of large and sparse symmetric pencils. The projection subspace associated with interface variables is built by computing a few of the eigenvectors and associated leading derivatives of a zeroth-order approximation of the nonlinear matrix-valued interface operator. On the other hand, the projection subspace associated with interior variables is built independently in each subdomain by exploiting local eigenmodes and matrix resolvent approximations. The sought eigenpairs are then approximated by a Rayleigh--Ritz projection onto the subspace formed by the union of these two subspaces. Several theoretical and practical details are discussed, and upper bounds of the approximation errors are provided. Our numerical experiments demonstrate the efficiency of the proposed technique on sequential/distributed memory architectures as well as its competitiveness against schemes such as shift-and-invert Lanczos and automated multilevel substructuring combined with p-way vertex-based partitionings. [ABSTRACT FROM AUTHOR]

Traveling oscillating fronts (TOFs) are specific one-dimensional waves of the form U (x, t) = e-iωV (x ct) with a complex-valued profile V that decays at -∞ but approaches a nonzero limit at +∞. In particular, we consider TOFs which connect two stable homogeneous rest states and which occur generically in complex Ginzburg Landau equations of the type Ut = \alpha Uxx + G(| U| ²)U. In this paper we prove a theorem on the asymptotic stability of TOFs, where we allow the initial perturbation to be the sum of an exponentially localized part and a front-like part which approaches a small but nonzero limit at +∞. The underlying assumptions guarantee that the operator, obtained from linearizing about the TOF in a co-moving and co-rotating frame, has essential spectrum touching the imaginary axis in a quadratic fashion and that further isolated eigenvalues are bounded away from the imaginary axis. The basic idea of the proof is to consider the problem in an extended phase space which couples the wave dynamics on the real line to the ODE dynamics at +∞. Using slowly decaying exponential weights, the framework allows one to derive appropriate resolvent estimates, semigroup techniques, and Gronwall estimates. [ABSTRACT FROM AUTHOR]

This paper provides a provably quasi-optimal preconditioning strategy of the linear Schr\"odinger eigenvalue problem with periodic potentials for a possibly nonuniform spatial expansion of the domain. The quasi-optimality is achieved by having the iterative eigenvalue algorithms converge in a constant number of iterations for different domain sizes. In the analysis, we derive an analytic factorization of the spectrum and asymptotically describe it using concepts from the homogenization theory. This decomposition allows us to express the eigenpair as an easy-to-calculate cell problem solution combined with an asymptotically vanishing remainder. We then prove that the easy-to-calculate limit eigenvalue can be used in a shift-and-invert preconditioning strategy to bound the number of eigensolver iterations uniformly. Several numerical examples illustrate the effectiveness of this quasi-optimal preconditioning strategy. [ABSTRACT FROM AUTHOR]

In this paper, we propose and analyze the extrapolation method and asymptotically exact a posterior error estimate for eigenvalues of the Morley element. We establish an asymptotic expansion of eigenvalues and prove an optimal result for this expansion and the corresponding extrapolation method. We also design an asymptotically exact a posterior error estimate and propose new approximate eigenvalues with higher accuracy by utilizing this a posteriori error estimate. Finally, several numerical experiments are considered to confirm the theoretical results and compare the performance of the proposed methods. [ABSTRACT FROM AUTHOR]

A Dirichlet k-partition of a domain is a collection of k pairwise disjoint open subsets such that the sum of their first Laplace--Dirichlet eigenvalues is minimal. In this paper, we propose a new relaxation of the problem by introducing auxiliary indicator functions of domains and develop a simple and efficient diffusion generated method to compute Dirichlet k-partitions for arbitrary domains. The method only alternates three steps: (1) convolution, (2) thresholding, and (3) projection. The method is simple, easy to implement, and insensitive to initial guesses and can be effectively applied to arbitrary domains without any special discretization. At each iteration, the computational complexity is linear in the discretization of the computational domain. Moreover, we theoretically prove the energy decaying property of the method. Experiments are performed to show the accuracy of approximation, efficiency, and unconditional stability of the algorithm. We apply the proposed algorithms on both 2- and 3-dimensional flat tori, triangle, square, pentagon, hexagon, disk, three-fold star, five-fold star, cube, ball, and tetrahedron domains to compute Dirichlet k-partitions for different k to show the effectiveness of the proposed method. Compared to previous work with reported computational time, the proposed method achieves hundreds of times acceleration. [ABSTRACT FROM AUTHOR]

We prove that we can always construct strongly minimal linearizations of an arbitrary rational matrix from its Laurent expansion around the point at infinity, which happens to be the case for polynomial matrices expressed in the monomial basis. If the rational matrix has a particular self-conjugate structure, we show how to construct strongly minimal linearizations that preserve it. The structures that are considered are the Hermitian and skew-Hermitian rational matrices with respect to the real line, and the para-Hermitian and para-skew-Hermitian matrices with respect to the imaginary axis. We pay special attention to the construction of strongly minimal linearizations for the particular case of structured polynomial matrices. The proposed constructions lead to efficient numerical algorithms for constructing strongly minimal linearizations. The fact that they are valid for any rational matrix is an improvement on any other previous approach for constructing other classes of structure preserving linearizations, which are not valid for any structured rational or polynomial matrix. The use of the recent concept of strongly minimal linearization is the key for getting such generality. Strongly minimal linearizations are Rosenbrock's polynomial system matrices of the given rational matrix, but with a quadruple of linear polynomial matrices (i.e., pencils): L(\lambda) := \Bigl[ A(\lambda) B(\lambda) C(\lambda) D(\lambda) \Bigr], where A(\lambda) is regular, and the pencils \bigl[ A(\lambda) B(\lambda) \bigr] and \Bigl[ A(\lambda) C(\lambda) \Bigr] have no finite or infinite eigenvalues. Strongly minimal linearizations contain the complete information about the zeros, poles, and minimal indices of the rational matrix and allow one to very easily recover its eigenvectors and minimal bases. Thus, they can be combined with algorithms for the generalized eigenvalue problem for computing the complete spectral information of the rational matrix. [ABSTRACT FROM AUTHOR]

We determine the generic complete eigenstructures for n \times n complex symmetric matrix polynomials of odd grade d and rank at most r. More precisely, we show that the set of n Ã-- n complex symmetric matrix polynomials of odd grade d, i.e., of degree at most d, and rank at most r is the union of the closures of the [rd/2] + 1 sets of symmetric matrix polynomials having certain, explicitly described, complete eigenstructures. Then we prove that these sets are open in the set of nÃ--n complex symmetric matrix polynomials of odd grade d and rank at most r. In order to prove the previous results, we need to derive necessary and sufficient conditions for the existence of symmetric matrix polynomials with prescribed grade, rank, and complete eigenstructure in the case where all their elementary divisors are different from each other and of degree 1. An important remark on the results of this paper is that the generic eigenstructures identified in this work are completely different from the ones identified in previous works for unstructured and skew-symmetric matrix polynomials with bounded rank and fixed grade larger than 1, because the symmetric ones include eigenvalues while the others not. This difference requires using new techniques. [ABSTRACT FROM AUTHOR]

This paper is concerned with the one-dimensional version of a specific member of the (abcd) family of Boussinesq systems having the higher possible dispersion and eigenvalues with nontrivial zeros. We will establish two different long time existence results for the solutions of the Cauchy problem. The first result concerns the system {∂tζ + (1 + ∂²x)∂xv + ∂x(ζv) = 0, ∂tv + (1 + ∂2x)∂xζ+1/2 ∂x(v²) = 0} without a small parameter. If the initial data is of order O (ε), we prove that the existence time scale is of 1/ε4/3, which improves the result 1/ε that could be obtained by a 'dispersive" method (that is, using essentially the dispersive properties of the linear part). The second result is about the system { ∂tζ+(1+ε∂²x)∂xv+ε ∂x(ζv) = 0, ∂tv+(1+ε ∂²x)∂xζ+ε/2 ∂x(v²) = 0}, which involves a small parameter ε in front of the dispersive and nonlinear terms and which is the form obtained when the system is derived from the water wave system in the KdV/Boussinesq regime. If the initial data is of order O(1), we obtain the existence time scale 1/ε2/3, which improves the result 1/√ε obtained by a dispersive method. These results were not included in the previous papers dealing with similar issues because of the presence of zeros in the phases. The proof involves normal form transformations suitably modified away from the zero set of the phases [ABSTRACT FROM AUTHOR]

This paper presents a multilevel convergence framework for multigrid-reduction-intime (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles, with different relaxation schemes, by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time-stepping operator, analyzed directly and bounded in the norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time-stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic (anisotropic diffusion) and hyperbolic (wave equation) model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for estimating MGRIT convergence a priori and for the design of a convergent algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms and the benefit of a stronger relaxation scheme. An important observation is that with increasing numbers of levels MGRIT convergence deteriorates for the hyperbolic model problem, while constant convergence factors can be achieved for the diffusion equation. The theory also indicates that L-stable Runge--Kutta schemes are more amendable to multilevel parallel-in-time integration with MGRIT than A-stable Runge--Kutta schemes. [ABSTRACT FROM AUTHOR]

Two asymptotically exact a posteriori error estimates are proposed for eigenvalues by the nonconforming Crouzeix--Raviart and enriched Crouzeix--Raviart elements. The main challenge in the design of such error estimators comes from the nonconformity of the finite element spaces used. Such nonconformity causes two difficulties: the first is the construction of high accuracy gradient recovery algorithms, and the second is a computable high accuracy approximation of a consistency error term. The first difficulty was solved for both nonconforming elements in a previous paper. Two methods are proposed to solve the second difficulty in the present paper. In particular, this solution allows the use of high accuracy gradient recovery techniques. Further, a postprocessing algorithm is designed by utilizing asymptotically exact a posteriori error estimators to construct the weights of a combination of two approximate eigenvalues. This algorithm requires solving only one eigenvalue problem and admits high accuracy eigenvalue approximations both theoretically and numerically. [ABSTRACT FROM AUTHOR]

Generalized eigenvalue problems involving a singular pencil may be very challenging to solve, both with respect to accuracy and efficiency. While Part I presented a rank-completing addition to a singular pencil, we now develop two alternative methods. The first technique is based on a projection onto subspaces with dimension equal to the normal rank of the pencil while the second approach exploits an augmented matrix pencil. The projection approach seems to be the most attractive version for generic singular pencils because of its efficiency, while the augmented pencil approach may be suitable for applications where a linear system with the augmented pencil can be solved efficiently. [ABSTRACT FROM AUTHOR]

A successful computational approach for solving large-scale positive semidefinite (PSD) programs is to enforce PSD-ness on only a collection of submatrices. For our study, we let Sn,k be the convex cone of n x n symmetric matrices where all k x k principal submatrices are PSD. We call a matrix in this k-locally PSD. In order to compare Sn,k to the cone of PSD matrices, we study eigenvalues of k-locally PSD matrices. The key insight in this paper is that there is a convex cone H(ekn) so that if X ∈ Sn,k, then the vector of eigenvalues of X is contained in H(ekn). The cone H(ekn) is the hyperbolicity cone of the elementary symmetric polynomial ekn (where ekn(x) = Σs⊆[n]:|s|=k ∏i∈s xi) with respect to the all ones vector. Using this insight, we are able to improve previously known upper bounds on the Frobenius distance between matrices in Sn,k and PSD matrices. We also study the quality of the convex relaxation H(ekn). We first show that this relaxation is tight for the case of k = n -- 1, that is, for every vector in H(en-1n) there exists a matrix in Sn,n-1 whose eigenvalues are equal to the components of the vector. We then prove a structure theorem on nonsingular matrices in Sn,k all of whose k x k principal minors are zero, which we believe is of independent interest. This result shows shows that for 1 < k < n -- 1 "large parts" of the boundary of H(ekn) do not intersect with the eigenvalues of matrices in Sn,k. [ABSTRACT FROM AUTHOR]

Recursive systems of unimodal type may exhibit rich propagation dynamics. The shape of traveling wave profiles is one of the unsolved questions in this challenging topic. In this paper, we obtain criteria for the nonmonotonicity of wave profiles in terms of an eigenvalue problem. The proofs rely on establishing several nonlocal Harnack type inequalities, which may be of interest on their own. The existence and uniqueness of traveling waves are also obtained based on these inequalities. [ABSTRACT FROM AUTHOR]

In this paper we study Lipschitz regularity of elliptic PDEs on geometric graphs, constructed from random data points. The data points are sampled from a distribution supported on a smooth manifold. The family of equations that we study arises in data analysis in the context of graph-based learning and contains, as important examples, the equations satisfied by graph Lapla-cian eigenvectors. In particular, we prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues. Our analysis relies on a probabilistic coupling argument of suitable random walks at the continuum level, and an interpolation method for extending functions on random point clouds to the continuum manifold. As a byproduct of our general regularity results, we obtain high probability L∞ and approximate C0,1 convergence rates for the convergence of graph Laplacian eigenvectors toward eigenfunctions of the corresponding weighted Laplace-Beltrami operators. The convergence rates we obtain scale like the L² convergence rates established in J. Calder and N. Garcia Trillos, arXiv:1910.13476, 2019. [ABSTRACT FROM AUTHOR]

This paper is mainly concerned with a two-species competition model in open advective environments, where individuals cannot pass through the upstream boundary and do not return to the habitat after leaving the downstream boundary. By the theory of principal eigenvalue, we first obtain two critical curves (Γ1 and Γ2) in the plane of bifurcation parameters that sharply determine the local stability of the two semitrivial steady states. Then under various conditions on given parameters, we discuss the global dynamics via different techniques, including the comparison principle for eigenvalues and perturbation and compactness arguments, and show that both competitive exclusion and coexistence are possible. For general values of parameters, we take both analytic and numerical approaches to further understand the potential behaviors of Γ1 and Γ2, and we numerically observe that in addition to the competitive exclusion and coexistence, the bistable phenomenon is also possible, which is different from the known results of competitive ODE and reaction-diffusion systems (where bistability is impossible). The implication of our numerical results on future work is also discussed. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of single-ratio fractional minimization problems, in which the numerator of the objective is the sum of a nonsmooth nonconvex function and a smooth nonconvex function while the denominator is a nonsmooth convex function. In this work, we first derive its first-order necessary optimality condition, by using the first-order operators of the three functions involved. Then we develop first-order algorithms, namely, the proximity-gradientsubgradient algorithm (PGSA), PGSA with monotone line search (PGSA ML), and PGSA with nonmonotone line search (PGSA NL). It is shown that any accumulation point of the sequence generated by them is a critical point of the problem under mild assumptions. Moreover, we establish global convergence of the sequence generated by PGSA or PGSA ML and analyze its convergence rate, by further assuming the local Lipschitz continuity of the nonsmooth function in the numerator, the smoothness of the denominator, and the Kurdyka--Łojasiewicz (KL) property of the objective. The proposed algorithms are applied to the sparse generalized eigenvalue problem associated with a pair of symmetric positive semidefinite matrices, and the corresponding convergence results are obtained according to their general convergence theorems. We perform some preliminary numerical experiments to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In [IMA J. Numer. Anal., 29 (2009), pp. 24--42], Nielsen, Tveito, and Hackbusch study the operator generated by using the inverse of the Laplacian as the preconditioner for second order elliptic PDEs-Δ · (k(x)Δu) = f. They prove that the range of k(x) is contained in the spectrum of the preconditioned operator, provided that k(x) is continuous. Their rigorous analysis only addresses mappings defined on infinite dimensional spaces, but the numerical experiments in the paper suggest that a similar property holds in the discrete case. Motivated by this investigation, we analyze the eigenvalues of the matrix L-1 A, where L and A are the stiffness matrices associated with the Laplace operator and second order elliptic operators with a scalar coefficient function, respectively. Using only technical assumptions on k(x), we prove the existence of a one-to-one pairing between the eigenvalues of L-1 A and the intervals determined by the images under k(x) of the supports of the finite element nodal basis functions. As a consequence, we can show that the nodal values of k(x) yield accurate approximations of the eigenvalues of L-1 A. Our theoretical results, including their relevance for understanding how the convergence of the conjugate gradient method may depend on the whole spectrum of the preconditioned matrix, are illuminated by several numerical experiments. [ABSTRACT FROM AUTHOR]

The structural data of any rational matrix R(λ), i.e., the structural indices of its poles and zeros together with the minimal indices of its left and right nullspaces, is known to satisfy a simple condition involving certain sums of these indices. This fundamental constraint was first proved by Van Dooren in 1978; here we refer to this result as the rational index sum theorem. An analogous result for polynomial matrices has been independently discovered (and rediscovered) several times in the past three decades. In this paper we clarify the connection between these two seemingly different index sum theorems, describe a little bit of the history of their development, and discuss their curious apparent unawareness of each other. Finally, we use the connection between these results to solve a fundamental inverse problem for rational matrices--for which lists L of prescribed structural data does there exist some rational matrix R(λ) that realizes exactly the list L? We show that Van Dooren's condition is the only constraint on rational realizability; that is, a list L is the structural data of some rational matrix R(λ) if and only if L satisfies the rational index sum condition. [ABSTRACT FROM AUTHOR]

This paper is dedicated to robust matrix eigenvalue clustering in a subregion D of the complex plane. A norm-bounded uncertainty is considered. D is any intersection and/or union of half planes, discs, and outsides of discs. This work aims at computing the associated complex D-stability radius. This challenge was already tackled in a recent paper but the technique therein may fail or lead to conservative results when the subregions overlap. The present paper proposes to circumvent those limits thanks to an extended version of the Kalman-Yakubovich-Popov (KYP) lemma which is deduced from the so-called generalized S-procedure. [ABSTRACT FROM AUTHOR]