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

doi:10.1007/s42967-024-00400-2

Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (5): 1769-1790.doi: 10.1007/s42967-024-00400-2

• ORIGINAL PAPERS • 上一篇

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

Lu-Xin Wang^1,2, Yang Cao^1,3, Qin-Qin Shen³

1. School of Information Science and Technology, Nantong University, Nantong, 226019, Jiangsu, China;
2. Department of Basic Teaching, Jiangsu Shipping College, Nantong, 226010, Jiangsu, China;
3. School of Transportation and Civil Engineering, Nantong University, Nantong, 226019, Jiangsu, China

收稿日期:2023-11-30 修回日期:2024-03-10 接受日期:2024-03-14 出版日期:2024-07-23 发布日期:2024-07-23
通讯作者: Qin-Qin Shen,E-mail:shenqq@ntu.edu.cn E-mail:shenqq@ntu.edu.cn
基金资助:
This work was supported by the National Natural Science Foundation of China (No. 11771225), and the Qinglan Project of Jiangsu Province and the Science and Technology Project of Nantong City of China (No. JC2021198).

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

Lu-Xin Wang^1,2, Yang Cao^1,3, Qin-Qin Shen³

1. School of Information Science and Technology, Nantong University, Nantong, 226019, Jiangsu, China;
2. Department of Basic Teaching, Jiangsu Shipping College, Nantong, 226010, Jiangsu, China;
3. School of Transportation and Civil Engineering, Nantong University, Nantong, 226019, Jiangsu, China

Received:2023-11-30 Revised:2024-03-10 Accepted:2024-03-14 Online:2024-07-23 Published:2024-07-23
Contact: Qin-Qin Shen,E-mail:shenqq@ntu.edu.cn E-mail:shenqq@ntu.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (No. 11771225), and the Qinglan Project of Jiangsu Province and the Science and Technology Project of Nantong City of China (No. JC2021198).

摘要/Abstract

摘要： 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.

关键词: Mixed-cell-height circuit legalization (MCHCL), Linear complementarity problem (LCP), Modulus-based method, Modulus-based matrix splitting, Convergence

Abstract: 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.

Key words: Mixed-cell-height circuit legalization (MCHCL), Linear complementarity problem (LCP), Modulus-based method, Modulus-based matrix splitting, Convergence

Lu-Xin Wang, Yang Cao, Qin-Qin Shen. Two Variants of Robust Two-Step Modulus-Based Matrix Splitting Iteration Methods for Mixed-Cell-Height Circuit Legalization Problem[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1769-1790.

参考文献

[1] Bai, Z.-Z.: The convergence of parallel iteration algorithms for linear complementarity problems. Comput. Math. Appl. 32(9), 1-17 (1996)
[2] Bai, Z.-Z.: On the convergence of the multisplitting methods for the linear complementarity problem. SIAM J. Matrix Anal. Appl. 21(1), 67-78 (1999)
[3] Bai, Z.-Z.: Optimal parameters in the HSS-like methods for saddle-point problems. Numer. Linear Algebra Appl. 16(6), 447-479 (2009)
[4] Bai, Z.-Z.: Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17(6), 917-933 (2010)
[5] Bai, Z.-Z., Golub, G.H.: Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems. IMA J. Numer. Anal. 27(1), 1-23 (2007)
[6] Bai, Z.-Z., Golub, G.H., Ng, M.K.: Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl. 24(3), 603-626 (2003)
[7] Bai, Z.-Z., Guo, X.-P.: On Newton-HSS methods for systems of nonlinear equations with positive-definite Jacobian matrices. J. Comput. Appl. Math. 28(2), 235-260 (2010)
[8] Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia (2021)
[9] Bai, Z.-Z., Parlett, B.N., Wang, Z.-Q.: On generalized successive overrelaxation methods for augmented linear systems. Numer. Math. 102, 1-38 (2005)
[10] Bai, Z.-Z., Wang, Z.-Q.: On parameterized inexact Uzawa methods for generalized saddle point problems. Linear Algebra Appl. 428(11/12), 2900-2932 (2008)
[11] Bai, Z.-Z., Yang, X.: On HSS-based iteration methods for weakly nonlinear systems. Appl. Numer. Math. 59, 2923-2936 (2009)
[12] Bai, Z.-Z., Zhang, L.-L.: Modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 20(3), 425-439 (2013)
[13] Bai, Z.-Z., Zhang, L.-L.: Modulus-based multigrid methods for linear complementarity problems. Numer. Linear Algebra Appl. 24(6), e2105 (2017)
[14] Bustany, I.S., Chinnery, D., Shinnerl, J.R., Yutsis, V.: ISPD 2015 benchmarks with fence regions and routing blockages for detailed-routing-driven placement. In: Proceedings of the Symposium on International Symposium on Physical Design (2015)
[15] Cao, Y., Shi, Q., Zhu, S.-L.: A relaxed generalized Newton iteration method for generalized absolute value equations. AIMS Math. 6(2), 1258-1275 (2021)
[16] Cao, Y., Wang, A.: Two-step modulus-based matrix splitting iteration methods for implicit complementarity problems. Numer. Algorithms 82, 1377-1394 (2019)
[17] Cao, Y., Yang, G.-C., Shen, Q.-Q.: Convergence analysis of projected SOR iteration method for a class of vertical linear complementarity problems. Comput. Appl. Math. 42(4), 191 (2023)
[18] Chen, F., Zhu, Y.: A variant of two-step modulus-based matrix splitting iteration method for Retinex problem. Comput. Appl. Math. 41(6), 244 (2022)
[19] Chen, F., Zhu, Y., Muratova, G.V.: Two-step modulus-based matrix splitting iteration methods for retinex problem. Numer. Algorithms 88, 1989-2005 (2021)
[20] Chen, J.-L., Lin, Z.-F.: Mixed-cell-height placement with complex minimum-implant-area constraints. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 41(11), 4639-4652 (2021)
[21] Chen, J.-L., Zhu, Z.-R., Zhu, W.-X., Chang, Y.W.: Toward optimal legalization for mixed-cell-height circuit designs. In: Proceedings of the Annual Design Automation Conference (2017)
[22] Chen, J.-L., Zhu, Z.-R., Zhu, W.-X., Chang, Y.W.: A robust modulus-based matrix splitting iteration method for mixed-cell-height circuit legalization. ACM Trans. Des. Autom. Electron. Syst. 26(2), 1-28 (2020)
[23] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. SIAM, Philadelphia (2009)
[24] Dong, J.-L.: Shifted skew-symmetric iteration methods for nonsymmetric linear complementarity problems. Numer. Algorithms 54(3), 343-357 (2010)
[25] Dong, J.-L., Jiang, M.-Q.: A modified modulus method for symmetric positive-definite linear complementarity problems. Numer. Linear Algebra Appl. 16(2), 129-143 (2009)
[26] Hung, C.-Y., Chou, P.-Y., Mak, W.K.: Mixed-cell-height standard cell placement legalization. In: Proceedings of the on Great Lakes Symposium on VLSI (2017)
[27] Liao, L.-Z., Wang, S.-L.: A self-adaptive projection and contraction method for linear complementarity problems. Appl. Math. Optim. 48(3), 169-180 (2003)
[28] Lin, Y.-B., Jiang, Z.-X., Gu, J.-Q.: DREAMPlace: deep learning toolkit-enabled GPU acceleration for modern VLSI placement. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 40(4), 748-761 (2021)
[29] Noor, M.A.: Fixed point approach for complementarity problems. J. Math. Anal. Appl. 133(2), 437-448 (1988)
[30] Press, W.H. , Flannery ,B.P. , Teukolsky, S.A., Vetterling,W, T.: Numerical Recipes: the Art of Scientific Computing. Cambridge University Press, New York (2007)
[31] Schfer, U.: On the modulus algorithm for the linear complementarity problem. Oper. Res. Lett. 32(4), 350-354 (2004)
[32] Shi, Q., Shen, Q.-Q., Tang, T.-P.: A class of two-step modulus-based matrix splitting iteration methods for quasi-complementarity problems. Comput. Appl. Math. 39(1), 11 (2020)
[33] Subramanian, P.K., Xiu, N.-H.: Convergence analysis of Gauss-Newton methods for the complementarity problem. J. Optim. Theory Appl. 94(3), 727-738 (1997)
[34] Sun, L., Huang, Y.-M.: A modulus-based multigrid method for image retinex. Appl. Numer. Math. 164, 199-210 (2021)
[35] Wang, A., Cao, Y., Chen, J.-X.: Modified Newton-type iteration methods for generalized absolute value equations. J. Optim. Theory. Appl. 181(1), 216-230 (2019)
[36] Wang, L.-X., Shen, Q.-Q., Cao, Y.: Modulus-based matrix splitting iteration method for horizontal quasi-complementarity problem. Commun. Appl. Math. Comput. (2023). https://doi.org/10.1007/s42967-023-00311-8
[37] Zhang, L.-L.: Two-step modulus-based matrix splitting iteration method for linear complementarity problems. Numer. Algorithms 57(1), 83-99 (2011)
[38] Zhang, L.-L., Ren, Z.-R.: A modified modulus-based multigrid method for linear complementarity problems arising from free boundary problems. Appl. Numer. Math. 164, 89-100 (2021)
[39] Zhang, J.-J.: The relaxed nonlinear PHSS-like iteration method for absolute value equations. Appl. Math. Comput. 265, 266-274 (2015)
[40] Zheng, H., Vong, S., Liu, L.: The relaxation modulus-based matrix splitting iteration method for solving a class of nonlinear complementarity problems. Int J. Comput. Math. 96, 1648-1667 (2019)
[41] Zheng, N., Yin, J.-F.: Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem. Numer. Algorithms 64(2), 245-262 (2013)
[42] Zhou, C.-C., Cao, Y., Shi, Q., Qiu, J.: A robust two-step modulus-based matrix splitting iteration method for mixed-size cell circuit legalization problem. J. Circ. Syst. Comput. 32(8), 2350129 (2023)
[43] Zhou, C.-C., Qiu, J., Cao, Y., Yang, G.-C., Shen, Q.-Q., Shi, Q.: An accelerated modulus-based matrix splitting iteration method for mixed-size cell circuits legalization. Integration VLSI J. 88, 20-31 (2023)
[44] Zhou, C.-C., Shen, Q.-Q., Yang, G.-C., Shi, Q.: A general modulus-based matrix splitting method for quasi-complementarity problem. AIMS Math. 7(6), 10994-11014 (2022)

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

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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	Qin-Qin Shen, Geng-Chen Yang, Chen-Can Zhou. Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1617-1638.
[2]	Xu Li, Jian-Sheng Feng. Parameterized QHSS Iteration Method and Its Variants for Non-Hermitian Positive Definite Linear Systems of Strong Skew-Hermitian Parts[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1665-1683.
[3]	Jin-Feng Mao, Fang Chen. On Multi-step Partially Randomized Extended Kaczmarz Method for Solving Large Sparse Inconsistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1724-1743.
[4]	Zhao-Zheng Liang, Jun-Lin Tian, Hong-Yi Wan. A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1242-1263.
[5]	Huaijun Yang. Unconditionally Superconvergence Error Analysis of an Energy-Stable and Linearized Galerkin Finite Element Method for Nonlinear Wave Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1264-1281.
[6]	Lu-Xin Wang, Qin-Qin Shen, Yang Cao. Modulus-Based Matrix Splitting Iteration Method for Horizontal Quasi-complementarity Problem[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1308-1332.
[7]	Xing Liu. An Accelerated Convergence Scheme for Solving Stochastic Fractional Diffusion Equation[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1444-1461.
[8]	Jing Chen, Qi Wang. Numerical Stability and Convergence for Delay Space-Fractional Fisher Equations with Mixed Boundary Conditions in Two Dimensions[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1462-1488.
[9]	Xuan Zhao, Zhongqin Xue. Efficient Variable Steps BDF2 Scheme for the Two-Dimensional Space Fractional Cahn-Hilliard Model[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1489-1515.
[10]	Long-Ze Tan, Ming-Yu Deng, Xue-Ping Guo. On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1580-1597.
[11]	Yujian Cao, Jianguo Huang, Haoqin Wang. A Hybrid Iterative Method for Elliptic Variational Inequalities of the Second Kind[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 910-928.
[12]	Yun-Xia Tan, Zheng-Da Huang. On a Nonlinear Fast Deterministic Block Kaczmarz Method for Solving Nonlinear Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 954-969.
[13]	Gang Bao, Peijun Li, Xiaokai Yuan. Convergence of the PML Method for the Biharmonic Wave Scattering Problem in Periodic Structures[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 1122-1145.
[14]	Shipeng Mao, Jiaao Sun. Error Estimates of Finite Element Method for the Incompressible Ferrohydrodynamics Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 485-535.
[15]	Gui-Lin Yan, Yu-Jiang Wu, Bo Deng. Improvement of Convergence of One- and Two-Step MSM Iteration Methods for Nondifferentiable Nonlinear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 733-758.