Over the last few decades, iterative methods, in particular Krylov subspace-based algorithms, have become widely-used and indispensable tools for the solution of large-scale computational problems in science and engineering. While most Krylov methods were originally developed for the solution of large eigenvalue problems or large systems of linear equations, starting in the early 1990s, Krylov techniques have also proven to be powerful tools for order reduction of large-scale systems of ordinary differential equations or algebraic-differential equations. The basic idea of order reduction is to replace the original large-scale system with a system of similar type, but of much smaller dimension. In recent years, a lot of Krylov machinery for order reduction has been put in place. Still, the existing algorithms are not at the same level as Krylov subspace methods for eigenvalue problems or systems of linear equations. For example, Krylov subspace methods combined with powerful preconditioning techniques are routinely used to solve linear systems with millions of unknowns. However, the application of Krylov techniques for order reduction to such truly large-scale systems remains prohibitive for a number of reasons. First, most existing algorithms generate reduced-order models via explicit projection after a suitable basis for the underlying Krylov subspace has been generated, and thus they require the storage of all these basis vectors. In the truly large-scale case, the resulting storage requirements become excessive. Second, Lanczos-type algorithms generate reduced-order models on the fly, and thus avoid the issue of keeping all basis vectors. However, in general, the resulting reduced-order models do not preserve crucial properties of the original large-scale system, such as stability or passivity. Third, all existing Krylov techniques involve the solution of large sparse linear systems of equations at each Krylov iteration. It is usually assumed that these systems can be solved via sparse direct methods. However, this is not the case in all applications. The goal of the proposed work is to develop new and effective Krylov subspace-based methods for order reduction that overcome the above issues and are thus applicable to truly large-scale systems. In particular, the focus will be on techniques that allow the use of preconditioned iterative methods for the solution of the inner linear systems, instead of sparse direct methods, and on methods that allow flexible shift-and-invert preconditioners for the outer Krylov iteration itself. The use of nonlinear semidefinite programming to remedy the loss of stability or passivity of reduced-order models generated by Lanczos-type algorithms will also be explored. The proposed research is expected to lead to a more complete understanding of Krylov subspace-based order reduction and to result in original algorithms that are on par with their state-of-the-art counterparts for large eigenvalue problems and large linear systems.
The use of computational techniques and numerical simulation is ubiquitous in the design and verification of today's complex engineering systems. For example, a state-of-the-art computer computer chip contains about one billion transistors. Despite this enormous complexity, the design and verification of such chips is done almost exclusively with simulation, and first-time-correct fabrication in silicon is the norm. However, even with today's computing power, simulation of a complete system is often not feasible due to the extremely high dimension of the mathematical model describing the system. Order reduction is a key technology to make such simulation tasks possible by first replacing the original model by a suitable approximation of much smaller dimension. The proposed research is expected to lead to new order-reduction techniques that will have applications in many important areas, including the design of computer chips, microelectromechanical systems, nanotechnology, and structural dynamics.
