复杂电磁问题的快速算法研究

复杂目标的电磁散射问题以及复杂环境下的电磁兼容问题一直是国防工业和民用技术中迫切需要解决的关键问题。随着近年来材料技术的快速发展，各种新的人工合成材料的不断涌现，使如何分析这些新材料的电磁特性并将其成功应用到国防及民用工业中也成为了亟待解决的问题。在这些新材料当中，快速精确地分析双各项同/异性材料、单/双负介质材料等是电磁学领域中最具挑战的课题之一。同时研究各种新的复杂电磁结构，例如光子晶体结构、频率选择表面结构等也成为电磁学领域中迫切需要解决的难题之一。因此，本项目以求解上述复杂电磁问题为立项依据，深入研究快速有效的电磁计算方法，以解决当前计算方法在分析复杂电磁问题中的薄弱环节。主要的研究内容包括：1）研究与积分核无关的算法及其相应的关键技术，2）研究快速收敛的迭代算法和预条件算法，3）研究金属与复杂媒质混合的全波求解算法，4）研究与积分核无关的快速算法的并行化。

本项目主要从参数算法、精确算法和近似算法的角度来研究计算机中一些基本的图问题，其中包括被称之为六个基本NP难问题的独立集和点覆盖问题，以及经典的最大流最小割问题的扩展- - 图多分割问题。这些问题非常基础，且应用相当广泛，在整个计算机学科中影响深远，同时这些问题也被研究得非常透彻，任何改进都将在计算机学科内受到强烈关注。项目申请者在这些问题上具有较强的科研基础，近两年研究获得七个当前最优的参数算法、精确算法和近似算法，并解决一个近二十年的公开难题。.参数计算是本项目主要研究方法之一，研究的是一个很难的问题在某个参数较小的时候是否存在有效算法（参数算法）。基于申请人提出的最远最小割技术和新的分支理论，本项目将有望进一步改进并简化图多分割问题的参数算法，3度图及稀疏图上独立集和点覆盖问题的各项算法。在新理论下参数计算中另一个公开难题还有望被解决。目前以上科研进展顺利，预计3年完成。

本项目主要用计算理论中的新发展起来的分支——参数算法等方法来研究若干基本NP难问题，主要包括：独立集、点覆盖、边支配集、图多分割等问题。项目按照计划全部完成，研究成果超过计划的一倍。项目期间共研获10余个当前最佳的算法等。其中两个基本参数算法被参数计算新闻快报《Parameterized Complexity News》中的Table of Races栏目收录，是该栏目目前收录的仅有两项来自中国的研究结果；在图多分割问题上解决了一个10余年的公开难题；在超图上的多分割研究结果及后续研究在EGRES Open等科学网站上被介绍。项目期间以项目负责人为第一作者在Algorithmica、Theoretical Computer Science、MFCS、ISAAC等国际重要期刊和会议发表学术论文21篇，接收并网上发表论文2篇，其中5篇属于中国计算机协会2013年公布的的B区论文，6篇属于C区论文。另外在投C区以上论文4篇。项目主要取得的研究结果如下： 1. 给出了超图上3块割问题的第一个多项式算法，被EGRES Open网站介绍同时算法被日本京都大学实现，在VLSI上得到应用。 2. 给出了多块割问题一个常用的贪心分而治之算法的的紧致近似率从而解决此问题中的一个10余年的公开问题，同时得到多块割问题目前最好的近似算法。 3. 改进了3度图点覆盖问题和边支配集问题两个基本问题的最佳参数算法，其结果在《Parameterized Complexity News》中的Table of Races栏目中被列出。 4. 改进了低度图上独立集问题的最佳精确算法，基于该结果有望改进1986年Robson给出的一般图上的最佳结果。 5. 在其它图多分割、反馈集、TSP、支配集等问题上给出了8个最佳参数算法、精确算法、核心化算法等。 项目（包括地方人才计划等配套）资助学术交流包括：海外高校访问7人次，参加国际并报告会议13人次，邀请海外专家访问11人次等，国内高校访问8人次。共培养10余本科生和8名硕士研究生。

《线性规划问题的统一建模与快速算法》可作为运筹学、管理学、系统工程等专业的线性规划课程研究生教材，也可供有关专业的院校教师、研究生和大学高年级学生以及从事经济管理研究的相关人员作为参考用书。