{"id":5501,"date":"2012-07-18T22:28:21","date_gmt":"2012-07-18T22:28:21","guid":{"rendered":"https:\/\/mtlsites.mit.edu\/annual_reports\/2012\/?p=5501"},"modified":"2012-07-18T22:28:21","modified_gmt":"2012-07-18T22:28:21","slug":"fastmarkov-a-markov-chain-based-hierarchical-solver-for-large-scale-capacitance-extraction","status":"publish","type":"post","link":"https:\/\/mtlsites.mit.edu\/annual_reports\/2012\/fastmarkov-a-markov-chain-based-hierarchical-solver-for-large-scale-capacitance-extraction\/","title":{"rendered":"FastMarkov: A Markov\u2013Chain-based Hierarchical Solver for Large-scale Capacitance Extraction"},"content":{"rendered":"
Standard full-chip capacitance extraction algorithms rely for computational efficiency on 2D scanning and table lookup algorithms. These algorithms trade off accuracy for computational efficiency and result in large error in the extracted capacitance of complex layouts. It is therefore desirable to use accurate field solvers for full-chip extraction, which in general can be divided into two types: discretization-based and discretization-free. Discretization-based methods include the finite difference methods, the finite element methods and the boundary element methods [1<\/a>] <\/sup>. The most well-known discretization-free algorithm is the floating random walk method and its variants. It is widely accepted that discretization-based methods are very efficient for small and medium-size structures and that discretization-free methods are more efficient for very large structures. Recently, our group has proposed a Markov Chain-based hierarchical algorithm [2<\/a>] <\/sup> combining the advantages of both discretization-based and discretization-free methods.<\/p>\n