Nowadays task partition for parallel computing is becoming more and more important. Particular in power system dynamic simulation, it is critical to design an efficient partition algorithm to reduce the communication and balance the computation load [1]. This paper presents a novel multilevel partition scheme based on the graph partition algorithm. By introducing regional characteristic into the partition, improving the weights of nodes and edges, proposing an objective function to evaluate the partition results and some other schemes, we can efficiently improve the defects in the traditional partition methods. With 12 CPUs for a large scale power system with 10188 nodes, the parallel efficiency with our new algorithm was 63% higher than that with METIS, a well-known program used for partitioning graphs. The proposed algorithm will satisfy the requirement for large scale power grid dynamic simulation.