Computationally efficient modeling and simulation of large scale systems

1. A method of simulating operation of a VLSI interconnect structure having capacitive and inductive coupling between nodes thereof, comprising:

obtaining a matrix U and a matrix V containing different combinations of passive circuit element values for said interconnect structure, said element values for each matrix including inverse inductance K and capacitance C;

obtaining an adjacency matrix A associated with said interconnect structure;

using a processor to perform numerical integration to solve first and second equations each including as a factor the product of the inverse matrix U −1 and at least one other matrix, said first equation including U −1 V and U −1 A, and said second equation including U −1 A and U −1 K.

2. The method of claim 1 , wherein matrices U and V each contain conductance values G in addition to K and C.

3. The method of claim 2 , wherein said first equation is substantially of the form

v n k+1 =U −1 Vv n k −2 U −1 A l T i l k +U −1 A i T ( I s k+1 +I s k ),

where v n and i l are node voltages and inductor currents, respectively, A l is an adjacency matrix for inductance, and I s is a current source vector with adjacency matrix A i ; and

wherein said second equation is substantially of the form

2 U −1 A l T i l k+1 =2 U −1 A l T i l k +hU −1 S ( v n k+1 +v n k ),

where S=A l KA l T .

4. The method of claim 3 , wherein matrices U −1 V, U −1 A l T , U −1 A i T and U −1 S are substantially sparsified matrices, said method further comprising precomputing and storing said substantially sparsified matrices U −1 V, U −1 A l T , U −1 A i T and U −1 S.

5. The method of claim 4 , wherein said numerical integration is performed with matrix-vector multiplication limited to multiplication of substantially sparse matrices.

6. A method of simulating operation of a VLSI interconnect structure having capacitive and inductive coupling between nodes thereof, comprising:

obtaining a matrix U and a matrix V containing combinations of passive circuit element values for said interconnect structure, said element values for each matrix including conductance G, inverse inductance K, and capacitance C;

obtaining an adjacency matrix A associated with said interconnect structure; and

using a processor to perform numerical integration to solve first and second equations each including as a factor the product of the inverse matrix U −1 and at least one other matrix, said first equation including U −1 V and U −1 A, and said second equation including U −1 A and U −1 K.

7. The method of claim 6 , wherein matrices U −1 V, U −1 A and U −1 K are substantially sparsified matrices, said method further comprising precomputing and storing said substantially sparsified matrices U −1 V, U −1 A and U −1 K.

8. The method of claim 7 , wherein said numerical integration is performed with matrix-vector multiplication limited to multiplication of substantially sparse matrices.

9. The method of claim 8 , wherein said first equation is substantially of the form

v n k+1 =U −1 Vv n k −2 U −1 A l T i l k +U −1 A i T ( I s k+1 +I s k ),

where v n and i l are node voltages and inductor currents, respectively, A l is an adjacency matrix for inductance, and I s is a current source vector with adjacency matrix A i ; and

wherein said second equation is substantially of the form

2 U −1 A l T i l k+1 =2 U −1 A l T i l k +hU −1 S ( v n k+1 +v n k ),

where S=A l KA l T .