A Fast Newton/Smith Algorithm for Solving Algebraic Riccati Equations
and its Application in Model Order Reduction
A Fast Newton/Smith Algorithm for Solving Algebraic Riccati Equations
and its Application in Model Order Reduction
N. Wong, V. Balakrishnan, C.-K. Koh, and T.-S. Ng
In Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing,
Montreal, Canada, May 2004
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 \textit{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.
Download Postscript
PDF
Bibtex entry