復(fù)雜電磁問(wèn)題的快速算法研究中文摘要

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

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

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

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