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

真正大规模系统降阶迭代方法的设计与分析

• 批准号: 0613032
• 负责人: Roland Freund
• 金额: $ 30.81万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-08-15 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0613032&HistoricalAwards=false
• 关键词: Design; Analysis; Iterative; Methods; Order

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.

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