Multi-point model reductions of VLSI interconnects using the rational Arnoldi method with adaptive orders

1. Field of the Invention

The present invention relates to multi-point model reductions of VSLI interconnects, and more particularly to multi-point model reductions of VLSI interconnects using rational arnoldi method with adaptive orders (RAMAO).

2. Description of Related Art

Interconnect plays a significant role in the recent development of high-speed VLSI design. Due to the continuous increasing in component densities and clock rates, the signal integrity problems naturally arise in the interconnect structure. For efficient simulations, it is necessary to construct a low-order macro-model whose terminal behaviors essentially capture the complicated interactions among the interconnects. The process of finding such a reduced network is referred to as model reduction [References 4, 6, 13-15 and 18].

Recently, several methods that are based on Pade synthesis have been applied to improve the model-order reduction techniques. Asymptotic waveform evaluation (AWE) [References 3 and 15], Pade via Lanczos (PVL) [Reference 6 and 7], and congruence transformations (CT) [Reference 13] have successfully been used to analyze interconnect systems. Among all existing methods, it has been shown that the class of Krylov-space methods seems to be more accurate, because it can avoid the ill-conditional problems. However, these conventional approximation methods tend to converge in a local fashion around a single frequency, because Pade approximation is exact at the point while accuracy is lost away from it. So the reduced-order model may grow large before becoming an acceptable global approximation. To overcome this difficulty, multi-point Pade has been proposed [References 2, 5, 12 and 18].

The straightforward way for multi-point moment matching applications is to apply the Krylov subspace algorithm at various expansion frequencies. This is the so-called rational Krylov algorithm [references 1, 9 and 16]. The present invention uses the RAMAO to simplify the conventional algorithm without determining the order of moments at each expansion frequency in advance. The concept was first developed in the rational Lanczos method [reference 8]. In this work, the exact error between the output moment of the original system and that of the reduced-order system, associated with each expansion point, can be determined explicitly. In each iteration of the proposed method, the expansion frequency corresponding to the maximum output moment error is chosen. Consequently, the corresponding reduced-order model will yield the greatest improvement in output moments among all reduced-order models of the same order.

The main objective of the present invention is to provide improved multi-point model reductions of VLSI interconnects using rational Arnoldi method with adaptive orders.

To achieve the objective, the present invention proposes a model reduction method, the rational Arnoldi method with adaptive orders (RAMAO), to be applied to high-speed VLSI interconnect models. It is based on an extension of the classical multi-point Pade approximation, using the rational Arnoldi iteration approach. Given a set of predetermined expansion points, an exact expression for the error between the output moment of the original system and that of the reduced-order system, related to each expansion point, is derived first. In each iteration of the proposed RAMAO algorithm, the expansion frequency corresponding to the maximum output moment error will be chosen. Hence, the corresponding reduced-order model yields the greatest improvement in output moments among all reduced-order models of the same order.

Further benefits and advantages of the present invention will become apparent after a careful reading of the detailed description with appropriate reference to the accompanying drawings.

FIG. 1 is a mesh circuit;

FIG. 2 shows frequency responses of the voltage at Vout in the mesh circuit in FIG. 1 ;

FIG. 3 shows the RAMAO lemniscates at iterations 2 , 4 , 18 and 20 ;

FIG. 4 shows the imaginary part of Rtiz values; and

FIG. 5 shows errors in frequency responses of the current leaving from the voltage source in the mesh circuit.

Circuit Equation and Moment

In analyzing an RLC circuit, the modified nodal analysis (MNA) can be applied as follows [References 13 and 18].

E ⁢ ⅆ x ⁡ ( t ) ⅆ t = Ax ⁡ ( t ) + bu ⁡ ( t ) , and ⁢ ⁢ y ⁡ ( t ) = c T ⁢ x ⁡ ( t ) , ( 1 )

where state vector x(t)εR n includes node voltages and branch currents of inductors; u(t)εR is the input excitation, and y(t)εR is the output. The descriptor matrix EεR n×n contain capacitances and inductances; the system matrix AεR n×n contain conductances and resistances; the input vector is bεR n , and the output incidence vector is cεR n . The above system is large-scale, sparse, and stable. The model order reduction problem is to find a q-order system (2), q<<n,

E ^ ⁢ ⅆ x ^ ⁡ ( t ) ⅆ t = A ^ ⁢ x ^ ⁡ ( t ) + b ^ ⁢ u ⁡ ( t ) , y ^ ⁡ ( t ) = c ^ T ⁢ x ^ ⁡ ( t ) , ( 2 )

where Ê,ÂεC q×q , {circumflex over (x)},{circumflex over (b)},ĉεC q , and ŷεC. The reduced-order system is expected to capture the essential dynamic behaviors of the original system and to reduce the computational cost during the whole simulation process.

Suppose that u(t) is an impulse function. Taking the Laplace transform yields the transfer function of the original system as y(s)=c T X(S)=c T (sE−A) −1 b. Expanding X(s) in power series about various frequencies s i εC for i=1,2 . . . ,î,

X ⁡ ( s ) = ∑ j = 0 ∞ ⁢ X ( j ) ⁡ ( s i ) ⁢ ( s - s i ) j ,

where X (j) (s i )=[−(s i E−A) −1 E] j (s i E−A) −1 b and Y (j) (s i )=c T X (j) (s i ). X (j) (s i ) is called the jth-order system moment of X(s); and Y (j) (s i ) represents the jth-order output moment of Y(s) at s i .

Krylov Subspace

One efficient way of obtaining a reduced-order system is to use the multi-point Pade approximation (or multi-point moment matching) [Reference 2]. The multi-point Pade approximation requires that the output moment of the original system equals that of the reduced system, Y (j) (s i )=Ŷ (j) (s i ),j=0,1, . . ,ĵ i , i=1,2, . . . î. Notably, if î=1, the above equation is indeed the conventional Pade approximation. However, this method usually yields an ill-conditioned problem [Reference 6]. Recent works have proposed Krylov subspace projection methods to avoid such numerical difficulties [References 4, 6, 13 and 18]. The reduced-order system is constructed by projecting an original large-dimensional problem into a low-dimensional Krylov subspace.

Given a square matrix ΨεC n×n and a vector ξεC n , the qth Krylov sequence K q (Ψ,ξ)≡(ξ,Ψξ,Ψ 2 ξ, . . . Ψ q−1 ξ) is a sequence of q column vector and the corresponding column space is called the qth Krylov space [Reference 1]. The Arnoldi algorithm can be applied to iteratively generate an orthonormal basis V q εC n×q from the successive Krylov subspace K q (Ψ,ξ)=span{ν 1 ,ν 2 , . . . ,ν q }, where ν i εV q ,i=1, . . . ,q. Set Ψ=−(s i E−A) −1 E and ξ=(s i E−A) −1 b. The Kyrlov subspace K q {Ψ,ξ} is indeed spanned by the system moments X (j) (s i ) for j=0,1 . . . q−1. The reduced-order Ŷ(s) can be constructed using the orthogonal projection x(t)=V q {circumflex over (x)}(t). In such a situation, the reduced system parameters in Eq. (2) can be defined by the congruence transformation [Reference 13 and 18],

Ê=V q T EV q , Â=V q T AV q , {circumflex over (b)}=V q T b, and ĉ=V q T c   (3)

The number of moments in the reduced system is exactly the number of moments in the original system at an expansion frequency s i , up to the order of q, that is, Y (j) (s i )=Ŷ(s i ), for j=0,1, . . . ,q−1.

Adjoint Network Reduction

Suppose that c=b. The signature matrix S is defined as S=[I nv 0;0−I ni ] so that S −1 =S,SES=E,SAS=A T , and Sb=b[11,18]. Suppose that X (j) (s i )εcolspan{V q } for j=0,1 . . . ,ĵ−1 and i=1,2, . . . ,î. V q is the orthonormal matrix generated iteratively by the AORA algorithm. Assuming U=[V SV q ] is the congruence transformation matrix for model-order reductions, then

Ŷ (j) ( s i )= Y (j) ( s i ), for j= 0,1, . . . ,2 ĵ− 1 and i= 1,2, . . . , î   (4)

Therefore, the cost about constructing the congruence transformation matrix can be simplified up to 50% of the previous methods.

A rational Arnoldi method, which uses multiple expansion points, was developed to implement the multi-point Pade approximation. To simplify the developments, the number of the matched moments of the reduced-order system at each expansion point are assumed to be fixed. Formally, assume S=(s 1 ,s 2 , . . . s i } represent the set of predetermined expansion frequencies. Assume j=(ĵ 1 ,ĵ 2 , . . . ĵ i } is the set of the number of the matched moments at each corresponding frequency. The rational Arnoldi method will generate a reduced-order system transfer function Ŷ(s) which matches q-order

( q = ∑ i = 1 i ^ ⁢ j ^ 1 )

moments of the original system transfer function, Y(s), at the expansion points s i ,i=1, . . . ,î.

Implementing the rational Arnoldi method is equivalent to implementing the Arnoldi method ĵ, times at î expansion frequencies. That is, the first ĵ 1 iterations correspond to the expansion frequency s 1 ; the next ĵ 2 iterations are associated with s 2 , and so on. Each Arnoldi iteration generates ĵ i orthonormal vectors. Then, V q =[ν 1 ,ν 2 , . . . ,ν q ] is the desired orthonormal matrix generated from a union Krylov space at various expansion points, as stated by

K q = [ X ( 0 ) ⁡ ( s 1 ) , … ⁢ , X ( j ^ 1 - 1 ) ⁡ ( s 1 ) , … ⁢ , X ( 0 ) ⁡ ( s i ^ ) , … ⁢ , X ( j ^ 1 ^ - 1 ) ⁡ ( s i ^ ) ] .

Table 1 refers to the algorithm of the rational Arnoldi method.

Special attention should be paid to any change of the expansion point. Step (Krylov Subspace) gives relevant details. If the expansion points remains unchanged, j=ĵ i and i≦î, then the residue vector r k is the same as that used in the Arnoldi method. However, if the expansion point is changed, then, the residue vector r k can be reset to (s i+1 E−A) −1 b, which is equal to the system moment X (0) (s i+1 ) for the subsequent expansion frequency s i+1 . Hence, this expression intuitively captures the concept of moments. Moreover, the errors between the output moments of the original model and those of the reduced-order model can be exactly and efficiently calculated from the residue vectors, stated in Theorem 2 in detail. Accordingly, the specific choice of the residue vector in Step (2.2) plays a crucial role in developing the proposed RAMAO method. Given the settings specified in Step (2.2), the new orthonormal vector v k and the orthonormal matrix V k−1 generated in earlier iterations can indeed span the entire Krylov subspace. Once the orthonormal matrix V q has been formed by applying the rational Arnoldi method, the reduced-order system can be obtained using the congruence transformation. The following Theorem 1 indicates that the output moments can be matched.

THEOREM 1. [Reference 10] Assume that V q is the orthonormal matrix generated by the rational Arnoldi algorithm with q iterations. Since X (j) (s i ) εcolspan{V q } for j=0,1, . . . ,ĵ i and i=1,2, . . . î,

X (j) ( s i )= V q {circumflex over (X)} (j) ( s i ) and Y (j) ( s i )= Ŷ (j) ( s i )  (5)

The Ramao Method

As stated in the last section, selecting a set of expansion points s i for i=1, . . . ,î and the number of matched moments ĵ i about each s i is not trivial. For simplicity, the expansion points s i for i=1, . . . ,î are determined in advance using engineering heuristics or experimental measurements over a specified frequency range. This section describes an intelligent scheme for choosing multiple expansion points in each iteration.

Assume that Y (j) (s i )=Ŷ (j) (s i ) for j=1,2, . . . ,ĵ i and i=1,2, . . . ,î after q iterations of the rational Arnoldi algorithm. However, the (j+1)st-order output moments Y (j+1) (s i )=Ŷ (j+1) (s i ) can be guaranteed. The concept that underlines the RAMAO method is employed to select an expansion point s i* q+1 in the (q+1) st iteration. Hence, the resulting (q+1)st-order reduced model yields the greatest moment improvement |Y (j+1) (s i* q+1 )−Ŷ (j+1) (s i* q+1 )| of the qth-order reduced-order model. The moment errors can be directly obtained in the new iteration without explicitly calculating system moments. Table 2 shows the algorithm of the RAMAO method. The vector S includes î expansion points; q is the total number of iterations, and V q is the resulting orthonormal matrix. The main difference between the rational Arnoldi method and the RAMAO method is in Step (2.1).

Algorithm 2: RAMAO (input: E, A, b, c, S, q; output: V q ) (1): /* Initialize */ for each s i ε S do k (0) (s i ) := (s i E − A) −1 b, r (0) (s i ) := k (0) (s i ) h π (s i ) := 1 end for (2): /* Begin RAMAO Iterations */ for j = 1, 2, . . . , q do (2.1): /* Select the Expansion Frequency with the Maximum Output Moment Error*/ Choose s i ε S as the i giving max i (|h π (s i )c T r (j−1) (s i )|) Set s i j * be the expansion frequency in the jth iteration (2.2): /* Generate the Orthonormal Vector at s ij * */ h j,j−1 (s i j *) := ∥r (j−1) (s i j *)∥ v j = r (j−1) (s i j *)/h j,j−1 (s i j *) h π (s i j *) := h π (s i j *) · h j,j−1 (s i j *) (2.3): /* Update r (j) (s i ) for the Next Iteration */ for each s i ε S do if (s i == s i j *) then k (j) (s i j *) := −(s i E − A) −1 Ev j else k (j) (s i ) := k (j−1) (s i ) end if r (j) (s i ) := k (j) (s i ) for t = 1, 2, . . . , j do h t,j (s i ) := v t H r (j) (s i ) r (j) (s i ) := r (j) (s i ) − h t,j (s i )v t end for end for end for V q = [v 1 v 2 . . . v q ] (3): /* Yield Real V q for Complex Expansion Points */ if there exists any s i ε S such that s i is not real then V r := real(V q ), V i := imag(V q ) [V q , rr] = qr([V r V i ]) end if

The RAMAO method comprises the following steps. Step (1): Initialize the first vector k (0) (s i )=(s i E−A) −1 b of the Krylov sequence for each expansion points s i , where iε{1, . . . î}. Since the reduced-order model and the orthonormal matrix are not yet determined, the residue r (0) (s i ) for each s i is set to k (0) (s i ). The normalization coefficient about each s i , h π (s i ), is initialized to be one.

Step (2.1): Choose an expansion frequency s i such that s i gives the greatest difference between the (j+1)st-order output moment of the original system Y(s) and that of the reduced-order system Ŷ(s), that is, max s i εS |Y (j+1) (s i )−Ŷ (j+1) (s i )|=max s i εS |h π (s i )c T r (j−1) (s i ). Ŷ (j+1) (s i ) is the (j+1)st-order output moment of the reduced-order model Ŷ(s), which if yielded using the congruence transformation matrix V j−1 (j >1) and matches j-order output moments of Y(s) at s i . The chosen expansion frequency in the jth iteration is called s i* j .

Step (2.2): After the chosen expansion point s i* j in jth iteration has been determined, the single-point Arnoldi method is applied at the expansion point s i* j . The new orthonormal vector ν j is incorporated into the orthonormal matrix V j−1 . The normalization coefficient h π (s i )=Π j ∥r (j−1) (s i )∥ if s i is selected in the jth iteration.

Step (2.3): Determine the new residual r (j) (s i ) at each expansion point s i . The calculation involves a projection with the new orthonormal matrix V j . The next vector k (j) (s i* j ) at the frequency s i* j must be updated to enable further matching of the output moment in the (j+1)st iteration. Since no improvement is obtained at the other unselected frequency s i , the vector k (j) (s i ) at frequency s i in the current iteration remains k (j−1) (s i ), which was obtained in the preceding iteration.

Step (3): Generate the real orthogonal matrix V q by using the reduced QR factorization if there exists any complex expansion points.

The following theorem presents an exact formula for the output moment errors used in Step (2.1).

THEOREM 2. [Reference 10] Suppose that the output moments of the original system and those of the reduced-order system are matched, that is, Y (j) (s i )=Ŷ (j) (s i ) for i=0,1, . . . ,ĵ i −1 and i=1,2, . . . ,î. The system matrices of reduced-order system are generated by the congruence transformation with the othonormal matrix V q using the RAMAO algorithm, where q=Σ i=1 î ĵ i . The magnitude error between the ĵ i th-order moments Y (ĵ i ) (s i ) and Ŷ (ĵ i ) (s i ) at each expansion point s i can be expressed as follows:

|Y (ĵ i ) ( s i )− Ŷ (ĵ i ) ( s i )|=| h π ( s i ) c T r (ĵ i −1) ( s i )|,  (6)

where h π (s i )=Π j ∥r (j−1) (s i )∥. Moment matching can still be preserved by following the similar proof of Theorem 1.

To demonstrate that the greatest improvement in output moments in each RAMAO iteration can yield the reduced-order model with better overall performances in frequency responses, there are two observations:

1. In the first iteration in the RAMAO method, the Step (2.2) is to choose s i εS such that max(|c T (s i E−A) −1 b|)=max(|Y(s i )|). This is equivalent to finding out the expansion frequency with the maximum magnitude in the output frequency response.

2. The residual error, defined as r(s)=b−(sE−A)V{circumflex over (x)}(s), is an effective and efficient estimator for modeling error [Reference 9]. A sufficiently small r(s 0 ) at some s 0 typically implies a small error at s 0 .

r ⁡ ( s ) = ( sE - A ) ⁢ ( ∑ j = j ^ i + 1 ∞ ⁢ ( X j ⁡ ( s i ) - V ⁢ X ^ j ⁡ ( s i ) ) ⁢ ( s - s i ) j ) .

Ignoring the occurrences that s 0 is near an eigenvalue of (A,E) and assuming that the predetermined expansion points are chosen for minimizing (s−s i ) j and the high-order terms,

r ( s )≈ X ĵ+1 ( s i )− V{circumflex over (X)} ĵ i +1 ( s i ).

Ignoring the occurrences that s 0 is near an eigenvalue of (A,E) and assuming that the predetermined expansion points are chosen for minimizing (s−s i ) j and the high-order terms, we have

r ⁡ ( s ) ≈ X j ^ + 1 ⁡ ( s i ) - V ⁢ X ^ j ^ i + 1 ⁡ ( s i ) .

Experimental Results

A mesh twelve-line circuit, presented in FIG. 1 , is studied to show the efficiency of the method of the present invention. The line parameters of the horizontal lines are T 1 :R=0.05 Ω/mm,L=0.5025 nH/mm,C=0.155 pF/mm and those of the vertical lines are T 2 :R=0.06 Ω/mm,L=0.5480 nH/mm, C=0.1423 pF/mm. Each line is 30 mm long and divided into 20 sections. Therefore, the dimension of the system matrices is n=719, m=1, and p=1. The frequency response between 0 and 5 GHz at the voltage V out is investigated, and a total of 1001 frequency points are distributed uniformly for simulations. Three reduced-order models are examined.

1. The Arnoldi method at an expansion frequency of 0 hz with 40 iterations;

2. The Arnoldi method at an expansion frequency of s=2 πj×5 GHz with 20 iterations; and

3. The RAMAO method at the expansion frequencies of S=2 πj×{1 Hz, 0.83 GHz, 1.67 GHz, 2.50 GHz, 3.33 GHz, 4.17 GHz, 5 GHz} with 20 iterations.

The real congruence transformation is used, so the dimensions of these reduced-order models are all equal to 40. FIG. 2 shows the corresponding waveforms. Comparing the average relative errors, corresponding to 1001 sampling frequency points, in frequency response of the three reduced-order models obtains (a) the error of the model yielded by the Arnoldi algorithm at 0 Hz: 436%; (b) that yielded by the Arnoldi algorithm at 2 πj*5 GHz:60.0%, and (c) that yielded by the AORA algorithm: 14.4%. From simulation results, the following observations exist:

1. The error between the original model and the reduced-order model by the Arnoldi method at frequency 0 is very small near the low frequency. Also, the error between the original model and the reduced-order model by the Arnoldi method at 3GHz near the high frequency is relatively small. The above results illustrate that the single-point Arnoldi method can only capture the local characteristics near their expansion points.

2. The reduced-order model by the RAMAO method can reflect the dynamical behaviors over a more wide frequency range than the above models. It is not hard to see that it shows the best performance among all simplified models by their intelligently selecting scheme.

FIG. 3 shows the RAMAO lemniscates at iterations 2 , 4 , 18 and 20 , where star “*”, circle “o”, and dash “—” represent eigenvalues of the original model and the corresponding reduced-order model and lemniscates, respectively. These lemniscates help to observe the convergence behavior of approximation eigenvalues generated by the RAMAO method [Reference 17]. As the iteration number increases, components of these lemniscates typically appear, which surround the extreme eigenvalues of −Â −1 Ê and then shrink rapidly to a point, namely the eigenvalue itself. Some observations need to be addressed: (1) the convergence range is big at first and then shrinks; (2) the approximate eigenvalues almost converge to the outer eigenvalues at the 20 th iteration. The inner ones can not be distinguished.

Also, in order to take a view of the convergence mechanism of the RAMAO iteration, a class of views of the convergence process appear in FIG. 4 . The figure shows the Ritz values, which are the approximate eigenvalues yielded by the RAMAO algorithm for the steps from q=1 to q=20. The eigenvalues and Ritz values are represented by circle ‘o’ and point ‘.’, respectively. The lines connecting the points help to view the path of convergence. It can be observed that the dispersive eigenvalues have fast convergence and the dense ones do not. Hence, more iterations are needed to split the dense eigenvalues if better performances are desired. Note that no ghost eigenvalue exists in FIG. 4 .

Next, consider the frequency response of the current that leaves from the voltage source, that is, c=b. Set the iteration number q=20. Two reduced-order models by the RAMAO method with different sets of the number of the matched moments at each expansion point are examined. First, both the orthnormal matrices V q and V 2q are yielded by the RAMAO algorithm with 20 and 40 iteration numbers, respectively. Next, the reduced-order models generated by two projectors: (1) U 1 =V 2q and (2) U 2 =[V q SV q ]. The total number of matched moments of the two reduced-order models is the same.

Table 3 summarizes the order of moments to be matched at each expansion points of the RAMAO algorithm. Their corresponding relative errors of frequency responses are displayed in FIG. 5 . Comparing their corresponding average relative error (1) 1.22% and (2) 4.04% in FIG. 5 , the error of the model yielded by applying V 2q , which is obtained by performing the RAMAO algorithm 10 iterations more than the others, is the smallest. The result implies that the model generated by the RAMAO method with more iterations can indeed yield the greatest improvement not only in output moments but also in the frequency response among all reduced-order models with the same order.

A general framework for constructing a reduced-order system has been developed using a RAMAO method. The proposed framework extends the classical multi-point Pade approximation, using the rational Arnoldi iteration method. In each iteration, the expansion frequency will be chosen to generate the greatest improvement of output moments. The proposed method is highly suitable for large-scale electronic systems. An application of the circuit simulation has been considered to illustrate the accuracy and the efficiency of the proposed method.

[1] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, H. van der Vorst, and editors. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide . SLAM, Philadelphia, 2000.

[2] M. Celik, O. Ocali, M. A. Tan, and A. Atalar. Pole-zero computation in microwave circuits using multi-point Pade approximation. IEEE Trans. Circuits and Systems - I Fundamental Theory and Applications, 42:6-13, 1995.

[3] E. Chiprout and M. S. Nakhla. Asymptotic Waveform Evaluation and Moment Matching for Interconnect Analysis . Kluwer Academic Publishers, Boston, 1994.

[4] M. Chou and J. K. White. Efficient formulation and model-order reduction for transient simulation of three-dimensional VLSI interconnect. IEEE Trans. CAD, 16:1454-1476, 1997.

[5] I. M. Elfadel and D. D. Ling. A block rational Arnoldi algorithm for multipoint passive model-order reduction of mutiport RLC networks. In Proc. ICCAD 97, pages 66-71, 1997.

[6] P. Feldmann and R. W. Freund. Efficient linear circuit analysis by Pade approximation via the Lanczos process. IEEE Trans. CAD, 14:639-649, 1995.

[7] R. W. Freund. Krylov-subspace methods for reduced-order modeling in circuit simulation. Journal of Computational and Applied Mathematics, 123:395-421, 2000.

[8] K. Gallivan, E. J. Grimme, and P. V. Dooren. A rational Lanczos algorithm for model reduction. Numerical Algorithms, 12:33-63, 1996.

[9] E. J. Grimme. Krylov Projection Methods for Model Reduction . PhD thesis, University of Illinois at Urbana-Champaign, 1997.

[10] H. J. Lee, C. C. Chu, and W. S. Feng. An adaptive-order rational arnoldi method for model-order reductions of linear time-invariant systems. Technical report, Chang Gung Univ., 2003.

[11] H. J. Lee, C. C. Chu, and W. S. Feng. Interconnect modeling and sensitivity analysis using adjoint networks reduction technique. In Proc. ISCAS 2003, pages 648-651, 2003.

[12] T. V. Nguyen and J. Li. Multipoint Pade approximation using a rational block Lanczos algorithm. In Proc. ICCAD 97, pages 72-75, 1997.

[13] A. Odabasioglu, M. Celik, and L. Pileggi. PRIMA: Passive reduced-order interconnect macromodeling algorithm. IEEE Trans. On CAD, 17:645-653, 1998.

[14] J. R. Phillips, L. Daniel, and L. M. Silveira. Guaranteed passive balancing transformations for model order reduction. IEEE Trans. On CAD, 22:1027-1041, 2003.

[15] L. T. Pillage and R. A. Rohrer. Asymptotic waveform evaluation for timing analysis. IEEE Trans. On CAD, 9:352-366. 1990.

[16] A. Ruhe. Rational Krylov sequence methods for eigenvalue computation. Lin. Alg. Appl., 58:391-405, 1984.

[17] L. N. Trefethen and D. Bau. Numerical Linear Algebra. SLAM, Philadelphia, 1997.

[18] J. M. Wang, C. C. Chu, Q. Yu, and E. S. Kuh. On projection-based algorithms for model-order reduction of interconnects. IEEE Trans. Circuits Syst. I, 49:1563-1585, 2002.