Two Variants of Robust Two-Step Modulus-Based Matrix Splitting Iteration Methods for Mixed-Cell-Height Circuit Legalization Problem

The mathematical formulation of the mixed-cell-height circuit legalization (MCHCL) problem can be expressed by a linear complementarity problem (LCP) with the system matrix being a block two-by-two saddle point matrix. Based on the robust modulus-based matrix splitting (RMMS) iteration method and its two-step improvement (RTMMS) studied recently, the well-known Hermitian and skew-Hermitian splitting iteration method and the generalized successive overrelaxation iteration method for solving saddle point linear systems, two variants of robust two-step modulus-based matrix splitting (VRTMMS) iteration methods are proposed for solving the MCHCL problem. Convergence analyses of the proposed two iteration methods are studied in detail. Finally, five test problems are presented. Numerical results show that the proposed two VRTMMS iteration methods not only take full use of the sparse property of the circuit system but also speed up the computational efficiency of the existing RMMS and RTMMS iteration methods for solving the MCHCL problem.