集成电路布局设计合法化问题中鞍点矩阵的特征值估计

来源：计算数学杂志2026年第2期北京时间：

作者：曹阳, 王鲁欣, 杨爱利, 周晨璨

单位：1 南通大学交通与土木工程学院, 南通 226019;2 海南师范大学, 海南省计算科学与应用重点实验室, 海口 571158;3 通大学信息科学技术学院, 南通 226019

摘要：将集成电路布局设计合法化问题转化成具有鞍点矩阵结构的线性互补问题具有诸多优点, 而后者高效的数值求解算法与鞍点矩阵的特征值分布密切相关. 针对标准单元具有单倍行高的情形, 本文详细分析了所导出的鞍点矩阵的特征值估计. 理论分析表明, 该鞍点矩阵有部分特征值为1, 其余特征值在复平面内都分布在以(\frac{1}{2},0)为中心的相互垂直的两条线段上. 文中进一步分析了实特征值和复特征值虚部的上下界. 最后通过三个数值算例验证了理论分析结果.

关键词：集成电路布局设计,合法化问题,鞍点矩阵,特征值估计

基金资助：国家自然科学基金项目(12471354,12571402,12401700,92373207),海南省计算科学与应用重点实验室开放课题(JSKX202402),江苏省研究生科研与实践创新计划项目(KYCX24_3640)资助.