Krylov Subspace-Based Model Order Reduction
              of Large-Scale RCL Networks

                   Roland W. Freund
               Department of Mathematics
            University of California, Davis
                  One Shields Avenue
                 Davis, CA 95616, USA

          web:  http://www.math.ucdavis.edu/~freund/

In recent years, order-reduction techniques based on Krylov 
subspaces have become the methods of choice for generating
macromodels of large-scale multi-port RLC networks that 
arise in VLSI circuit simulation.   Early algorithms of 
this type, such as MPVL and its variants, are based on the 
nonsymmetric Lanczos process and were proposed to remedy 
the numerical shortcomings of the celebrated asymptotic 
waveform evaluation (AWE) method.  Lanczos-based order-reduction 
techniques methods, however, in general do not preserve other 
important properties, such as stability and passivity, of 
the original RLC networks.  This has led to the development 
of Krylov subspace-based projection methods, such as PRIMA, 
that preserve stability and passivity of the original RLC 
networks at the expense of significantly lower approximation 
accuracy.  By exploiting the RCL-specific block structure of 
the standard modified-nodal formulation of the large-scale 
RCL network, it is possible to devise a Krylov subspace-based
projection method that preserves passivity, reciprocity, and 
the RCL-specific block structure and at the same time has
significantly higher approximation accuracy than PRIMA.
The resulting SPRIM algorithm represents the current 
state-of-the-art of Krylov subspace-based order reduction
of large-scale RLC networks.

In this talk, we first describe the problem of order reduction
of RCL networks and how it arises in VLSI circuit simulation. 
We then present an overview of Krylov subspace-based reduction
techniques from MVPL to PRIMA and SPRIM.  In particular, we
describe recent variants of SPRIM that exploit certain rank 
deficiencies in the Krylov subblocks used in the projection 
approach to further reduce the size of the SPRIM models. 
Finally, we discuss some recent progress on the problem of 
constructing structure-preserving Krylov subspace-based 
reduced-order models that have optimal approximation accuracy.