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

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

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.