Preconditioned Algorithms for Large Eigenvalue Problems

在许多应用领域，迫切需要新的数值技术来解决非常大的代数特征值问题。它们是由偏微分方程组描述的连续模型的离散化自然产生的，并提出了新的数值挑战。问题矩阵可能只能通过计算给定向量的相应向量-矩阵乘积的函数隐式地得到，因此需要无矩阵特征值求解器。随着问题规模的增长，往往会出现条件恶劣的问题，这就需要改进算法的稳定性和新的工具来估计计算出的特征值和特征向量的准确性。对于现代实际问题来说，经典的特征值解不随问题规模线性扩展是非常昂贵的。当前项目的重点是另一种技术，称为预处理。虽然该领域的主流研究通过使用预条件内迭代来求解具有移位和逆矩阵的线性系统来引入特征值问题的预条件，但本项目的方法是将预条件直接纳入基于krylovv的求解器，如局部最优块预条件共轭梯度法。这种预条件迭代法是专门为求解大规模无矩阵病态问题而设计的，具有有效的并行性。研究了奇异值计算的预条件、预条件特征解对谱参数非线性依赖问题的适应性，以及系数大跳变偏微分方程特征问题的有效解。研究者开发了快速、可靠的方法来解决非常大的特征值问题。在现代并行计算系统上进行了数值模拟，例如在Beowulf集群上。与工程师联合研究的目标应用包括与再入飞行器及其复杂的航空航天和电子系统相关的结构动力学有限元模型，以及化学-输运大气模型中卡尔曼滤波方程误差协方差的演变。

Knyazev 0208773 In many application areas, there is a pressing and increasing need for novel numerical techniques for solving very large algebraic eigenvalue problems. They arise naturally as discretization of continuous models described by systems of partial differential equations and pose new numerical challenges. The problem matrix may be available only implicitly through a function that computes the corresponding vector-matrix product for a given vector, which thus calls for matrix-free eigenvalue solvers. The growth of the problem size often leads to badly conditioned problems, which require improved algorithm stability and new tools to estimate the accuracy of computed eigenvalues and eigenvectors. Classical eigenvalue solvers that do not scale linearly with the problem size are very expensive for modern practical problems. The focus of the present project is on an alternative technique, called preconditioning. While the mainstream research in the area introduces preconditioning for eigenvalue problems by using preconditioned inner iterations for solving linear systems with shift-and-invert matrices, the approach of the present project is to incorporate preconditioning directly into Krylov-based solvers such as the locally optimal block preconditioned conjugate gradient method. The preconditioned iterative methods of this kind are specially designed for large-scale ill-conditioned matrix-free problems and can be effective and parallelizable. The investigator studies preconditioning for singular values computations, an adaptation of the preconditioned eigensolvers to some problems with nonlinear dependence on the spectral parameter, and an efficient solution of eigenproblems resuling from partial differential equations with large jumps in coefficients. The investigator develops fast, reliable methods to solve very large eigenvalue problems. Numerical simulations are performed on modern parallel computing systems, e.g., on a Beowulf cluster. The targeted applications for a joint investigation with engineers include structural dynamics finite element models associated with re-entry vehicles and their complex aerospace and electronic systems, and evolution of the error covariances in Kalman filter equations for chemistry-transport atmospheric models.