Computing Derivatives of Eigenvalues and Elgenvectors by Simultaneous Iteration

A simultaneous iteration scheme of Andrew is analysed and extended,and developed into an effective algorithm for numerical computationof partial derivatives of several eigenvalues and eigenvectorsof a matrix which depends on a number of parameters. It is shownthat, with exact computation, application of either the vector-algorithm or the topological -algorithm to this method producesthe exact solution in a small number of steps. Numerical testsconfirm the viability of the method.     

Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices

This report may be considered as a non-trivial extension of an unpublished report by William Kahan (Accurate Eigenvalues of a symmetric tri-diagonal matrix, Technical Report CS 41, Computer Science Department, Stanford University, 1966). His interplay between matrix theory and computer arithmetic led to the development of algorithms for computing accurate eigenvalues and singular values. His report is generally considered as the precursor for the development of IEEE standard 754 for binary arithmetic. This standard has been universally adopted by virtually all PC, workstation and midrange hardware manufactures and tens of billions of such machines have been produced. Now we use the features in this standard to improve the original algorithm.In this paper, we describe an algorithm in floating-point arithmetic to compute the exact inertia of a real symmetric (shifted) tridiagonal matrix. The inertia, denoted by the integer triplet (π, ν, ζ), is defined as the number of positive, negative and zero eigenvalues of a real symmetric (or complex Hermitian) matrix and the adjective exact refers to the eigenvalues computed in exact arithmetic. This requires the floating-point computation of the diagonal matrix D of the LDL^t factorization of the shifted tridiagonal matrix T − τI with +∞ and −∞ rounding modes defined in IEEE 754 standard. We are not aware of any other algorithm which gives the exact answer to a numerical problem when implemented in floating-point arithmetic in standard working precisions. The guaranteed intervals for eigenvalues are obtained by bisection or multisection with this exact inertia information. Similarly, using the Golub-Kahan form, guaranteed intervals for singular values of bidiagonal matrices can be computed. The diameter of the eigenvalue (singular value) intervals depends on the number of shifts with inconsistent inertia in two rounding modes. Our algorithm not only guarantees the accuracy of the solutions but is also consistent across different IEEE 754 standard compliant architectures. The unprecedented accuracy provided by our algorithms could be also used to debug and validate standard floating-point algorithms for computation of eigenvalues (singular values). Accurate eigenvalues (singular values) are also required by certain algorithms to compute accurate eigenvectors (singular vectors).We demonstrate the accuracy of our algorithms by using standard matrix examples. For the Wilkinson matrix, the eigenvalues (in IEEE double precision) are very accurate with an (open) interval diameter of 6 ulps (units of the last place held of the mantissa) for one of the eigenvalues and lesser (down to 2 ulps) for others. These results are consistent across many architectures including Intel, AMD, SGI and DEC Alpha. However, by enabling IEEE double extended precision arithmetic in Intel/AMD 32-bit architectures at no extra computational cost, the (open) interval diameters were reduced to one ulp, which is the best possible solution for this problem. We have also computed the eigenvalues of a tridiagonal matrix which manifests in Gauss-Laguerre quadrature and the results are extremely good in double extended precision but less so in double precision. To demonstrate the accuracy of computed singular values, we have also computed the eigenvalues of the Kac₃₀ matrix, which is the Golub-Kahan form of a bidiagonal matrix. The tridiagonal matrix has known integer eigenvalues. The bidiagonal Cholesky factor of the Gauss-Laguerre tridiagonal is also included in the singular value study.     

A numerical method for computing the Hamiltonian Schur form

We derive a new numerical method for computing the Hamiltonian Schur form of a Hamiltonian matrix that has no purely imaginary eigenvalues. We demonstrate the properties of the new method by showing its performance for the benchmark collection of continuous-time algebraic Riccati equations. Despite the fact that no complete error analysis for the method is yet available, the numerical results indicate that if no eigenvalues of are close to the imaginary axis then the method computes the exact Hamiltonian Schur form of a nearby Hamiltonian matrix and thus is numerically strongly backward stable. The new method is of complexity and hence it solves a long-standing open problem in numerical analysis. Volker Mehrmann was supported by Deutsche Forschungsgemeinschaft, Research Grant Me 790/11-3.     

Arnoldi and Jacobi-Davidson methods for generalized eigenvalue problems

In many physical situations, a few specific eigenvalues of a large sparse generalized eigenvalue problem are needed. If exact linear solves with are available, implicitly restarted Arnoldi with purification is a common approach for problems where is positive semidefinite. In this paper, a new approach based on implicitly restarted Arnoldi will be presented that avoids most of the problems due to the singularity of . Secondly, if exact solves are not available, Jacobi-Davidson QZ will be presented as a robust method to compute a few specific eigenvalues. Results are illustrated by numerical experiments.

     

On a variational approximation method for a class of elliptic eigenvalue problems in composite structures

We consider a second-order elliptic eigenvalue problem on a convex polygonal domain, divided in nonoverlapping subdomains. The conormal derivative of the unknown function is continuous on the interfaces, while the function itself is discontinuous. We present a general finite element method to obtain a numerical solution of the eigenvalue problem, starting from a nonstandard formally equivalent variational formulation in an abstract setting in product Hilbert spaces. We use standard Lagrange finite element spaces on the subdomains. Moreover, the bilinear forms are approximated by suitable numerical quadrature formulas. We obtain error estimates for both the eigenfunctions and the eigenvalues, allowing for the case of multiple exact eigenvalues, by a pure variational method.

     

Radiation damping of “whispering gallery” type oscillations in the case of a sharp variation of the radius of curvature of the boundary

One investigates the radiation damping of whispering gallery waves. For a prolate ellipse it is shown that, in the neighborhood of the minimum of the radius of curvature, the solution, obtained with the aid of the complex ray method, coincides with the asymptotics of the exact eigenfunction. One isolates a class of boundaries for which one can use the complex ray method for the computation of the eigenvalues.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 129, pp. 149–151, 1983.The author is grateful to I. A. Molotkov for discussions.     

Error-free matrix symmetrizers and equivalent symmetric matrices

A symmetrizer of the matrix A is a symmetric solution X that satisfies the matrix equation XA=AX. An exact matrix symmetrizer is computed by obtaining a general algorithm and superimposing a modified multiple modulus residue arithmetic on this algorithm. A procedure based on computing a symmetrizer to obtain a symmetric matrix, called here an equivalent symmetric matrix, whose eigenvalues are the same as those of a given real nonsymmetric matrix is presented.Supported by CSIR.     

Operators,absolutely indefinitely bounded below,in spaces with indefinite metric

Let r be the spectral radius of an operatorU, absolutely indefinitely bounded below. It is proved that r = c^1/, where c is the exact lower bound ofU and is a number occurring in the definition of the I-metric. A bound is obtained for the dimensionality of the direct sum of root lineals ofU (c 1), corresponding to eigenvalues whose absolute values are smaller than unity.Translated from Matematicheskie Zametki, Vol. 10, No. 3, pp. 301–305, September, 1971.     

On spectral variations under bounded real matrix perturbations

Summary In this paper we investigate the set of eigenvalues of a perturbed matrix {ie509-1} whereA is given and ^{n × n}, ||< is arbitrary. We determine a lower bound for thisspectral value set which is exact for normal matricesA with well separated eigenvalues. We also investigate the behaviour of the spectral value set under similarity transformations. The results are then applied tostability radii which measure the distance of a matrixA from the set of matrices having at least one eigenvalue in a given closed instability domain _b.     

A Low-Complexity Divide-and-Conquer Method for Computing Eigenvalues and Eigenvectors of Symmetric Band Matrices

A framework for an efficient low-complexity divide-and-conquer algorithm for computing eigenvalues and eigenvectors of an n × n symmetric band matrix with semibandwidth b n is proposed and its arithmetic complexity analyzed. The distinctive feature of the algorithm—after subdivision of the original problem into p subproblems and their solution—is a separation of the eigenvalue and eigenvector computations in the central synthesis problem. The eigenvalues are computed recursively by representing the corresponding symmetric rank b(p–1) modification of a diagonal matrix as a series of rank-one modifications. Each rank-one modifications problem can be solved using techniques developed for the tridiagonal divide-and-conquer algorithm. Once the eigenvalues are known, the corresponding eigenvectors can be computed efficiently using modified QR factorizations with restricted column pivoting. It is shown that the complexity of the resulting divide-and-conquer algorithm is O (n ² b ²) (in exact arithmetic).This revised version was published online in October 2005 with corrections to the Cover Date.     

Certain modifications of the AB-algorithm

One considers various modifications of the AB-algorithm for the solution of the complete (partial) eigenvalue problem of a regular pencil A-B of square matrices. A modification of the AB-algorithm is suggested which allows to eliminate in a finite number of steps the zero and the infinite eigenvalues of the pencil A-B and to lower its dimensions. For regular pencils with real eigenvalues a modification ot the AB-algorithm with a shift is presented. For a well-defined choice of the shifts one proves the quadratic convergence of the algorithm, successively to each eigenvalue of the pencil, starting with the smallest one. For a pencil whose eigenvalues can be divided into the groups of large and small eigenvalues, one considers a modification of the AB-algorithm, allowing to obtain approximations to the indicated groups of eigenvalues as solutions of a problem for pencils of lower dimensions.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 117–136, 1981     

Multiplicity and eigenvalue intersecting nonlinearities

Summary Several results on the existence of multiple solutions are proved for nonlinear Sturm-Liouville equations with nonlinearities which cross asymptotically some eigenvalues of the linear operator (so-called jumping nonlinearities).By a change of variable the problem is transformed into a bifurcation equation. The bifurcation branches of this equation are seen to start in linear eigenvalues and to end asymptotically in nonlinear eigenvalues (split eigenvalues). This allows to deduce in a unified way several multiplicity results.     

Limit points of eigenvalues of (di)graphs

The study on limit points of eigenvalues of undirected graphs was initiated by A. J. Hoffman in 1972. Now we extend the study to digraphs. We prove 1. Every real number is a limit point of eigenvalues of graphs. Every complex number is a limit point of eigenvalues of digraphs. 2. For a digraph D, the set of limit points of eigenvalues of iterated subdivision digraphs of D is the unit circle in the complex plane if and only if D has a directed cycle. 3. Every limit point of eigenvalues of a set D of digraphs (graphs) is a limit point of eigenvalues of a set of bipartite digraphs (graphs), where consists of the double covers of the members in D. 4. Every limit point of eigenvalues of a set D of digraphs is a limit point of eigenvalues of line digraphs of the digraphs in D. 5. If M is a limit point of the largest eigenvalues of graphs, then −M is a limit point of the smallest eigenvalues of graphs.     

Eigenvalue problem for a regular linear pencil of matrices close to singular ones

The solution is examined of the eigenvalue problem (1) for a regular linear pencil of matrices A and B of which at least one is close to being singular. Two groups of algorithms are proposed for solving (1). Both groups of algorithms work in the situation when the eigenvalues of the original pencil can be separated into groups of eigenvalues large and small in absolute value. The algorithms reveal this situation. The algorithms of the first group permit the passage from the original pencil to a pencil strictly equivalent to it, which in form is close to a quasitriangular pencil (or coincides with a quasitriangular one in case at least one of the pencil's matrices is singular). The eigenvalues of the diagonal blocks of the pencil constructed yield approximations to the eigenvalues of problem (1). If the approximations obtained are refined by the Newton method, using the normalized decomposition of auxiliary constructed matrices, then both the eigenvalues of (1) as well as all the linearly independent eigenvectors corresponding to them can be found. The algorithms of the second group permit the passage from the original pencil to a strictly equivalent pencil representable as a sum of two singular pencils whose null spaces are mutually perpendicular; next, with the aid of an iteration process based on the use of perturbation theory, these algorithms permit the finding of the eigenvalues of pencil (1), small (large) in absolute value, and the eigenvectors corresponding to them. Ill-conditioned regular pencils close to singular ones also are examined. For them an algorithm is suggested which permits the ill conditioning to be revealed and permits approximations to the stable (to perturbations in the original data) eigenvalues of the pencil to be obtained.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 63–82, 1979.     

Exact formulae and matrix-less eigensolvers for block banded symmetric Toeplitz matrices

Precise asymptotic expansions for the eigenvalues of a Toeplitz matrix \(T_n(f)\), as the matrix size n tends to infinity, have recently been obtained, under suitable assumptions on the associated generating function f. A restriction is that f has to be polynomial, monotone, and scalar-valued. In this paper we focus on the case where \(\mathbf {f}\) is an \(s\times s\) matrix-valued trigonometric polynomial with \(s\ge 1\), and \(T_n(\mathbf {f})\) is the block Toeplitz matrix generated by \(\mathbf {f}\), whose size is \(N(n,s)=sn\). The case \(s=1\) corresponds to that already treated in the literature. We numerically derive conditions which ensure the existence of an asymptotic expansion for the eigenvalues. Such conditions generalize those known for the scalar-valued setting. Furthermore, following a proposal in the scalar-valued case by the first author, Garoni, and the third author, we devise an extrapolation algorithm for computing the eigenvalues of banded symmetric block Toeplitz matrices with a high level of accuracy and a low computational cost. The resulting algorithm is an eigensolver that does not need to store the original matrix, does not need to perform matrix-vector products, and for this reason is called matrix-less. We use the asymptotic expansion for the efficient computation of the spectrum of special block Toeplitz structures and we provide exact formulae for the eigenvalues of the matrices coming from the \(\mathbb {Q}_p\) Lagrangian Finite Element approximation of a second order elliptic differential problem. Numerical results are presented and critically discussed.     

Signal Decoupling with Preview in the Geometric Context: Exact Solution for Nonminimum-Phase Systems

The problem of making the output of a discrete-time linear system totally insensitive to an exogenous input signal known with preview is tackled in the geometric approach context. A necessary and sufficient condition for exact decoupling with stability in the presence of finite preview is introduced, where the structural aspects and the stabilizability aspects are considered separately. On the assumption that structural decoupling is feasible, internal stabilizability of the minimal self-bounded controlled invariant satisfying the structural constraint guarantees the stability of the dynamic feedforward compensator. However, if the structural decoupling is feasible, but is not internally stabilizable, exact decoupling is nonetheless achievable with a stable feedforward compensator on the sole assumption that has no unassignable internal eigenvalues on the unit circle, provided that the signal to be rejected is known with infinite preview. An algorithmic framework based on steering-along-zeros techniques, completely devised in the time domain, shows how to compute the convolution profile of the feedforward compensator in each case. Communicated by G. Leitmann     

Spectral Asymptotics for a Steady-State Heat Conduction Problem in a Perforated Domain

In this paper we study the eigenvalues and eigenfunctions of a boundary-value problem for an elliptic equation of second order with oscillatory coefficients in a periodically perforated domain when the boundary condition on the external boundary is of the first type and on the boundary of holes of the third type, for the case in which the linear dimension of the perforation period tends to zero. It is proved that these eigenvalues and eigenfunctions can be determined approximately via the eigenvalues and eigenfunctions of an essentially simpler Dirichlet problem for an elliptic equation with constant coefficients in a domain without holes. Estimates of errors in these approximations are given.     

Solutions of the spatially-dependent mass Dirac equation with the spin and pseudospin symmetry for the Coulomb-like potential

We study the effect of spatially-dependent mass function over the solution of the Dirac equation with the Coulomb potential in the (3+1)-dimensions for any arbitrary spin-orbit κ state. In the framework of the spin and pseudospin symmetry concept, the analytic bound state energy eigenvalues and the corresponding upper and lower two-component spinors of the two Dirac particles are obtained by means of the Nikiforov-Uvarov method, in closed form. This physical choice of the mass function leads to an exact analytical solution for the pseudospin part of the Dirac equation. The special cases , the constant mass and the non-relativistic limits are briefly investigated.     

Immersed Hypersurfaces in the Unit Sphere S^m＋1 with Constant Blaschke Eigenvalues

For an immersed submanifold x ： M^m→ Sn in the unit sphere S^n without umbilics, an eigenvalue of the Blaschke tensor of x is called a Blaschke eigenvalue of x. It is interesting to determine all hypersurfaces in Sn with constant Blaschke eigenvalues. In this paper, we are able to classify all immersed hypersurfaces in S^m＋1 with vanishing MSbius form and constant Blaschke eigenvalues, in case （1） x has exact two distinct Blaschke eigenvalues, or （2） m = 3. With these classifications, some interesting examples are also presented.     

A new definition of geometric multiplicity of eigenvalues of tensors and some results based on it

We give a new definition of geometric multiplicity of eigenvalues of tensors, and based on this, we study the geometric and algebraic multiplicity of irreducible tensors’ eigenvalues. We get the result that the eigenvalues with modulus ρ(A) have the same geometric multiplicity. We also prove that twodimensional nonnegative tensors’ geometric multiplicity of eigenvalues is equal to algebraic multiplicity of eigenvalues.