Design and Analysis of Iterative Methods for Order Reduction of Truly Large-Scale Systems

在过去的几十年里，迭代方法，特别是基于Krylov子空间的算法，已经成为解决科学和工程中大规模计算问题不可缺少的广泛使用的工具。虽然大多数Krylov方法最初是为了解决大型特征值问题或大型线性方程组，始于20世纪90年代初，但Krylov方法也被证明是用于大型常微分方程组或代数微分方程组降阶的强大工具。降阶的基本思想是用一个相似类型的系统来代替原来的大系统，但降阶的规模要小得多。近年来，克利洛夫推出了大量的减单机制。尽管如此，现有的算法并不像求解特征值问题或线性方程组的Krylov子空间方法那样处于同一水平。例如，Krylov子空间方法与强大的预条件技术相结合，通常用于求解具有数百万个未知数的线性系统。然而，由于许多原因，克雷洛夫降阶技术在这种真正大规模的系统中的应用仍然令人望而却步。首先，现有的大多数算法是在为底层的Krylov子空间生成合适的基后，通过显式投影来生成降阶模型，因此需要存储所有这些基向量。在真正大规模的情况下，由此产生的存储需求会变得过大。第二，Lanczos类算法动态地生成降阶模型，从而避免了保留所有基向量的问题；但是，所得到的降阶模型通常不保持原始大系统的关键性质，如稳定性或被动性；第三，所有现有的Krylov技术都涉及在每次Krylov迭代中求解大型稀疏线性方程组。通常认为这些系统可以用稀疏直接法来求解。然而，并不是所有的应用程序都是这样。这项工作的目标是发展新的和有效的基于Krylov子空间的降阶方法，以克服上述问题，从而适用于真正的大规模系统。特别是，重点将集中在允许使用预条件迭代方法来求解内部线性系统的技术，而不是稀疏直接方法，以及允许灵活的移位和逆预条件算子用于外部Krylov迭代本身的方法。还将探讨利用非线性半定规划来弥补由Lanczos类算法产生的降阶模型的稳定性或无源性的损失。这项研究有望使我们对基于Krylov子空间的降阶方法有更全面的理解，并产生与大型特征值问题和大型线性系统的同类算法相当的原始算法。在当今复杂工程系统的设计和验证中，计算技术和数值模拟的使用是普遍存在的。例如，一个最先进的计算机芯片包含大约10亿个晶体管。尽管有如此巨大的复杂性，这种芯片的设计和验证几乎完全是通过模拟完成的，第一次正确的硅片制造是标准。然而，即使在今天的计算能力下，由于描述系统的数学模型的维度非常高，对完整系统的仿真往往是不可行的，降阶是实现这类仿真任务的关键技术，首先用一个合适的小得多的近似模型来代替原始模型。这项拟议的研究有望带来新的降阶技术，这些技术将在许多重要领域得到应用，包括计算机芯片设计、微电子机械系统、纳米技术和结构动力学。

Over the last few decades, iterative methods, in particular Krylov subspace-based algorithms, have become widely-used and indispensable tools forthe solution of large-scale computational problems in science and engineering.While most Krylov methods were originally developed for the solution of largeeigenvalue problems or large systems of linear equations, starting in the early1990s, Krylov techniques have also proven to be powerful tools for order reduction of large-scale systems of ordinary differential equations oralgebraic-differential equations. The basic idea of order reduction is toreplace the original large-scale system with a system of similar type, but ofmuch smaller dimension. In recent years, a lot of Krylov machinery for orderreduction has been put in place. Still, the existing algorithms are not at thesame level as Krylov subspace methods for eigenvalue problems or systems oflinear equations. For example, Krylov subspace methods combined with powerfulpreconditioning techniques are routinely used to solve linear systems withmillions of unknowns. However, the application of Krylov techniques for orderreduction to such truly large-scale systems remains prohibitive for a number ofreasons. First, most existing algorithms generate reduced-order models viaexplicit projection after a suitable basis for the underlying Krylov subspacehas been generated, and thus they require the storage of all these basis vectors. In the truly large-scale case, the resulting storage requirementsbecome excessive. Second, Lanczos-type algorithms generate reduced-ordermodels on the fly, and thus avoid the issue of keeping all basis vectors.However, in general, the resulting reduced-order models do not preserve crucialproperties of the original large-scale system, such as stability or passivity.Third, all existing Krylov techniques involve the solution of large sparselinear systems of equations at each Krylov iteration. It is usually assumedthat these systems can be solved via sparse direct methods. However, this isnot the case in all applications. The goal of the proposed work is to developnew and effective Krylov subspace-based methods for order reduction thatovercome the above issues and are thus applicable to truly large-scale systems.In particular, the focus will be on techniques that allow the use ofpreconditioned iterative methods for the solution of the inner linear systems,instead of sparse direct methods, and on methods that allow flexibleshift-and-invert preconditioners for the outer Krylov iteration itself. Theuse of nonlinear semidefinite programming to remedy the loss of stability orpassivity of reduced-order models generated by Lanczos-type algorithms willalso be explored. The proposed research is expected to lead to a more completeunderstanding of Krylov subspace-based order reduction and to result inoriginal algorithms that are on par with their state-of-the-art counterpartsfor large eigenvalue problems and large linear systems.The use of computational techniques and numerical simulation is ubiquitous inthe design and verification of today's complex engineering systems. Forexample, a state-of-the-art computer computer chip contains about one billiontransistors. Despite this enormous complexity, the design and verification ofsuch chips is done almost exclusively with simulation, and first-time-correctfabrication in silicon is the norm. However, even with today's computingpower, simulation of a complete system is often not feasible due to theextremely high dimension of the mathematical model describing the system.Order reduction is a key technology to make such simulation tasks possible byfirst replacing the original model by a suitable approximation of much smallerdimension. The proposed research is expected to lead to new order-reductiontechniques that will have applications in many important areas, including thedesign of computer chips, microelectromechanical systems, nanotechnology, andstructural dynamics.