復雜電磁問題的快速算法研究

復雜目標的電磁散射問題以及復雜環(huán)境下的電磁兼容問題一直是國防工業(yè)和民用技術中迫切需要解決的關鍵問題。隨著近年來材料技術的快速發(fā)展，各種新的人工合成材料的不斷涌現(xiàn)，使如何分析這些新材料的電磁特性并將其成功應用到國防及民用工業(yè)中也成為了亟待解決的問題。在這些新材料當中，快速精確地分析雙各項同/異性材料、單/雙負介質(zhì)材料等是電磁學領域中最具挑戰(zhàn)的課題之一。同時研究各種新的復雜電磁結構，例如光子晶體結構、頻率選擇表面結構等也成為電磁學領域中迫切需要解決的難題之一。因此，本項目以求解上述復雜電磁問題為立項依據(jù)，深入研究快速有效的電磁計算方法，以解決當前計算方法在分析復雜電磁問題中的薄弱環(huán)節(jié)。主要的研究內(nèi)容包括：1）研究與積分核無關的算法及其相應的關鍵技術，2）研究快速收斂的迭代算法和預條件算法，3）研究金屬與復雜媒質(zhì)混合的全波求解算法，4）研究與積分核無關的快速算法的并行化。

本項目主要從參數(shù)算法、精確算法和近似算法的角度來研究計算機中一些基本的圖問題，其中包括被稱之為六個基本NP難問題的獨立集和點覆蓋問題，以及經(jīng)典的最大流最小割問題的擴展- - 圖多分割問題。這些問題非?；A，且應用相當廣泛，在整個計算機學科中影響深遠，同時這些問題也被研究得非常透徹，任何改進都將在計算機學科內(nèi)受到強烈關注。項目申請者在這些問題上具有較強的科研基礎，近兩年研究獲得七個當前最優(yōu)的參數(shù)算法、精確算法和近似算法，并解決一個近二十年的公開難題。.參數(shù)計算是本項目主要研究方法之一，研究的是一個很難的問題在某個參數(shù)較小的時候是否存在有效算法（參數(shù)算法）?；谏暾埲颂岢龅淖钸h最小割技術和新的分支理論，本項目將有望進一步改進并簡化圖多分割問題的參數(shù)算法，3度圖及稀疏圖上獨立集和點覆蓋問題的各項算法。在新理論下參數(shù)計算中另一個公開難題還有望被解決。目前以上科研進展順利，預計3年完成。

本項目主要用計算理論中的新發(fā)展起來的分支——參數(shù)算法等方法來研究若干基本NP難問題，主要包括：獨立集、點覆蓋、邊支配集、圖多分割等問題。項目按照計劃全部完成，研究成果超過計劃的一倍。項目期間共研獲10余個當前最佳的算法等。其中兩個基本參數(shù)算法被參數(shù)計算新聞快報《Parameterized Complexity News》中的Table of Races欄目收錄，是該欄目目前收錄的僅有兩項來自中國的研究結果；在圖多分割問題上解決了一個10余年的公開難題；在超圖上的多分割研究結果及后續(xù)研究在EGRES Open等科學網(wǎng)站上被介紹。項目期間以項目負責人為第一作者在Algorithmica、Theoretical Computer Science、MFCS、ISAAC等國際重要期刊和會議發(fā)表學術論文21篇，接收并網(wǎng)上發(fā)表論文2篇，其中5篇屬于中國計算機協(xié)會2013年公布的的B區(qū)論文，6篇屬于C區(qū)論文。另外在投C區(qū)以上論文4篇。項目主要取得的研究結果如下： 1. 給出了超圖上3塊割問題的第一個多項式算法，被EGRES Open網(wǎng)站介紹同時算法被日本京都大學實現(xiàn)，在VLSI上得到應用。 2. 給出了多塊割問題一個常用的貪心分而治之算法的的緊致近似率從而解決此問題中的一個10余年的公開問題，同時得到多塊割問題目前最好的近似算法。 3. 改進了3度圖點覆蓋問題和邊支配集問題兩個基本問題的最佳參數(shù)算法，其結果在《Parameterized Complexity News》中的Table of Races欄目中被列出。 4. 改進了低度圖上獨立集問題的最佳精確算法，基于該結果有望改進1986年Robson給出的一般圖上的最佳結果。 5. 在其它圖多分割、反饋集、TSP、支配集等問題上給出了8個最佳參數(shù)算法、精確算法、核心化算法等。 項目（包括地方人才計劃等配套）資助學術交流包括：海外高校訪問7人次，參加國際并報告會議13人次，邀請海外專家訪問11人次等，國內(nèi)高校訪問8人次。共培養(yǎng)10余本科生和8名碩士研究生。

《線性規(guī)劃問題的統(tǒng)一建模與快速算法》可作為運籌學、管理學、系統(tǒng)工程等專業(yè)的線性規(guī)劃課程研究生教材，也可供有關專業(yè)的院校教師、研究生和大學高年級學生以及從事經(jīng)濟管理研究的相關人員作為參考用書。