Optimal partitioning of the power grid is a key step of parallel computing for on-line relay verifications.An optimal partition method based on virtual impedance matrix and boundary nodes migration is proposed.In order to quickly achieve the initial partition,the nodes are classified by applying the heuristic rule to the elements of virtual impedance matrix.A higher parallel efficiency of the partition results can be obtained if the boundary nodes are migrated based on the initial partition results,and the shortest verification time is used as the objective function.The proposed method has approximate linear time complexity and fast computing speed.The 220 kV network of a provincial grid is used as case studies to verify the correctness and effectiveness of the proposed method.