快速多極演算法

『壹』 關於 世紀 和年代的演算法我不是很明白【100分】

世紀公元和年代的演算法 本世紀初，美國物理學會(American Institute of Physics)和IEEE計算機社團 (IEEE Computer Society)的一本聯合刊物《科學與工程中的計算》發表了由田納西大學的Jack Dongarra和橡樹嶺國家實驗室的Francis Sullivan 聯名撰寫的「世紀十大演算法」一文，該文「試圖整理出在20世紀對科學和工程領域的發展產生最大影響力的十大演算法」。作者苦於「任何選擇都將是充滿爭議的， 因為實在是沒有最好的演算法」，他們只好用編年順序依次列出了這十項演算法領域人類智慧的巔峰之作——給出了一份沒有排名的演算法排行榜。有趣的是，該期雜志還 專門邀請了這些演算法相關領域的「大拿」為這十大演算法撰寫十篇綜述文章，實在是蔚為壯觀。本文的目的，便是要帶領讀者走馬觀花，一同回顧當年這一演算法界的盛 舉。

1946 蒙特卡洛方法

在廣場上畫一個邊長一米的正方形，在正方形內部隨意用粉筆畫一個不規則的形 狀，呃，能幫我算算這個不規則圖形的面積么？蒙特卡洛(Monte Carlo)方法便是解決這個問題的巧妙方法:隨機向該正方形內扔N（N 是一個很大的自然數）個黃豆，隨後數數有多少個黃豆在這個不規則幾何形狀內部，比如說有M個:那麼，這個奇怪形狀的面積便近似於M/N，N越大，算出來的 值便越精確。別小看這個數黃豆的笨辦法，大到國家的民意測驗，小到中子的移動軌跡，從金融市場的風險分析，到軍事演習的沙盤推演，蒙特卡洛方法無處不在背 後發揮著它的神奇威力。

蒙特卡洛方法由美國拉斯阿莫斯國家實驗室的三位科學家John von Neumann（看清楚了，這位可是馮諾伊曼同志！）,Stan Ulam 和 Nick Metropolis共同發明。就其本質而言，蒙特卡洛方法是用類似於物理實驗的近似方法求解問題，它的魔力在於，對於那些規模極大的問題，求解難度隨著 問題的維數（自變數個數）的增加呈指數級別增長，出現所謂的「維數的災難」（Course of Dimensionality）。對此，傳統方法無能為力，而蒙特卡洛方法卻可以獨辟蹊徑，基於隨機模擬的過程給出近似的結果。

最後八卦一下，Monte Carlo這個名字是怎麼來的？它是摩納哥的一座以博彩業聞名的城市，賭博其實是門概率的高深學問，不是么？

1947 單純形法

單 純形法是由大名鼎鼎的「預測未來」的蘭德公司的Grorge Dantzig發明的，它成為線性規劃學科的重要基石。所謂線性規劃，簡單的說，就是給定一組線性（所有變數都是一次冪）約束條件（例如a1*x1+ b1*x2+c1*x3>0)，求一個給定的目標函數的極值。這么說似乎也太太太抽象了，但在現實中能派上用場的例子可不罕見——比如對於一個公司 而言，其能夠投入生產的人力物力有限（「線性約束條件」），而公司的目標是利潤最大化（「目標函數取最大值」），看，線性規劃並不抽象吧！線性規劃作為運 籌學(operation research)的一部分，成為管理科學領域的一種重要工具。而Dantzig提出的單純形法便是求解類似線性規劃問題的一個極其有效的方法，說來慚 愧，本科二年級的時候筆者也學過一學期的運籌學，現在腦子里能想起的居然只剩下單純形法了——不過這不也正說明了該方法的簡單和直觀么？

順便說句題外話，寫過《萬曆十五年》的黃仁宇曾說中國的傳統是「不能從數目字上管理」，我們習慣於「拍腦袋」，而不是基於嚴格的數據做決定，也許改變這一傳統的方法之一就是全民動員學習線性規劃喔。

1950 Krylov子空間迭代法
1951 矩陣計算的分解方法

50 年代初的這兩個演算法都是關於線性代數中的矩陣計算的，看到數學就頭大的讀者恐怕看到演算法的名字已經開始皺眉毛了。Krylov子空間疊代法是用來求解形如 Ax=b 的方程，A是一個n*n 的矩陣，當n充分大時，直接計算變得非常困難，而Krylov方法則巧妙地將其變為Kxi+1=Kxi+b-Axi的迭代形式來求解。這里的K(來源於作 者俄國人Nikolai Krylov姓氏的首字母)是一個構造出來的接近於A的矩陣，而迭代形式的演算法的妙處在於，它將復雜問題化簡為階段性的易於計算的子步驟。

1951年由橡樹嶺國家實驗室的AlstonHouseholder提出的矩陣計算的分解方法，則證明了任何矩陣都可以分解為三角、對角、正交和其他特殊形式的矩陣，該演算法的意義使得開發靈活的矩陣計算軟體包成為可能。

1957 優化的Fortran編譯器

說 實話，在這份學術氣息無比濃郁的榜單里突然冒出一個編譯器(Compiler)如此工程化的東東實在讓人有「關公戰秦瓊」的感覺。不過換個角度想 想，Fortran這一門幾乎為科學計算度身定製的編程語言對於科學家（尤其是數學家，物理學家）們實在是太重要了，簡直是他們形影不離的一把瑞士軍刀， 這也難怪他們紛紛搶著要把票投給了它。要知道，Fortran是第一種能將數學公式轉化為計算機程序的高級語言，它的誕生使得科學家們真正開始利用計算機 作為計算工具為他們的研究服務，這是計算機應用技術的一個里程碑級別的貢獻。

話說回來，當年這幫開發Fortran的傢伙真是天 才——只用23500行匯編指令就完成了一個Fortran編譯器，而且其效率之高令人嘆為觀止:當年在IBM 主持這一項目的負責人JohnBackus在數十年後，回首這段往事的時候也感慨，說它生成代碼的效率「出乎了所有開發者的想像」。看來作為程序員，自己 寫的程序跑起來「出乎自己的想像」，有時候還真不一定是件壞事！

1959-61 計算矩陣特徵值的QR演算法

呼， 又是一個和線性代數有關的演算法，學過線性代數的應該還記得「矩陣的特徵值」吧？計算特徵值是矩陣計算的最核心內容之一，傳統的求解方案涉及到高次方程求 根，當問題規模大的時候十分困難。QR演算法把矩陣分解成一個正交矩陣（什麼是正交矩陣？！還是趕緊去翻書吧！）與一個上三角矩陣的積，和前面提到的 Krylov 方法類似，這又是一個迭代演算法，它把復雜的高次方程求根問題化簡為階段性的易於計算的子步驟，使得用計算機求解大規模矩陣特徵值成為可能。這個演算法的作者 是來自英國倫敦的J.G.F. Francis。

1962 快速排序演算法

不少讀者恐怕和我一樣,看到「快 速排序演算法」（Quick Sort）這個條目時,心裡的感覺是——「這可總算找到組織了」。相比於其他一些對程序員而言高深莫測的數學物理公式,快速排序演算法真是我們朝夕相處的好 夥伴——老闆讓你寫個排序演算法,如果你寫出來的不是快速排序,你都不好意思跟同事打招呼。其實根本不用自己動手實現, 不論是ANSI C,C++ STL,還是Java SDK,天下幾乎所有的SDK里都能找到它的某種實現版本。

快速排序演算法最早由Tony Hoare爵士設計，它的基本思想是將待排序列分為兩半，左邊的一半總是「小的」，右邊的一半總是「大的」，這一過程不斷遞歸持續下去，直到整個序列有 序。說起這位Tony Hoare爵士，快速排序演算法其實只是他不經意間的小小發現而已，他對於計算機貢獻主要包括形式化方法理論，以及ALGOL60 編程語言的發明等，他也因這些成就獲得1980 年圖靈獎。

快速排序的平均時間復雜度僅僅為O(Nlog(N))，相比於普通選擇排序和冒泡排序等而言，實在是歷史性的創舉。

1965 快速傅立葉變換

如 果要評選對我們的日常生活影響最大的演算法，快速傅立葉變換演算法應該是當仁不讓的總冠軍——每天當拿起話筒，打開手機，聽mp3，看DVD，用DC拍照 ——毫不誇張的說，哪裡有數字信號處理，哪裡就有快速傅立葉變換。快速傅立葉演算法是離散傅立葉演算法（這可是數字信號處理的基石）的一種快速演算法，它有 IBM 華生研究院的James Cooley和普林斯頓大學的John Tukey共同提出，其時間復雜度僅為O(Nlog(N))；比時間效率更為重要的是，快速傅立葉演算法非常容易用硬體實現，因此它在電子技術領域得到極其 廣泛的應用。

1977 整數關系探測演算法

整數關系探測是個古老的問題，其歷史甚至可以追溯到歐幾里德的時代。具體的說:

給 定—組實數X1,X2,...,Xn，是否存在不全為零的整數a1,a2,...an，使得:a 1 x 1 +a 2 x 2 + . . . + a n x n ＝ 0 這一年BrighamYoung大學的Helaman Ferguson 和Rodney Forcade解決了這一問題。至於這個演算法的意義嘛，呃，該演算法應用於「簡化量子場論中的Feynman圖的計算」——太深奧的學問拉！

1987 快速多極演算法

日 歷翻到了1987 年，這一年的演算法似乎更加玄奧了，耶魯大學的Leslie Greengard和Vladimir Rokhlin提出的快速多極演算法用來計算「經由引力或靜電力相互作用的N 個粒子運動的精確計算——例如銀河系中的星體，或者蛋白質中的原子間的相互作用」，天哪，不是我不明白，這世界真是變得快！

所謂浪花淘盡英雄，這些演算法的發明者許多已經駕鶴西去。二十一世紀的頭五年也已經在不知不覺中從我們指尖滑過，不知下一次十大演算法評選的盛事何時再有，也許我們那時已經垂垂老去，也許我們早已不在人世，只是心中唯一的希望——裡面該有個中國人的名字吧！

『貳』 「演算法」 在編程中什麼意思

比如你從b地到a地，有許多條路可以走，任何一條路都可以看作一個演算法。

編程中解決一個問題同樣有很多不同方法，每個方法就是一個演算法。

演算法裡面總有一個最好的，效率最高的，能否做到用效率最高的方法來完成任務，就是一個程序員水平高低的表現之一

『叄』 電磁兼容常用分析軟體有哪些

國外發展概況
電磁模擬技術中運用的主要計算電磁學方法大致可分為2 類：精確演算法和高頻近似方法。精確計算方法包括差分法（FDTD，FDFD）、有限元（FEM）、矩量法（MoM）以及基於矩量法的快速演算法（如快速多極子FMM 和多層快速多極子MLFMA）等，其中，在解決電大目標電磁問題中最有效的方法為多層快速多極子方法。高頻方法一般可歸作2 類：一類基於射線光學，包括幾何光學（GO）、幾何繞射理論（GTD）以及在GTD 基礎上發展起來的一致性繞射理論（UTD）等；另一類基於波前光學，包括物理光學（PO）、物理繞射理論（PTD）、等效電磁流方法（MEC）以及增量長度繞射系數法（ILDC）等。PO 高頻方法由於計算效率較高，對大目標的適應能力強，因此被廣為採用。
基於這些方法，國外不僅形成了眾多的預測模擬系統和軟體，還建立了相應的EMC 資料庫，可開展：1）各種軍用平台電磁兼容性設計，包括大型艦船平台的天線布置設計、艙室內EMC 設計、系統內EMC 分析、系統間EMC 分析等；2）平台間EMC 分析，包括艦船編隊的EMC 分析；3）EMP（電磁脈沖）模擬、各種載體EMP 效應及適應性分析；4）陸海空天電五維現代化戰場電磁環境分析。
目前國外主要的商業軟體主要如下：
1、 EMC2000軟體
該軟體由法國某公司研製，採用的計算方法主要是MoM，FDTD，FVO（有限體積法），PO/GO，GTD，UTD，PTD，ECM（等效電流法），在演算法上與Ship EDF基本相同（增加了FVO），兩者的分析功能非常接近。據介紹，EMC2000 可以對雷電、靜電、電磁脈沖對目標的沖擊效應進行模擬分析，可對復雜介質進行時域分析，對孔縫耦合進行計算，但沒有RCS 計算功能。
2、 FEKO+Cable Mod軟體
該軟體由南非某公司研製，採用的數值演算法主要是MoM，PO，UTD，FEM（有限元法）以及一些混合演算法，在新版軟體中增加了多層快速多極子演算法（MLFMA），Cable Mod 功能和多種脈沖源（高斯、三角、雙指數和斜波脈沖）的時域分析，可為飛機、艦船、衛星、導彈、車輛等系統的全波電磁分析提供解決手段，包括電磁目標的散射分析（圖1）、機箱的屏蔽效能分析（圖2）、天線的設計與分析（圖3）、多天線布局分析（圖4）、系統的EMC/EMI 分析、介質實體的SAR 計算、微波器件的分析與設計、電纜束的耦合分析等。
3、 Ansoft-HFSS軟體
該軟體由美國Ansoft公司研製，採用的主要演算法是有限元法（FEM），主要應用於微波器件（如波導、耦合器、濾波器、隔離器、諧振腔）和微波天線設計（圖5）中，可獲得特徵阻抗、傳播常數、S 參數及電磁輻射場、天線方向圖等參數和結果。該軟體與FEKO 最早進入中國市場，並在國內擁有一定數量的用戶。
4、 CST-SD 軟體
德國CST 公司研製了基於有限積分技術（FIT，該技術類似於FDTD）的模擬軟體CST-SD，主要用於高階諧振結構的設計。它通過散射參數（S 參數）將復雜系統分離成更小的單元進行分析，具體應用范圍主要是微波器件，包括耦合器、濾波器、平面結構電路、各種微波天線和藍牙技術等。圖6 是該軟體對雙指數脈沖信號沿電纜進入機箱後的效應進行模擬分析的結果。
5、 FIDELITY 軟體
FIDELITY 軟體由Zeland公司研製，主要採用非均勻網格FDTD技術，可分析復雜填充介質中的場分布問題，其模擬結果主要包括：S 參數、VSWR（駐波比）、RLC 等效電路、坡印亭矢量、近場分布和輻射方向圖，具體應用范圍主要包括微波/毫米波集成電路（MMIC）、RFDCB、RF 天線、HTS 電路和濾波器、IC 內部連接、電路封裝等。
6、 IMST-Empire軟體
IMST-Empire軟體主要採用FDTD 法，是RF 元件設計的標准模擬軟體，它的應用范圍包括平面結構、連接線、波導、RF 天線和多埠集成，模擬參數主要是S參數、輻射場方向圖等。
7、 Micro-Stripe模擬軟體
該軟體由美國FLOMERICS 公司研製，主要採用傳輸線矩陣法（TLM）。該軟體可對飛機、艦船平台天線布置中的耦合度進行計算，可以對電子設備防雷擊、電磁脈沖和靜電放電威脅進行分析，可以輔助面天線、貼片天線、天線陣的電磁設計。
8、 ADS軟體
該軟體是美國安捷倫公司在HP EESOF系列的EDA 軟體基礎上發展完善起來的大型綜合設計軟體，主要採用MoM 演算法，可協助系統和電路工程師進行各種形式的射頻設計，如離散射頻/微波模塊的集成、電路元件的模擬和模式識別。該軟體還提供了一種新的濾波器的設計，其強大的模擬設計手段可在時域或頻域內實現對數字或模擬、線性或非線性電路的綜合模擬分析與優化。
9、 Sonnet 模擬軟體
Sonnet 是一種基於矩量法的電磁模擬軟體，是高頻電路、微波、毫米波領域設計和電磁兼容/電磁干擾分析的三維模擬工具。主要應用於：微帶匹配網路、微帶電路、微帶濾波器、帶狀線電路、帶狀線濾波器、過孔（層的連接或接地）、耦合線分析、PCB 板電路分析、PCB 板干擾分析、橋式螺線電感器、平面高溫超導電路分析、毫米波集成電路（MMIC）設計和分析、混合匹配的電路分析、HDI 和LTCC 轉換、單層或多層傳輸線的精確分析、多層/平面的電路分析、單層或多層的平面天線分析、平面天線陣分析、平面耦合孔分析等。
10、 IE3D模擬軟體
IE3D 是一個基於矩量法的電磁場模擬工具，可以解決多層介質環境下三維金屬結構的電流分布問題，包括不連續性效應、耦合效應和輻射效應。模擬結果包括S 參數、VWSR（駐波比）、RLC 等效電路、電流分布、近場分布、輻射方向圖、方向性、效率和RCS等。IE3D 在微波/毫米波集成電路（MMIC）、RF 印製板電路、微帶天線、線電線及其它形式的RF 天線、HTS 電路及濾波器、IC 的內部連接及高速數字電路封裝方面是一個非常有用的工具。
11、 Microwave Office軟體
該軟體也是基於矩量法的電磁場模擬工具，是通過2個模擬器實現對微波平面電路的模擬和模擬。「VoltaireXL」模擬器處理集總元件構成的微波平面電路問題，「EMSight」模擬器處理任何多層平面結構的三維電磁場問題。「VoltaireXL」模擬器內設一個元件庫，其中無源器件有電感、電阻、電容、諧振電路、微帶線、帶狀線、同軸線等；非線性器件有雙極晶體管、場效應晶體管、二極體等。在建立電路模型時，可以調出所用的元件。「EMSight」 模擬器的特點是把修正譜域矩量法與直觀的圖形用戶界面（GUI）技術結合起來，使得計算速度加快許多。它可以分析射頻集成電路（RFIC）、微波單片集成電路（MMIC）、微帶貼片天線和高速印製電路（PCB）等的電氣特性。
12、 ICE WAVE模擬軟體
該軟體是針對電子產品電磁兼容設計/電磁干擾分析的三維模擬工具，採用FDTD 全波數值方法。應用范圍包括：PCB 退耦、輻射、接地、過孔和不連續分析，以及微波元器件、鐵氧體、諧振腔、屏蔽盒的電磁分析。
13、 WIPL-D軟體
該軟體是由WIPL-d.o.o.公司基於MoM演算法開發的三維全波電磁模擬設計軟體。它採用了最先進的最大正交化高階基函數（HOBFs）、四邊形網格技術等，減少了內存需求和計算時間。據介紹，該軟體可用201s 模擬一個58λ長平台的天線布局問題。該軟體能解決的電磁問題包括：各種電磁兼容天線設計、復雜平台天線布局問題、復雜平台RCS 計算以及微波無源結構設計。
14、 Singula軟體
該軟體由加拿大IES 公司開發，採用MoM＋PO的混合演算法，可用於天線與天線陣、波導與諧振腔、射頻電路與微波元器件、電磁散射與RCS、吸收率（SAR）等方面的電磁分析，可以分析復雜平台短波和超短波天線布局問題。
15、 FISC軟體
美國Illinois大學於2001年公布的電磁散射分析軟體FISC 適用於導彈（圖7）、飛機（圖8）、坦克等的電磁散射分析，採用的主要方法是多層快速多極子方法（MLFMA），據報道，可以求解未知量達1 千萬的電磁散射問題。
16、 XPATCH軟體
該軟體由美國軍方研製，主要採用彈跳射線法（SBR），並與計算機圖形學技術緊密結合。在計算中，同時考慮了射線直射時的物理光學近似、物理繞射以及射線的多次反射效應（multi-bounce rays）。在計算射線直射效應（first bounce）時，最花時間的是確定復雜目標的陰影部分和遮擋部分，該軟體採用Z-buffering 技術的硬體和軟體精確確定這2 部分。陰影部分和遮擋部分確定之後，直射場部分的貢獻可由PO 計算。為了計算多次反射效應，從入射波向目標發射一系列平行的射線，對每一條射線在目標上（或目標內）的反射和折射進行跟蹤，直到射線離開目標為止。射線的跟蹤是根據幾何光學原理進行的，在反射點或折射點處的場由幾何光學確定，包括極化效應、多層媒質效應等。在射線離開目標時的最後一個反射點，應用物理光學積分計算遠區散射場（圖9）。疊加所有射線對遠區散射場的貢獻，即獲得總的遠區散射場或雷達散射截面。通常，對RCS 的計算而言，1個波長的距離至少需要10 根射線。此軟體基於的方法的原理雖然簡單，但需要有效的幾何CAD 技術和快速的射線跟蹤演算法。

我個人見到的是ansoft和CTS兩個軟體使用的比較多。