A fast Newton/Smith algorithm for solving algebraic Riccati equations and its application in model order reduction

Abstract

A very fast Smith-method-based Newton algorithm is introduced for the solution of large-scale continuous-time algebraic Riccati equations (CAREs). When the CARE contains low-rank matrices, as is common in the modeling of physical systems, the proposed algorithm, called the Newton/Smith CARE or NSCARE algorithm, offers significant computational savings over conventional CARE solvers. Effectiveness of the algorithm is demonstrated in the context of VLSI model order reduction wherein stochastic balanced truncation (SBT) is used to reduce large-scale passive circuits. It is shown that the NSCARE algorithm exhibits guaranteed quadratic convergence under mild assumptions. Moreover, two large-sized matrix factorizations and one large-scale singular value decomposition (SVD) necessary for SBT can be omitted by utilizing the Smith method output in each Newton iteration, thereby significantly speeding up the model reduction process.