Preconditioned Algorithms for Large Eigenvalue Problems

Knyazev 0208773在许多应用领域，迫切需要新的数值技术来解决非常大的代数特征值问题。它们是由偏微分方程组描述的连续模型的离散化而自然产生的，并提出了新的数值挑战。问题矩阵可能只能通过计算给定向量的相应向量-矩阵乘积的函数来隐式获得，因此需要无矩阵的特征值求解器。问题规模的增长往往导致条件恶劣的问题，这就需要改进的算法稳定性和新的工具来估计计算的特征值和特征向量的精度。对于现代实际问题来说，不随问题大小线性扩展的经典特征值求解器是非常昂贵的。本项目的重点是一种可替代的技术，称为预适应。虽然该领域的主流研究引入了特征值问题的预条件，通过使用预条件内迭代来求解具有移位和逆矩阵的线性方程组，但本项目的方法是将预条件直接结合到基于Krylov的求解器中，例如局部最优块预条件共轭梯度法。这种预条件迭代法是专门针对大规模病态无矩阵问题而设计的，具有高效和可并行化的特点。研究了奇异值计算的预条件，预条件本征解对谱参数的非线性依赖，以及系数大跳跃偏微分方程本征解的有效解。研究人员开发了快速、可靠的方法来解决非常大的特征值问题。在现代并行计算系统上，例如在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.