Efficient model order reduction via multi-point moment matching

Abstract

A method for mapping moments in a reduced order system of approximation order q for use in simulating a circuit or system having n state variables at n nodes, the circuit or system having I inputs. The method includes calculating only q+I moments, where q is the approximation order and I is the number of inputs of the circuit or system being simulated, sorting the state variables at the n nodes, selecting q nodes of the n nodes, and calculating the dominate poles and zeros using a multi-point moment matching algorithm to simultaneously match q+I moments at the selected q nodes of the circuit or system. In one embodiment, the method includes using extra dummy inputs such that the total number of inputs equals I, such that K*I>q where K is a constant having a value in the range of about 4 to 8.

1 . A method for matching moments of selected state variables of a circuit or system, said method comprising: 
 determining a reduced order system having q+I moments of the original state variables, where q is the approximation order and I is the number of inputs of the circuit or system, using the equations        A=Λ   1 Λ 2   −1      b   k   =−Am   o,k      m   i,k   =Am   i+1,k      for any i=0, 1, 2, . . . q−1. and any k=1, 2, . . . , I, wherein Λ 1  and Λ 2  are two q×q matrices given by                    Λ   1     =     [       m     0   ,   1       ⁢     m     1   ,   1       ⁢           ⁢   …   ⁢           ⁢     m         q   I     -   1     ,   1       ⁢     m     0   ,   2       ⁢     m     1   ,   2       ⁢           ⁢   …   ⁢           ⁢     m         q   I     -   1     ,   2       ⁢           ⁢   …   ⁢           ⁢     m     0   ,   1       ⁢     m       1   ,   1     ⁢               ⁢   …   ⁢           ⁢     m         q   I     -   1     ,   1         ]                   Λ   2     =     [       m     1   ,   1       ⁢     m     2   ,   1       ⁢           ⁢   …   ⁢           ⁢     m       q   I     ,   1       ⁢     m     1   ,   2       ⁢     m     2   ,   2       ⁢           ⁢   …   ⁢           ⁢     m       q   I     ,   2       ⁢           ⁢   …   ⁢           ⁢     m     1   ,   1       ⁢     m       2   ,   1     ⁢               ⁢   …   ⁢           ⁢     m       q   I     ,   I         ]                   wherein m o,k , m 1,k , . . . , m q/I,k  are the first q/I+1 moments due to the k th  input of the circuit or system being simulated.    
   
   
       2 . The method according to  claim 1 , including matching only q(q+I) moments which are q+I moments at q nodes of the circuit or system being simulated.  
   
   
       3 . The method according to  claim 2 , wherein the numerical stability of a q order approximation increases as the number of inputs increases.  
   
   
       4 . The method according to  claim 1 , including using at least one extra dummy input.  
   
   
       5 . The method according to  claim 1 , including using extra dummy inputs such that the total number of inputs equals I, such that K*I>q, where K is a constant having a value in the range of about 4 to 8.  
   
   
       6 . The method according to  claim 5 , wherein K has a value of 6.  
   
   
       7 . A method for simulating a circuit or system using model order reduction, the circuit or system including n state variables, said method comprising: 
 determining a reduced order system having q+I moments of the original state variables, where q is the approximation order and I is the number of inputs of the circuit or system, using the equations        A=Λ   1 Λ 2   −1      b   k   =−Am   o,k      m   i,k   =Am   i+1,k      for any i=0, 1, 2, . . . and any k=1, 2, . . . , I, wherein Λ 1  and Λ 2  are two q×q matrices given by                    Λ   1     =     [       m     0   ,   1       ⁢     m     1   ,   1       ⁢           ⁢   …   ⁢           ⁢     m         q   I     -   1     ,   1       ⁢     m     0   ,   2       ⁢     m     1   ,   2       ⁢           ⁢   …   ⁢           ⁢     m         q   I     -   1     ,   2       ⁢           ⁢   …   ⁢           ⁢     m     0   ,   1       ⁢     m       1   ,   1     ⁢               ⁢   …   ⁢           ⁢     m         q   I     -   1     ,   1         ]                   Λ   2     =     [       m     1   ,   1       ⁢     m     2   ,   1       ⁢           ⁢   …   ⁢           ⁢     m       q   I     ,   1       ⁢     m     1   ,   2       ⁢     m     2   ,   2       ⁢           ⁢   …   ⁢           ⁢     m       q   I     ,   2       ⁢           ⁢   …   ⁢           ⁢     m     1   ,   1       ⁢     m       2   ,   1     ⁢               ⁢   …   ⁢           ⁢     m       q   I     ,   I         ]                   wherein m o,k , m 1,k , . . . , m q/I,k  are the first q/I+1 moments due to the k th  input of the circuit or system being simulated.    determining the moments due to an input k by matching the moments of the reduced order system to the moments of the q variables x j , x 2 , . . . , x q  of the original circuit or system        b   k   =−Am   o,k    m i,k   =Am   i+1,k      for any i=0, 1, 2, . . . and any k=1, 2, . . . , I;    wherein the eigen values of A, p 1 -p q , represent the common set of poles of the circuit and the residues of the transfer function between the input and any state variable x j  in the original circuit or system are related to the eigen vectors of A by                    k     1   ,   k       =       α     1   ,   k       ⁢     v   1                     k     2   ,   k       =       α     2   ,   k       ⁢     v   2                 ⋮               k     q   ,   k       =       α     q   ,   k       ⁢     v   q                     for k=1 . . . I where k i,k  is a vector including the residues of the i th  pole p i  at the q variables x.. x.. . . . , x q  due to u k . v i  is the eigen vector of A corresponding to the i th  pole p i  and α 1,k -α q,k  are a set of q constants unique to each input u k ; and    calculating the response of the circuit or system at these nodes to an arbitrary input using LaPlace transform techniques.    
   
   
       8 . The method according to  claim 7 , including matching only q(q+I) moments which are q+I moments at q nodes of the circuit or system being simulated.  
   
   
       9 . The method according to  claim 7 , wherein the numerical stability of a q order approximation increases as the number of inputs increases.  
   
   
       10 . The method according to  claim 7 , including using at least one extra dummy input.  
   
   
       11 . The method according to  claim 10 , including setting the dummy input to zero in the reduced order system after the reduced order system has been determined.  
   
   
       12 . The method according to  claim 10 , wherein the dummy input satisfies the condition that setting the dummy input to zero does not change the circuit structure of the circuit or system being simulated.  
   
   
       13 . The method according to  claim 10 , wherein the dummy input satisfies the condition that moment vectors due to the dummy input can be calculated by using path tracing techniques where applicable.  
   
   
       14 . The method according to  claim 10 , wherein the dummy input is represented as at least a voltage source.  
   
   
       15 . The method according to  claim 10 , wherein the dummy input is represented as a voltage source connected in series with an inductor or a resistor in the circuit or system being simulated.  
   
   
       16 . A method for simulating a circuit or system using model order reduction, the circuit or system including n state variables and a single input, said method comprising: 
 determining a reduced order system having q+1 moments of the original state variables, where q is the approximation order, using the equations        A=Λ   1 Λ 2   −1      b=−Am   0      and where Λ 1  and Λ 2  are two q×q matrices given by      Λ 1 =[m 1 m 2  . . . m q−1 ] Λ 2 =[m 1 m 2  . . . m q ]   and where m o , m 1 , . . . , m q  are the first q+1 moments at selected q nodes of the circuit of the circuit or system being simulated;    calculating the residues k i  of the transfer function between the input and any state variable x j  in the original circuit or system using the set of linear equations                      m   o   j     =     -     (         k   1   j       p   1       +       k   2   j       p   2       +   …   +       k   q   j       p   q         )         ,                   m   1   j     =     -     (         k   1   j       p   1   2       +       k   2   j       p   2   2       +   …   +       k   q   j       p   q   2         )         ,                 m     q   -   1     j     =     -       (         k   1   j       p   1   q       +       k   2   j       p   2   q       +   …   +       k   q   j       p   q   q         )     .                     where p 1 , p 2 , . . . p q  are the reduced order common set of poles for the circuit or system, and where the eigen values of A, p 1 , p 2 , . . . , p q , are the reduced order common set of poles of the circuit or system; and    calculating the response of the circuit or system at these nodes to an arbitrary input using LaPlace transform techniques.    
   
   
       17 . The method according to  claim 16 , including matching only q(q+I) moments which are q+I moments at q nodes of the circuit or system being simulated.  
   
   
       18 . The method according to  claim 17 , wherein the numerical stability of a q order approximation increases as the number of inputs increases.  
   
   
       19 . A method for mapping moments in a reduced order system of approximation order q for use in simulating a circuit or system having n state variables at n nodes, the circuit or system having I inputs, said method comprising: 
 calculating only q+I moments, where q is the approximation order and I is the number of inputs of the circuit or system being simulated,    sorting the state variables at the n nodes;    selecting q nodes of the n nodes; and    calculating the dominate poles and zeros using a multi-point moment matching algorithm to simultaneously match q+I moments at the selected q nodes of the circuit or system.    
   
   
       20 . The method according to  claim 19 , wherein sorting the state variables includes sorting the state variables at the nodes in terms of a first moment, and selecting the nodes corresponding to the moments at equidistant steps starting with the variable having the smallest moment and ending with the variable having the largest moment.  
   
   
       21 . The method according to  claim 19 , including using at least one extra dummy input.  
   
   
       22 . The method according to  claim 19 , including using extra dummy inputs such that the total number of inputs equals I, such that K*I>q where K is a constant having a value in the range of about 4 to 8.  
   
   
       23 . The method according to  claim 22 , wherein K has a value of 6.  
   
   
       24 . The method according to  claim 21 , including setting the dummy input to zero after the reduced order system has been determined.  
   
   
       25 . The method according to  claim 21 , wherein the dummy input comprises a voltage source.  
   
   
       26 . The method according to  claim 21 , wherein the dummy input comprises a voltage source in series with an inductor or a resistor.  
   
   
       27 . The method according to  claim 19 , including applying moment shifting to improve the accuracy of moment matching approximations.