电路仿真中求解线性方程组的实用随机化GMRES算法.pdf

1、A Practical Randomized GMRES Algorithm for Solving Linear Equation System In Circuit SimulationBaiyu Chen,Jiawen Cheng,WenjianYu*Department of Computer Science and TechnologyTsinghua UniversityPresenter:BAIYU CHEN2ContentsBackgroundProposed MethodExperimental ResultsConclusion3ContentsBackgroundProp

2、osed MethodExperimental ResultsConclusionWith the advance of chip technology,circuits with billions or even more nodes need to be simulated efficiently and effectively.Simulation for large-scale integrated circuits is of significance.4Circuit Simulation5Circuit SimulationA typical framework:(1)With

3、numerical methods,transform differential equations into non-linear equations.(2)With Newton method,transform non-linear equations to linear equations.(3)Solve the constructed linear equations.(the key process)Differential EquationsLinear EquationsNonlinear EquationsBackward Euler or Trapezoidal Meth

4、odNewton orQuasi-Newton MethodThe two key properties of linear equations from circuit simulation problem:(1)Sparse:while the nodes of circuits are enormous,their connections are very sparse.Therefore,the coefficient matrices are sparse.(2)Unsymmetric:the dissymmetry can be caused by many factors.The

5、 increasing dissymmetry can be observed if the integrated chips grow larger.We should leverage the above two properties for more efficient solution.6Circuit SimulationThe two typical types of methods for solving linear equations:(1)Direct methods:decompose the matrix and solve by substitution.Two ma

6、in weaknesses:because of the fill-ins in the decomposition process and we cannot control the accuracy of the solution.(2)Iterative methods:transform the solution process into many-times matrix-vector multiplication(keep the sparsity),and return the solution when the demanded accuracy is met.7Solutio