Numerical Algorithms for the Polynomial Eigenvalue Problem

多项式特征值问题（PEP）是求一个方阵的特征值和特征向量，该方阵的元素是变量λ的多项式，其中特征值是矩阵为奇异的λ的值。对于多项式次为1的情况，存在很好的数值方法。2度或更高的矩阵多项式在结构力学、声学系统和电路仿真等领域中经常出现。极端设计的趋势（例如微机电（MEMS）器件和超大型喷气机）意味着这些特征问题通常条件不佳（因此难以精确解决），同时也具有应该在数值方法中利用的代数结构。作为一个具体的例子，在柏林工业大学的一个项目中，对欧洲高速列车的声音和振动水平进行建模，发现标准有限元包在计算解决方案中没有提供正确的数字，直到在本提案中使用的类型的线性代数技术在潜在的二次（2度）特征值问题中发挥作用（参见2004年11月SIAM新闻的封面文章）。解决PEP的标准方法是将问题转化为更大维度的1度特征值问题——线性化过程。这几乎都是用伴随矩阵形式的线性化来完成的，但这只是许多可能的线性化中的一种。在最近的工作中，研究了三个线性化的向量空间，它们推广了伴生形式，并提供了一种系统的方法来生成一类广泛的线性化。这些空间使识别具有特定属性的线性化成为可能，例如最优条件，最优向后误差边界和结构的保留，例如对称性。我们最近的工作已经表明，这些新的线性化可以产生比伴生形式质量更好的数值解。本项目旨在开发新的线性化解PEP的算法，这些算法比目前使用的算法具有更高的精度和稳定性，并充分利用结构的对称性和确定性等特性。这项工作将涉及新理论的发展，包括新线性化空间的向后误差界限，新特征向量恢复公式的研究，以及双曲多项式及其确定线性化的研究。（双曲多项式是对称且具有实特征值的多项式的子集，它们在工程应用中很常见，包括在过阻尼机械系统中。）这项工作的一个重要产出将是可以作为库软件基础的算法，因为目前还没有解决PEP的标准库软件。

The polynomial eigenvalue problem (PEP) is to find the eigenvalues and eigenvectors of a square matrix whose elements are polynomials in a variable lambda, where an eigenvalue is a value of lambda for which the matrix is singular.Excellent numerical methods exist for the case where the polynomial degree is 1. Matrix polynomials of degree 2 or higher arise commonly in areas such as structural mechanics, acoustic systems and electrical circuit simulation. The trend to towards extreme designs (such as in micro-electromechanical (MEMS) devices and superjumbo jets) means that these eigenproblems are often poorly conditioned (hence difficult to solve accurately) while also having algebraic structure that should be exploited in a numerical method. As a specific example, in a project at TU Berlin modelling the sound and vibration levels in European high-speed trains it was found that standard finite element packages provided no correct figures in the computed solutions until linear algebra techniques of the type to be used in this proposal were brought into play in the underlying quadratic (degree 2) eigenvalue problem (see the cover article in SIAM News, Nov. 2004).The standard way of solving the PEP is by converting the problem to a degree 1 eigenvalue problem of larger dimension---the process of linearization. This is almost invariably done using a linearization having the well known companion matrix form, but this is just one of many possible linearizations. In very recent work three vector spaces of linearizations have been studied that generalize the companion form and which provide a systematic way of generating a wide class of linearizations. These spaces make it possible to identify linearizations having specific properties such as optimal conditioning, optimal backward error bounds and preservation of structure such as symmetry. Our recent work has already shown that these new linearizations can produce numerical solutions of significantly better quality than the companion form.This project aims to develop new algorithms for solving the PEP by linearization that have substantially better accuracy and stability properties than those currently used in practice, and which take full advantage of structural properties such as symmetry and definiteness. The work will involve the development of new theory, including backward error bounds for the new spaces of linearizations, the study of a new eigenvector recovery formula, and the study of hyperbolic polynomials and their definite linearizations. (The hyperbolic polynomials are a subset of those that are symmetric and have real eigenvalues, and they are common in engineering applications, including in overdamped mechanical sytems.) An important output of the work will be algorithms that can serve as the basis for library software, since at present there is no standard library software for solving the PEP.