Numerical Algorithms for the Polynomial Eigenvalue Problem

多项式特征值问题(PEP)是求一个方阵的特征值和特征向量，方阵的元素是变量λ中的多项式，其中特征值是矩阵的奇异值。对于多项式次数为1的情况，已有很好的数值方法。2次以上的矩阵多项式在结构力学、声学系统和电路仿真等领域中普遍存在。倾向于极端设计的趋势(如在微电子机械(MEMS)设备和超大型喷气式飞机中)意味着这些特征问题通常条件很差(因此很难精确求解)，同时也具有应该在数值方法中利用的代数结构。作为一个具体的例子，在柏林工业大学的一个项目中，对欧洲高速列车的声级和振动级进行建模，发现标准的有限元程序包在计算解中没有提供正确的数字，直到本建议中使用的类型的线性代数技术在基本的二次(2次)本征值问题中发挥作用(参见SIAM新闻，2004年11月的封面文章)。解决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.