# Patent

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

## Abstract

A model reduction method utilizing the rational Arnoldi method with adaptive orders (RAMAO) is applied to high-speed VLSI interconnect models. The method 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.

## Background
BACKGROUND OF THE INVENTION
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.
SUMMARY OF THE INVENTION
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.



BRIEF DESCRIPTION OF THE 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.



DETAILED DESCRIPTION OF THE INVENTION
Circuit Equation and Moment
In analyzing an RLC circuit, the modified nodal analysis (MNA) can be applied as follows [References 13 and 18].




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




where state vector x(t)εRn 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εRn×n contain capacitances and inductances; the system matrix AεRn×n contain conductances and resistances; the input vector is bεRn, and the output incidence vector is cεRn. 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
              ^
            
            ⁢
            
              
                d
                
                  
                    x
                    ^
                  
                  ⁡
                  
                    (
                    t
                    )
                  
                
              
              
                d
                t
              
            
          
          =
          
            
              
                A
                ^
              
              ⁢
              
                
                  x
                  ^
                
                ⁡
                
                  (
                  t
                  )
                
              
            
            +
            
              
                b
                ^
              
              ⁢
              
                u
                ⁡
                
                  (
                  t
                  )
                
              
            
          
        
        ,
        
          
            
              y
              ^
            
            ⁡
            
              (
              t
              )
            
          
          =
          
            
              
                c
                ^
              
              T
            
            ⁢
            
              
                x
                ^
              
              ⁡
              
                (
                t
                )
              
            
          
        
        ,
      
    
    
      
        (
        2
        )
      
    
  




where Ê,ÂεCq×q, {circumflex over (x)},{circumflex over (b)},ĉεCq, 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)=cTX(S)=cT(sE−A)−1b. Expanding X(s) in power series about various frequencies siεC for i=1,2 . . . ,î,




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




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

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)(si)=Ŷ(j)(si),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 ΨεCn×n and a vector ξεCn, the qth Krylov sequence Kq(Ψ,ξ)≡(ξ,Ψξ,Ψ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 VqεCn×q from the successive Krylov subspace Kq(Ψ,ξ)=span{ν1,ν2, . . . ,νq}, where νiεVq,i=1, . . . ,q. Set Ψ=−(siE−A)−1E and ξ=(siE−A)−1b. The Kyrlov subspace Kq{Ψ,ξ} is indeed spanned by the system moments X(j)(si) for j=0,1 . . . q−1. The reduced-order Ŷ(s) can be constructed using the orthogonal projection x(t)=Vq{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],

Ê=VqTEVq, Â=VqTAVq, {circumflex over (b)}=VqTb, and ĉ=VqTc   (3)

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

Adjoint Network Reduction

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

Ŷ(j)(si)=Y(j)(si), 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=(s1,s2, . . . si} 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 si,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 s1; the next ĵ2 iterations are associated with s2, and so on. Each Arnoldi iteration generates ĵi orthonormal vectors. Then, Vq=[ν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.








TABLE 1





Rational Arnoldi Algorithm

















Algorithm 1: RA (input: E, A, b, S, J; output: Vq)



(1): /* Initialize */



r0 := (s1E − A)−1b



(2): /* Begin RA Iterations */



for i = 1, 2, ..., î do









for j = 1, 2, ..., ĵi do









k := (i − 1)ĵi + j



(2.1): /* Generate the New vk */



hk,k−1 := ∥rk−1∥, vk = rk−1/hk,k−1



(2.2): /* Update rk for the Next Iteration */



if j = ĵi and i <= î then rk := (si+1E − A)−1b



else rk := −(siE − A)−1Evk



end if



for t = 1, 2, ..., k do









ht,k := vtHrk, rk := rk − ht,kvt









end for









end for









end for



q := Σi=1îĵi, Hq := [hi,j]i,j=1,2,... ,q



Vq = [v1 v2 ... vq]



(3): /* Yield Real Vq for Complex Expansion Points */



if there exists any si ε S such that si is not real



then Vr := real(Vq), Vi := imag(Vq)









[Vq, rr] = qr([Vr Vi])









end if










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 rk is the same as that used in the Arnoldi method. However, if the expansion point is changed, then, the residue vector rk can be reset to (si+1E−A)−1b, which is equal to the system moment X(0)(si+1) for the subsequent expansion frequency si+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 vk and the orthonormal matrix Vk−1 generated in earlier iterations can indeed span the entire Krylov subspace. Once the orthonormal matrix Vq 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 Vq is the orthonormal matrix generated by the rational Arnoldi algorithm with q iterations. Since X(j)(si) εcolspan{Vq} for j=0,1, . . . ,ĵi and i=1,2, . . . î,

X(j)(si)=Vq{circumflex over (X)}(j)(si) and Y(j)(si)=Ŷ(j)(si)  (5)

The Ramao Method

As stated in the last section, selecting a set of expansion points si for i=1, . . . ,î and the number of matched moments ĵi about each si is not trivial. For simplicity, the expansion points si 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)(si)=Ŷ(j)(si) 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)(si)=Ŷ(j+1)(si) can be guaranteed. The concept that underlines the RAMAO method is employed to select an expansion point si*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)(si*q+1)−Ŷ(j+1)(si*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 Vq 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: Vq)



(1): /* Initialize */



for each si ε S do









k(0)(si) := (siE − A)−1b, r(0)(si) := k(0)(si)



hπ(si) := 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 si ε S as the i giving maxi(|hπ(si)cTr(j−1)(si)|)



Set sij* be the expansion frequency in the jth iteration



(2.2): /* Generate the Orthonormal Vector at sij* */



hj,j−1(sij*) := ∥r(j−1)(sij*)∥



vj = r(j−1)(sij*)/hj,j−1(sij*)



hπ(sij*) := hπ(sij*) · hj,j−1(sij*)



(2.3): /* Update r(j)(si) for the Next Iteration */



for each si ε S do









if (si == sij*) then k(j)(sij*) := −(siE − A)−1Evj



else k(j)(si) := k(j−1)(si)



end if



r(j)(si) := k(j)(si)



for t = 1, 2, . . . , j do









ht,j(si) := vtHr(j)(si)



r(j)(si) := r(j)(si) − ht,j(si)vt









end for









end for









end for



Vq = [v1 v2 . . . vq]



(3): /* Yield Real Vq for Complex Expansion Points */



if there exists any si ε S such that si is not real



then Vr := real(Vq), Vi := imag(Vq)









[Vq, rr] = qr([Vr Vi])









end if










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

Step (2.1): Choose an expansion frequency si such that si 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, maxsiεS|Y(j+1)(si)−Ŷ(j+1)(si)|=maxsiεS|hπ(si)cTr(j−1)(si). Ŷ(j+1)(si) is the (j+1)st-order output moment of the reduced-order model Ŷ(s), which if yielded using the congruence transformation matrix Vj−1(j >1) and matches j-order output moments of Y(s) at si. The chosen expansion frequency in the jth iteration is called si*j.
Step (2.2): After the chosen expansion point si*j in jth iteration has been determined, the single-point Arnoldi method is applied at the expansion point si*j. The new orthonormal vector νj is incorporated into the orthonormal matrix Vj−1. The normalization coefficient hπ(si)=Πj∥r(j−1)(si)∥ if si is selected in the jth iteration.
Step (2.3): Determine the new residual r(j)(si) at each expansion point si. The calculation involves a projection with the new orthonormal matrix Vj. The next vector k(j)(si*j) at the frequency si*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 si, the vector k(j)(si) at frequency si in the current iteration remains k(j−1)(si), which was obtained in the preceding iteration.
Step (3): Generate the real orthogonal matrix Vq 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)(si)=Ŷ(j)(si) 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 Vq using the RAMAO algorithm, where q=Σi=1îĵi. The magnitude error between the ĵith-order moments Y(ĵi)(si) and Ŷ(ĵi)(si) at each expansion point si can be expressed as follows:

|Y(ĵi)(si)−Ŷ(ĵi)(si)|=|hπ(si)cTr(ĵi−1)(si)|,  (6)

where hπ(si)=Πj∥r(j−1)(si)∥. 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 siεS such that max(|cT(siE−A)−1b|)=max(|Y(si)|). 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(s0) at some s0 typically implies a small error at s0.




  
    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 s0 is near an eigenvalue of (A,E) and assuming that the predetermined expansion points are chosen for minimizing (s−si)j and the high-order terms,

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

Ignoring the occurrences that s0 is near an eigenvalue of (A,E) and assuming that the predetermined expansion points are chosen for minimizing (s−si)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 T1:R=0.05 Ω/mm,L=0.5025 nH/mm,C=0.155 pF/mm and those of the vertical lines are T2: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 Vout 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 20th 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 Vq and V2q are yielded by the RAMAO algorithm with 20 and 40 iteration numbers, respectively. Next, the reduced-order models generated by two projectors: (1) U1=V2q and (2) U2=[VqSVq]. 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 V2q, 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.







TABLE 3







Selection scheme of the RAMAO method










Frequency
Selecting Order












(×2πj)

(U = Vq)
(U = V2q)

















1
Hz
2
8
2
8
16


0.83
GHz
4
10 
4
10
15


1.67
GHz
7
—
7
11
19


2.50
GHz
5
—
5
12
18


3.33
GHz
6
—
6
14
—


4.17
GHz
3
9
3
9
17


5
GHz
1
—
1
13
20









CONCLUSIONS
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.
REFERENCES
[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.

## Claims

1. A computer implemented method for making a simplified circuit model comprising:
using said computer to perform the steps of;
(A) inputting a mesh circuit and values of parameters of the mesh circuit;
(B) establishing a state matrix of an original circuit mode;
(C) inputting an order of a simplified circuit and acquiring a corresponding orthonormal matrix by an adaptive-order multipoint rational Arnoldi algorithm, wherein the adaptive-order multipoint rational Arnoldi algorithm consists of:
(a) Approximation model using moment matching method;
(b) Arnoldi algorithm that features Krylov subspace iteration;
(c) An approximation model that contains several expansion frequencies; and
(d) An expansion frequency selection methods;

(D) orthogonally projecting the state matrix of the original circuit mode into the corresponding orthonormal matrix of the simplified circuit;
(E) outputting the simplified circuit model from the orthogonally projection; and
(F) storing the simplified circuit model in the computer memory.

2. The method for making the simplified circuit model as defined in claim 1, wherein the Arnoldi algorithm that features Krylov subspace iteration successively establishes approximate simplified circuits by iteration, wherein as the order of the simplified circuit increases by one order, a newly formed simplified circuit requires only one additional iteration.

3. The method for making the simplified circuit model as defined in claim 1, wherein the approximation model that contains several expansion frequencies makes the simplified circuit meet a designing regulation of frequency responding values of a range, and offsets reducing the range to one expansion frequency.

4. The method for making the simplified circuit model as defined in claim 1, wherein the expansion frequency selection method in accordance with the original circuit mode selects an expansion frequency that makes an approximation of the simplified circuit in each iteration of the adaptive-order rational multipoint Arnoldi algorithm.

5. A computer implemented method for making a simplified circuit model comprising:
using said computer to perform the steps of;
(A) inputting a mesh circuit and values of parameters of the mesh circuit;
(B) establishing a state matrix of an original circuit mode;
(C) inputting an order of a simplified circuit and acquiring a corresponding orthonormal matrix by an adaptive-order multipoint rational Arnoldi algorithm, wherein the adaptive-order multipoint rational Arnoldi algorithm follows the following:
(a) inputting the state matrix of the original circuit mode, pre-set expansion frequencies and data about a maximum iteration times of the algorithm;
(b) vectoring a first Krylov series corresponding with an initial setting frequency point;
(c) determining an expansion frequency in each iteration;
(d) carrying out operation of the multipoint rational Arnoldi algorithm in each iteration; and
(e) outputting the orthonormal matrix that matches the maximum iteration times of the multipoint rational Arnoldi algorithm;

(D) orthogonally projecting the state matrix of the original circuit mode into the corresponding orthonormal matrix of the simplified circuit;
(E) outputting the simplified circuit model from the orthogonally projection; and
(F) storing the simplified circuit model in the computer memory.

6. The method for making the simplified circuit model as defined in claim 5, wherein determining the expansion frequency in j times iteration comprises making the maximum advancing moment between the simplified circuits of j order and (j−1) order; comparing the difference between the moment value of the original circuit at different expansion frequencies and the next unmatched moment value of simplified circuit of (j−1) order; and using the expansion frequency with the maximum difference in moment matching method.

7. The method for making the simplified circuit model as defined in claim 6, wherein comparing the difference between the moment value uses:


maxsiεs|Y(j+1)(si)−Ŷ(j+1)(si)|=maxsiεs|hπ(si)cTr(j−1)(si)|


where,
si: in each given group of frequency points for the transfer function of expansion original circuit system{s1,s2, . . . ,simax}, si is the number i;
q: after the adaptive-order multipoint rational Arnoldi method has undergone q times iterations, the approximate simplified circuit can match the moment of q order original circuit;
X(j)(si): the moment of j order original circuit expanded at frequency point si, j<=q;
{circumflex over (X)}(j)(si): The j order moment of approximate simplified circuit that has matched j order original circuit moment and expanded at frequency point si;
r(j−1)(si): The complement vector produced by substituting the vector of Krylov series of adaptive-order multipoint rational Arnoldi method at (j−1) times iterations that corresponding expansion frequency si into modificatory Gram-Schmidt perpendicularity; and
hπ(si): hπ(si)=Πj∥r(j−1)(si)∥, means that frequency point si is selected as the optimal expansion frequency only when the adaptive-order multipoint rational Arnoldi method iterates for j times, and is regarded as the product of the length of complement vector generated from previous iteration, otherwise, the value remains unchanged.

8. The method for making the simplified circuit model as defined in claim 5, wherein the multipoint rational Arnoldi algorithm includes:
(a) carrying out the orthogonally projection between the vector of Krylov series corresponding with the expansion frequency of the iteration and the orthogonal matrix generated by the previous iteration to produce a new orthogonal vector and fulfill the moment matching method; and
(b) carrying out the orthogonally projection between the vector of next unmatched Krylov series corresponding with each expansion frequency of the iteration and the orthogonal matrix generated by the previous iteration and used to calculate the optimal expansion frequency of the next iteration.