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

点击翻译按钮获取中文摘要

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.