随机行走的电路分析应用及并行化改进

论述了随机行走算法的基本原理，理论分析了给定允许误差和置信概率下，随机行走算法的结束条件；讨论了随机行走算法在电路分析中的应用，并结合应用实例分析了算法的性能；讨论了算法的时间复杂性和影响算法执行时间的主要因素，重点分析了算法的并行特征，提出了采用并行计算技术提高算法性能的新方法，通过与串行算法的实验比较，表明了并行计算技术是提高随机行走算法执行速度的有效方法，比现有的方法适应性更广。

Random walk for circuit analysis and improving by parallel computing

The random walk algorithm is introduced basically.The stop criterion of random walk algorithm is analyzed theoretically.Techniques of circuit analysis by random walk algorithm are discussed in details.Through an instance circuit,the performance of algorithm is studied carefully.And the complexity of random walk algorithm is analyzed.The factors related with algorithm runtime are discussed as well.As analyzing the parallel characteristics of random walk algorithm,a novel parallel computing technique is adopted to speedup the random walk algorithm.The experiment results indicate that parallel computing technique can improve random walk algorithm greatly.Moreover,the parallel computing techniques for random walk algorithm are much more adaptable than other methods.