Numerical solutions of matrix equations arising in model reduction of large-scale linear -time -invariant systems
Nong, Hung Dinh
Sorensen, Danny C.
Doctor of Philosophy
This thesis presents and analyzes new algorithms for matrix equations arising from model reduction of linear-time-invariant (LTI) systems. Such systems arise in a variety of areas, especially in circuit simulation. When an integrated circuit has millions of devices, performing a full-system simulation can be infeasible due to the time required for the nonlinear solver to compute the solution of large linearized systems. Model reduction becomes indispensable since model reduction techniques aim to produce low-dimensional systems that capture the same response characteristics as the originals while enabling substantial improvement in simulation time and resulting in greatly reduced storage requirements. One of the crucial physical features of LTI systems in circuit simulation is passivity, which is essential to preserve during model reduction. Passivity preserving model reduction using the invariant subspace method in conjunction with positive real balancing for LTI systems provides an error bound and involves the solution of two Riccati equations. The contributions of this thesis are fourfold. First, a generalization of the invariant subspace method for passivity preserving model reduction is presented for LTI systems in descriptor form. Second, two iterative algorithms to compute the solution of the two algebraic Riccati equations are derived. Even though these two iterative algorithms have been in existence, the thesis introduces them here in addition with specific conditions on LTI systems for their convergence. At each step of either iteration, a pair of Lyapunov equations result. The thesis next investigates a parameter free ADI-like (PFADI) method for the solution of the Lyapunov equation. This PFADI method involves the solution of the Sylvester equation at each step, and its computational complexity depends on how efficiently the solution of the Sylvester equation is obtained. The final part of the thesis is devoted to the study of two techniques to solve the Sylvester equation. The first technique is to obtain the solution of the Sylvester equation via that of an invariant subspace problem. The thesis presents a complete analysis and an efficient algorithm to compute the optimal real shift for the Cayley transformation used in the invariant subspace technique. The analysis is then generalized for multiple optimal real shift selection for the ADI technique for the solution of the Sylvester equation.