By Kelvin Yuk

Abstract

As reduced order modeling of large scale systems by using Pade approximation has become an important part of improving the computation speed of circuit simulation, more methods are being explored. Pade approximation by moment matching (AWE) introduced by [2] illustrates the idea of reduced order modeling and provides accurate approximations of systems for order numbers less than 20. However newer Lanczos based methods have become more popular due to their smaller dependence on the expansion point and their robustness as the order number is increased. In this work, the AWE algorithm is implemented in Matlab and its dependence on the expansion point and model order is explored. Reduced order modeling by the AWE implemented here is then performed on several examples to exploit the order-dependent behavior. The results are compared to the Pade via Lanczos (PVL) implementation described in [1].

Overview of Pade approximation for reduced order modeling

A continuous time invariant linear dynamical system such as a passive RLC circuit network can be described in state-space form by

and then transformed into the frequency domain, the transfer function can be described by

The goal of reduced order modeling is to approximate the transfer function while preserving its essential characteristics.

If the system is computing about a selected expansion point s0 and it is assumed that the system is a single input single output system such that B=b and L=l, the transfer function can be concisely written as a function of a single matrix A and a vector r

where

and

In Pade approximation this transfer function can be approximated by its moments mj in the following manner

where mj are the moments about s₀ and are computed by

for j=0,1,2,….

Without going into the details, the AWE method seeks to directly compute the moments of the system required to solve for the coefficients of the reduced transfer function of the form

However, as described in [1,3], the direct computation of the moments in the AWE method about the expansion point s0 is a major limitation of the algorithm since powers of the matrix A are needed. In exact math, this dependency is non problematic, however, due to the limited precision of the computing platform, the Hankel matrix M_n formed by the moments m_j becomes ill-conditioned very quickly for even modest degrees of reduced ordering. During execution of AWE, ill conditioning can cause the reduced order model to diverge from as the order number is increased resulting in a limited accuracy and poor approximations of some systems.

However, it is easy to see since the powers of the matrix A are required, Krylov subspace techniques and Lanczos methods can be used to indirectly compute the moments of the system leading to a convergent behavior as the order number is increased. The Lanczos method described in [1] is used to compare with the AWE algorithm implemented here. Omitting the details, the reduced order transfer function computed by PVL is given by

where T_n is the triangularized A matrix up to the nth term obtained from the Lanczos proess and T’_n is the an (n-1) by (n-1) matrix obtained by deleting the first row and column of T_n [1]. The PVL implementation is taken from the simulation files accompanying the paper [1] at http://www.cs.ucdavis.edu/~bai/ROMmatlab/.

AWE Implementation

The AWE algorithm is implemented exactly as stated in [1]. The Hankel matris Mn is assembled based on the computed moments of the system and then used to solve for the set of denominator coefficients b by the system

with b₀=1. The numerator coefficients a are then solved for from the moments m and the coefficients b by the relationship:

These coefficients are stored into vectors and then used with the Matlab transfer function command tf() which generates a system object based on the provided coefficients. Since the implementation of the PVL provided by Bai computes the reduced order model in terms of the state-space matrices G,C,B and L, the Matlab-generated system is converted into state space form and then G, C, B and L are extracted from that model. The code for our AWE implementation is shown in Figure 1.

Simulation examples

In the following examples, we show that our implementation of the AWE algorithm is correct and how the AWE-obtained reduced order models are limited in terms of order, while the PVL approximation only continues to improve as the order is increased and is much more robust than AWE.

These examples are obtained from [1], [2] and [4] and are all frequency domain models of actual circuits. For each example, due to the sensitivity of the AWE method to the expansion point, extensive simulations were performed to select an expansion point at which the convergence behavior and then divergence behavior for increasing order can be seen. The same expansion point is used for the PVL simulation for comparison.

Although not illustrated here, if the expansion point is chosen incorrectly, it can lead to very poor results. One possible solution is to use multiple expansion points, but this incurs a large computation cost and still no guarantee of convergence. Since the PVL method is tolerant to the choice of s0, it is more suitable for a wide range of frequencies and more efficient in terms of computational time.

Simple RLC circuit example

This is a small RLC network presented in [2] on page 29. This example is used to verify the correctness of the AWE algorithm implemented here. The expansion point chosen here is s0=2p * 10⁷ rad/s.

The magnitude and phase plots of the simple RLC example are shown in Figure 2. From the figure, we see that the magnitude of the reduced model converges quite nicely as the order is increased to 4,5 and 6. At n=6, the magnitude and phase are very close to the exact solution and the plots overlap. However when the order is increased to 7, the model diverges away from the exact solution at frequencies greater than the expansion frequency. This shows the ill-condition sensitivity to the order and the expansion point.

The same example is simulated using the PVL implementation and the results are shown in Figure 3. The PVL models converge very well, just like the AWE algorithm for n=4, 5, and 6. However, unlike the AWE models, at n=7, the PVL-obtained models continue to maintain convergence towards the exact solution. One reason why this is important is that it allows us to detect for the convergence of the reduced order model at the same time of achieving a high level of accuracy.

Clock distribution system of an integrated circuit

Interconnect modeling is an important part of integrated circuit design as feature size and performance are being pushed to the limits. As a result, the delay and attenuation effects of simple metal lines cannot be ignored and doing so will lead to poor circuit performance. In this example, a clock distribution network is modeled as transmission lines consisting of RLC lumped elements. This example is taken from [4]. In this example, the ill conditioned behavior of the AWE algorithm is again illustrated and then compared to the PVL algorithm. The expansion point used here is s0=2p * 10⁷ rad/s.

The magnitude and phase plots of the AWE obtained reduced order models are shown in Figure 4 compared with the exact model. At n=4, the approximation is not very good, however, at n=6, both the magnitude and the phase are very close to the exact solution. When the order is increased beyond 6, the models starts to become ill conditioned and cannot maintain convergence about the exact solution. At n=6, the magnitude and phase approximation is poor beyond 2e10 rad/s. At n=11, the results get even worse and the approximation appears to be good only up to 6e9 rad/s.

Figure 5 shows the PVL at the same orders as simulated by the AWE algorithm. At n=4 and n=6, the magnitude and phase responses resemble that obtained by the AWE algorithm. However, unlike the AWE case, the PVL-obtained models continue to converge towards the exact solution even at n=9 and n=11. Again, this example shows how the PVL algorithm is superior to that of the AWE algorithm in terms of convergence behavior and avoids limitations due to ill conditioning of matrix A.

Partial element equivalent circuit (PEEC)

The PEEC example (PEEC) models a lumped element network generated by a 3-D electromagnetic problem and is a popular example used in [1,3]. In the PEEC simulation in [1], the order number used to obtain a very close approximation to the exact system by PVL is n=60. However, the standard AWE algorithm implemented here cannot even get close to that order due to the ill-conditioned Hankel matrix. Rather, through numerous solutions, we found that our implementation can only compute up to n=15 on our platform. But even at n=10, the matrix M becomes very ill conditioned and the results become useless which will be illustrated here.

Here, because the order is limited for the AWE method and we will not be able to obtain good models for the circuit, we will instead of compare its behavior against that of the PVL method as the order is increased to 10. This way, we can see how the AWE model converges versus the PVL model, which we know will converge very well at n=60. The expansion point chosen here is s0=2p * 1e8.

The next sequence of figures 6 through 9 shows the magnitude and phase behavior of the AWE-obtained and PVL-obtained models of order n=3, 5, 9 and 10. In Figure 6, n=3 and although neither model describes the exact model well, the AWE and PVL obtained models are close especially the phase. The models shown there only approximate the gain in the first “hump” of the PEEC filter. The second pass region at around 2.25e10 rad/s does not seem to be included into the reduced order model at all. In Figure 7 at n=5 ,both AWE and PVL, the approximation improves in that both methods begin to account for the higher frequency pass region. Note that both methods, although slightly different, are still very well matched in both magnitude and phase. In Figure 8, at n=9, the approximated hump of the AWE and PVL methods moves farther out towards the exact solution. Again, the phase agreement between the two models is excellent and the magnitude response is comparable. However, in Figure 9, at just one order higher than the previous plot, the Hankel matrix becomes ill conditioned and has lost convergence from the exact solution. It continues to stray as the order is increased while the PVL approximation only gets better.

This example shows the limitation of the AWE method, that it may not even be able to give a decent approximation of the system due to the limited order range.

Conclusion

Here we have implement the AWE algorithm in Matlab for the purpose of comparing it to the PVL implementation provided by Bai and to exploit the weaknesses of the direct computation compared to the Krylov subspace Lanzcos-based techniques. We have shown that the Lanczos based method is more robust and avoids the limit of computational precision.

To show exemplify the sensitivity to the expansion point and the limitation of the order due to ill-conditioning, several examples based on real circuits has been performed. The AWE algorithm is extremely limited by the machine precision and not an effective method for the modeling of high order systems. The AWE may obtain decent results by using various expansion points, but this may not be feasible due to the cost of computing the matrix A. One possible way to minimize the cost of multi-expansion point methods is to observe the range of accuracy about a single expansion point and configure the stepsize between expansion points accordingly. The accurate results about each expansion point can then be combined to form a more exact reduced-order model. If time permitted further investigation in the time domain could be explored as well.

The goal of the algorithm is to reduce the order of the model to a lower ordered model that still can accurately represent the characteristics of the exact model. To define this model reduces the required analysis in the frequency domain of the time domain. One goal in implementing reduced order modeling may be to set a stopping criteria to determine the sufficient model order number needed to accurately describe the exact system. In PVL, because it always converges as the model number is increased regardless of the expansion point, a residual test for convergence could be used for the stopping criteria. However, because the reduced order approximation from AWE may eventually diverge from a close approximation of the exact system due to the ill-conditioning of the Hankel matrix as n is increased, it may be difficult to detect when exactly a good approximation has been achieved.

References

[1] Z. Bai, Krylov subspace techniques for reduced-order modeling of large-scale dynamical systems, Applied Numerical Mathematics 43 (2002) 9-44

[2] E. Chiprout, M.S. Nakhla, Asymptotic Waveform Evaluation, Kluwer Academic, Dordrecht, 1994

[3] P. Feldman, R.W. Freund, Efficient Linear Circuit Analysis by Pade Approximation via Lanczos Process, IEEE Trans. Computer Aided Design, CAD 14 (1995) 639-649.

[4] P. Triverio (triverio@tin.it), Electronic engineer, Politecnico di Torina, Italy, via Tomati 41/A, 13811 Tavigliano (BI), Italy