Efficient computation of high index Sturm-Liouville eigenvalues for problems in physics

Finding the eigenvalues of a Sturm-Liouville problem can be a computationally challenging task, especially when a large set of eigenvalues is computed, or just when particularly large eigenvalues are sought. This is a consequence of the highly oscillatory behavior of the solutions corresponding to high eigenvalues, which forces a naive integrator to take increasingly smaller steps. We will discuss the most used approaches to the numerical solution of the Sturm-Liouville problem: finite differences and variational methods, both leading to a matrix eigenvalue problem; shooting methods using an initial-value solver; and coefficient approximation methods. Special attention will be paid to techniques that yield uniform approximation over the whole eigenvalue spectrum and that allow large steps even for high eigenvalues.     

Projection and deflation method for partial pole assignment inlinear state feedback

Two projection methods are proposed for partial pole placement in linear control systems. These methods are of interest when the system is very large and only a few of its poles must be assigned. The first method is based on computing an orthonormal basis of the left invariant subspace associated with the eigenvalues to be assigned and then solving a small inverse eigenvalue problem resulting from projecting the initial problem into that subspace. The second method can be regarded as a variant of the Weilandt deflation technique used in eigenvalue methods     

Computing Extremal Eigenvalues for Three-Dimensional Photonic Crystals with Wave Vectors Near the Brillouin Zone Center

The band structures of three-dimensional photonic crystals can be determined numerically by solving a sequence of generalized eigenvalue problems. However, not all of the spectral structures of these eigenvalue problems are well-understood, and not all of these eigenvalue problems can be solved efficiently. This article focuses on the eigenvalue problems corresponding to wave vectors that are close to the center of the Brillouin zone of a three dimensional, simple cubic photonic crystal. For these eigenvalue problems, there are (i) many zero eigenvalues, (ii) a couple of near-zero eigenvalues, and (iii) several larger eigenvalues. As the desired eigenvalues are the smallest positive eigenvalues, these particular spectral structures prevent regular eigenvalue solvers from efficiently computing the desired eigenvalues. We study these eigenvalue problems from the perspective of both theory and computation. On the theoretical side, the structures of the null spaces are analyzed to explicitly determine the number of zero eigenvalues of the target eigenvalue problems. On the computational side, the Krylov-Schur and Jacobi-Davidson methods are used to compute the smallest, positive, interior eigenvalues that are of interest. Intensive numerical experiments disclose how the shift values, conditioning numbers, and initial vectors affect the performance of the tested eigenvalue solvers and suggest the most efficient eigenvalue solvers.     

一种基于互信息的特征跃迁示例学习法

给出一种能够接受特征及变化的示例学习方法。该方法是对ID3方法的一种改进,传统ID3方法是基于持征值的学习,训练示例是若干组静态特征值,其局限性在于不能理解和记忆特征的变化信息,尤其没考虑特征间的动态相关。改进后的方能学习动态特征,接受的训练示例是特征值在一定间隔内的初值和终值,从中获取特征值及其在指定间隔的跃迁,该方法能够学习数据动态趋势,尤其能够挖掘出特征间动态相关。通过若干例子测试,该方法适用于具有多元动态相关特征问题的分类。     

Computing eigenvalue bounds for iterative subspace matrix methods

A procedure is presented for the computation of bounds to eigenvalues of the generalized hermitian eigenvalue problem and to the standard hermitian eigenvalue problem. This procedure is applicable to iterative subspace eigenvalue methods and to both outer and inner eigenvalues. The Ritz values and their corresponding residual norms, all of which are computable quantities, are needed by the procedure. Knowledge of the exact eigenvalues is not needed by the procedure, but it must be known that the computed Ritz values are isolated from exact eigenvalues outside of the Ritz spectrum and that there are no skipped eigenvalues within the Ritz spectrum range. A multipass refinement procedure is described to compute the bounds for each Ritz value. This procedure requires O(m) effort where m is the subspace dimension for each pass.     

Feedback placement of eigenvalues for a Hilbert space oscillator

Consider the effect of a compact linear feedback control on the eigenvalues of a Hilbert space oscillator. It is shown that the kth eigenvalue can be perturbed a distance of only if a sequence is summable. Conditions are also derived under which a sequence of complex numbers can be obtained as eigenvalues using such a feedback control. The analysis gives an explicit form for the control in terms of the desired eigenvalues. A simple application to the stabilization problem for water waves in a finite tank is given.     

A High Accuracy Post-processing Algorithm for the Eigenvalues of Elliptic Operators

In a very recent paper (Hu et al., The lower bounds for eigenvalues of elliptic operators by nonconforming finite element methods, Preprint, 2010), we prove that the eigenvalues by the nonconforming finite element methods are smaller than the exact ones for the elliptic operators. It is well-known that the conforming finite element methods produce the eigenvalues above to the exact ones. In this paper, we combine these two aspects and derive a new post-processing algorithm to approximate the eigenvalues of elliptic operators. We implement this algorithm and find that it actually yields very high accuracy approximation on very coarser mesh. The numerical results demonstrate that the high accuracy herein is of two fold: the much higher accuracy approximation on the very coarser mesh and the much higher convergence rate than a single lower/upper bound approximation. Moreover, we propose some acceleration technique for the algorithm of the discrete eigenvalue problem based on the solution of the discrete eigenvalue problem which yields the upper bound of the eigenvalue. With this acceleration technique we only need several iterations (two iterations in our example) to find the numerical solution of the discrete eigenvalue problem which produces the lower bound of the eigenvalue. Therefore we only need to solve essentially one discrete eigenvalue problem.     

On a class of generalized eigenvalue problems and equivalent eigenvalue problems that arise in systems and control theory

Systems and control theory has long been a rich source of problems for the numerical linear algebra community. In many problems, conditions on analytic functions of a complex variable are usually evaluated by solving a special generalized eigenvalue problem. In this paper we develop a general framework for studying such problems. We show that for these problems, solutions can be obtained by either solving a generalized eigenvalue problem, or by solving an equivalent eigenvalue problem. A consequence of this observation is that these problems can always be solved by finding the eigenvalues of a Hamiltonian (or discrete-time counterpart) matrix, even in cases where an associated Hamiltonian matrix, cannot (normally) be defined. We also derive a number of new compact tests for determining whether or not a transfer function matrix is strictly positive real. These tests, which are of independent interest due to the fact that many problems can be recast as SPR problems, are defined even in the case when the matrix D+D^∗ is singular, and can be formulated without requiring inversion of the system matrix A.     

求解对称区间矩阵标准特征值的进化策略新算法

针对实对称区间矩阵的特征值问题,将区间不确定量看成是围绕区间中点的一种摄动,提出了一种基于区间扩张的对称区间矩阵特征值问题求解的进化策略算法。将区间矩阵中点作为平衡点,区间不确定量作为相应的扰动量,根据摄动公式求出区间矩阵的最大特征值和最小特征值,从而获得区间矩阵特征值问题的解。算例显示了该算法的有效性,其主要特点是收敛速度快、求解区间精度高。     

The eigenvalue problem (A − λB)x = 0 for symmetric matrices of high order

Vibrational problems of complex structures treated by the method of finite elements lead to the general eigenvalue problem $\text{(A ? λB)x = 0}$, where $\text{A}$ and $\text{B}$ are symmetric and sparse matrices of high order. The smallest eigenvalues and corresponding eigenvectors of interest are usually computed by a variant of the inverse vector iteration. Instead of this, the smallest eigenvalue can be computed as the minimum of the corresponding Rayleigh quotient for instance by the method of the coordinate relaxation of Faddejew/Faddejewa. The slow convergence of this simple algorithm can however be sped up considerably in analogy to the successive overrelaxation method by a systematic overrelaxation. Numerical experiments indicate indeed a rate of convergence of this coordinate overrelaxation as a function of the relaxation parameter which is comparable to that of the usual seccessive overrelaxation for linear equations. In comparison with known procedures for the solution of the general eigenvalue problem there result some important computational advantages with regard to the amount of work. Finally, the higher eigenvalues can be computed successively by minimizing the Rayleigh quotient of a modified eigenvalue problem based on a deflation process.     

Discrete least-squares technique for eigenvalues. Part I: The one-dimensional case

A discrete least-squares technique for computing the eigenvalues of differential equations is presented. The eigenvalue approximations are obtained in two steps. Firstly, initial approximations of the desired eigenvalues are computed by solving a quadratic matrix eigenvalue problem resulting from the least-squares method applied to the equation under consideration. Secondly, these initial approximations, being of sufficient accuracy in some cases, are improved by using the Gauss-Newton method. Results from numerical experiments are reported that show great efficiency of the proposed technique in solving both regular and singular one-dimensional problems. The high flexibility of the technique enables one to use also the multidomain approach and the trial functions not satisfying any of the prescribed boundary conditions.     

利用Voronoi协方差矩阵重建隐式曲面

目的 针对含少量离群点的噪声点云,提出了一种Voronoi协方差矩阵的曲面重建方法。方法 以隐函数梯度在Voronoi协方差矩阵形成的张量场内的投影最大化为目标,构建隐函数微分方程,采用离散外微分形式求解连续微分方程,从而将曲面重建问题转化为广义特征值求解问题。在点云空间离散化过程中,附加最短边约束条件,避免了局部空间过度剖分。并引入概率测度理论定义曲面窄带,提高了算法抵抗离群点能力,通过精细剖分曲面窄带,提高了曲面重建精度。结果 实验结果表明,该算法可以抵抗噪声点和离群点的影响,可以生成不同分辨率的曲面。通过调整拟合参数,可以区分曲面的不同部分。结论 提出了一种新的隐式曲面重建方法,无需点云法向、稳健性较强,生成的三角面纵横比好。     

Fast structural optimization with frequency constraints by genetic algorithm using adaptive eigenvalue reanalysis methods

Structural optimization with frequency constraints is highly nonlinear dynamic optimization problems. Genetic algorithm (GA) has greater advantage in global optimization for nonlinear problem than optimality criteria and mathematical programming methods, but it needs more computational time and numerous eigenvalue reanalysis. To speed up the design process, an adaptive eigenvalue reanalysis method for GA-based structural optimization is presented. This reanalysis technique is derived primarily on the Kirsch’s combined approximations method, which is also highly accurate for case of repeated eigenvalues problem. The required number of basis vectors at every generation is adaptively determined and the rules for selecting initial number of basis vectors are given. Numerical examples of truss design are presented to validate the reanalysis-based frequency optimization. The results demonstrate that the adaptive eigenvalue reanalysis affects very slightly the accuracy of the optimal solutions and significantly reduces the computational time involved in the design process of large-scale structures.     

A Spectral-Element Method for Transmission Eigenvalue Problems

We develop an efficient spectral-element method for computing the transmission eigenvalues in two-dimensional radially stratified media. Our method is based on a dimension reduction approach which reduces the problem to a sequence of one-dimensional eigenvalue problems that can be efficiently solved by a spectral-element method. We provide an error analysis which shows that the convergence rate of the eigenvalues is twice that of the eigenfunctions in energy norm. We present ample numerical results to show that the method convergences exponentially fast for piecewise stratified media, and is very effective, particularly for computing the few smallest eigenvalues.     

On the efficient and accurate solution of the skew-symmetric eigenvalue problem: An arrangement of new and already known algorithmic formulations

Algorithms are presented to solve the special eigenvalue problem $\text{AZ}\text{=}\text{Zλ}$, where $\text{A}$ is skew-symmetric. The effective use of Householder's method, the bisection method and inverse iteration for solving the complete eigen-value problem are described in some detail. Simultaneous vector iteration is formulated for skew-symmetric matrices. The amount of work for the skew-symmetric Jacobi algorithm and the simultaneous vector iteration may be reduced by using the solution of a simplified eigenvalue problem. For Hermitian matrices also quadratic eigenvalue bounds for groups of eigenvalues and linear bounds for groups of eigenvectors are derived. The case where the set of calculated eigenvectors is not orthonormal is considered in some detail. In principle, the skew-symmetric eigenvalue problem may be easily transformed into a symmetric eigenvalue problem; but such a procedure has the following disadvantages: first, the results are in general less accurate, and, second, the eigenvectors which belong to well separated eigenvalues are not uniquely determined.     

基于SPSS统计分析的文本特征值提取算法

在文本特征值的信息隐藏过程中,特征值是一个句子固有的属性,具有随机性.通过分析特征值之间的相关关系,找出其分布变化规律,才能控制其变化,以实现更好的信息隐藏.针对文本信息,首先在VC平台下设计出自动的特征值提取算法,然后利用SPSS统计软件统计分析了文本的特征值.实验结果表明该算法的统计分析给出了有效的特征值数据.     

Necessary and sufficient conditions for global optimality of eigenvalue optimization problems

The necessary and sufficient conditions for global optimality are derived for an eigenvalue optimization problem. We consider the generalized eigenvalue problem where real symmetric matrices on both sides are linear functions of design variables. In this case, a minimization problem with eigenvalue constraints can be formulated as Semi-Definite Programming (SDP). From the Karush-Kuhn-Tucker conditions of SDP, the necessary and sufficient conditions are derived for arbitrary multiplicity of the lowest eigenvalues for the case where important lower bound constraints are considered for the design variables. Received May 18, 2000     

A parametric approach to finite-dimensional control of linear distributed-parameter systems

This article considers the design of finite-dimensional compensators for distributed-parameter systems using eigenvalue assignment. The proposed compensator consists of an observer estimating additional outputs and a static feedback of the measurable and the estimated outputs. Since the additional outputs can be asymptotically reconstructed, the compensator can be designed using the separation principle, i.e. the closed-loop eigenvalues are given by the observer eigenvalues and the eigenvalues resulting from the static output feedback control. In order to solve the corresponding eigenvalue assignment problem, the parametric approach for the design of static output feedback controllers in finite-dimensions is extended to distributed-parameter systems. By using a parameter optimisation it is possible to assign all closed-loop eigenvalues within specified regions of the complex plane in order to stabilise the system and to assure a desired control performance. A heat conductor is used to demonstrate the proposed design procedure.     

On the evaluation of the eigenvalues of the finite differences laplacian over a hexagon

Fast numerical methods for the evaluation of the eigenvalues of the finite-differences laplacian over a regular hexagon are devised. At first we show how this eigenvalue problem can be splitted into 3 eigenvalue problems, of lower dimension (reduced by a factor of 1/6), for the discrete laplacian over a regular triangle with suitable boundary conditions. Then, expressing explicitely the eigenvalues and the eigenvectors of the discrete laplacian over a triangle in terms of the coefficients of the discrete Fourier transform, we show how to deal efficiently with each subproblem. In particular we show that each step of the shifted inverse power method, for the approximation of the eigenvalues, costs O(n²log n) arithmetic operations in a sequential model of computation, and O(log n) steps with n² processors in a parallel model of computation, where n is the number of the nodes on the edge of the hexagon. Similar estimates hold for the orthogonal iterations (subspaces iterations) method and for Lanczos method. This approach includes the deflation of the eigenvalues of the triangle from those of the hexagon. These results improve the methods given by Bauer and Reiss [1] allowing a higher precision in the approximation of the eigenvalues of the laplacian and reducing the computational cost, either in a sequential or in a parallel model of computation.     

基于图像特征提取的飞行器故障诊断系统设计

为提高飞行器测试数据的利用率,解决飞行器故障诊断中资源浪费的问题。提出并实现了一种基于数据图像特征提取的飞行器故障自动诊断系统。系统通过建立一个历史测试数据库,对各种测试项目的历史图像提取特征值,将其存储在数据库中,且将该次测试对应的诊断信息存储在内。利用小波变换法作为特征提取的方法,小波能谱熵作为特征值表征。将当前测试故障的数据图像进行特征提取,并与数据库中图像进行比对,找出相似度最高的历史数据图像。从而帮助测试人员进行故障定位诊断工作。