數值線性代數算法在工程軟件中的應用與意義

盧靖程

北京市八一學校 北京 100000

引言

高級計算機體系結構對科學計算領域有著重要影響，包括算法研究和數值線性代數軟件。線性代數，特別是對于線性方程求解，有著重要的地位。如果一個矩陣有著大量的0元素，那么這個矩陣被稱為稀疏矩陣。

為了研究如何提高機計算機體系結構計算效率，研究人員做了大量的工作。在本篇文章中，我們主要關注兩個問題：①工作目的；②使用線性代數建立模塊；③算法設計和并行實；④未來的研究方向。克萊因和LU因式分解作為計算稠密矩陣的典型方法，我們將在設計高級計算機體系結構的線性代數計算軟件中作為重點[1-5]。Cholesky和LU分解是非常重要的數值線性代數算法。這些是高級架構計算機設計線性代數軟件時必須考慮的最重要的因素。數值線性代數算法不僅因為會使得復雜工程問題變得相對簡單，同時還因為正是這些算法才使得沒有閉形式解的方程得出近似解。這些應用包括電磁散射和計算動力學問題。在過去的15年左右，在解決線性代數問題的算法和軟件領域研究人員取得了大量的成果。實現跨平臺可移植的高性能代碼的目標在很大程度上是通過線性代數核的識別實現的，即基本線性代數子程序（BLAS），以及BLAS的連續級別表示的EISPACK、LINPACK、LAPACK和ScaLAPACK庫[6-10]。我們為高級架構計算機設計線性代數算法的方法的關鍵見解是，為了獲得高性能，數據在不同的內存層次之間移動的頻率必須最小化。因此，我們在實現中同時利用向量化和并行化的主要算法方法是使用塊劃分算法，特別是與執行矩陣-向量和矩陣-矩陣操作的高度調優的核一起使用（Level 2和Level 3 BLAS）。在計算機領域可利用諸如MATLAB，MATHEATICA等軟件來進行一些數學問題的計算，分析和大量的模擬。其中MATLAB被廣泛地運用到線性代數的計算中，具有數值分析和一些符號的計算、工程學方面與科學繪圖、數字圖像處理、財務計算與金融工程等功能。而MATHMATICA更多地被用在作圖，模型建立等方面。下圖的圖像由8×8=64個像素點組成。每個像素的值在0到255的范圍內。值0表示純黑色的像素，255表示純白色的像素。如果我們更進一步來去看的話，m×n圖像可以由具有m行和n列的2D矩陣表示，其中每個單元格包含相應的像素值：

圖1 由線性代數生成的像素圖片

綜上所述，線性代數還具有利用矩陣生成圖片的功能，每個圖像可以被認為是由3個2D矩陣表示，對于彩色圖片有相對應每個R，G，B通道各一個。R通道中的像素值0表示紅色的零強度，255表示紅色的全強度。以此來合成，編譯與轉錄圖片。

2 主要工作

2.1 一些關于矩陣的相關概念

2.1.1 行矩陣、列矩陣：在一個m×n階的矩陣中，m的值為1，稱為行矩陣，也被稱為n維行向量;n的值為1，稱為列矩陣，也被稱為m維列向量。

2.1.2 零矩陣：矩陣中所有元素都為0的m×n階矩陣。

2.1.3 n階方陣：對于m×n階矩陣A中，當m=n時，可定義行列式記為|A|；主對角線及主對角線元素存在于n階方陣中。

2.1.4 單位矩陣：當矩陣中主對角線上的元素都為1，其余元素均為0的n階方陣稱為n階單位矩陣，記為In。

2.1.5 對角形矩陣：不是主對角線上的元素全部等于0的n階方陣稱為對角形矩陣。

2.1.6 同型矩陣：若兩個矩陣A與B行列數皆相同，這兩個矩陣就是同型矩陣。

2.1.7 轉置矩陣：將一個矩陣A的行上的元素與列上的元素在不改變排列順序的情況下互換，記為：

2.1.8 對稱矩陣與反對稱矩陣：一個n階方陣A，如果A的轉置矩陣等于A，那么則稱A是一個對稱矩陣。如果A的轉置矩陣等于-A，那么則稱A為反對稱矩陣。

2.1.9 逆矩陣：一個n階方陣A，如果有一個n階方陣B，使得AB等于BA等于單位矩陣，則B稱為A的逆矩陣，記為

2.1.10 伴隨矩陣：設矩陣A，Aij為行列式A中元素aij的代數余子式，稱A*為矩陣A的伴隨矩陣。AA=A*A=|A|I。

2.1.12 正交矩陣：設A為實數R上的矩陣，如果它滿足則稱A為正交矩陣。

2.1.13 矩陣的初等變換：互換、倍乘、倍加。矩陣的對于初等行的變換和對于初等列的變換被統稱叫做矩陣的初等變換。

2.1.14 階梯形矩陣：若矩陣A滿足兩條件：條件一：若存在元素全為0的行，則該行應在最下方；條件二：非零行的第一個不為零的元素的列標號隨行標號的增加而嚴格逐漸增加，滿足兩條件則稱此矩陣A為階梯形矩陣。

2.1.15 一些矩陣的基本性質-秩的性質。

2.1.16 對于rank（X+Y）= rank(X)+rank(Y)的條件的證明。

首先，顯然有rank(X+Y) ≤ rank(X)+rank(Y).我們先證明（X+Y）X=0可以推出AX = 0且BX = 0，0=A（X+Y）X =A^2X，由于rank(X^2) = rank(X)且任意AX=0的解為A^2X = 0的解，我們有AX=0與A^2X=0的解空間相等，于是A^2X=0推出AX = 0，此時當然有BX = 0.由于rank(X^2) = rank(X)，記rank(X) = r，故X^2中有r列線性無關，記為列，考慮XX’，其中X’為與X的列，由題意rank(XX)’= r，故r≥rank(X)’≥rank(XX)’=r，所以有至少r個線性無關的向量使得BX=0而AX≠0，從而rank(X)-rank(Y)，從而rank(X+Y) ≥ rank(X)+rank(Y)，故rank(X+Y) = rank(X)+rank(Y)。

3 稠密線性代數算法

因此，我們需要確定3個的線性代數操作步驟：

第一步：向量-向量運算，如更新y←y + x和內積d = xTy。

這些操作涉及(當向量長度為n時)O(n)和O(n)次計算。

第二步：矩陣-向量運算，比如矩陣-向量乘積y = Ax。這是一個O(n2)數據量的O(n2)次運算。

第三步：矩陣-矩陣運算，比如矩陣-矩陣乘積C =AB。這是一個O(n2)數據量的O(n3)次運算。

BLAS級別2和3的操作可以分別使用雙嵌套循環和三嵌套循環來實現。通過簡單的修改，這意味著對于第2級，每個算法有兩個，而對于第3級，有6個不同的實現。關于第二和第三層的計算可以通過二層和三層嵌套循環實現。通過簡單的調整，這意味著第二層有2個，第三層有6個算法。

雖然就操作數量而言，這兩種實現是相同的，但由于體系結構的考慮，在性能方面可能存在很大的差異。例如，我們注意到，第一個實現中的內部循環使用L行，而第二個實現中的內部循環則遍歷一列。由于矩陣的行或列通常存儲在相鄰的位置，列存儲的歷史默認值繼承自FORTRAN編程語言，因此兩者的性能可能完全不同。大型密集線性系統的一個主要來源是涉及邊界積分方程的解的問題。這些是在感興趣區域邊界上確定的積分方程。

4 討論

所有有實際意義的例子都是在二維邊界上計算某個中間量，然后利用這個信息在三維空間中計算所需的最終量。將三維空間替換為二維空間的代價是最初的O(n3)變量的稀疏問題被O(n2)變量的密集問題所取代。

密集線性方程組在許多領域都有應用，包括：機翼設計；雷達截面研究；船舶和其他岸上設施周圍的船塢；固體在液體中的溶解；降噪；光線通過小顆粒的擴散。

電磁學領域是密集線性系統求解器的主要用戶。這個團體特別感興趣的是解決所謂的雷達截面問題。在這個問題中，一個固定頻率的信號從一個對象反射回來；目標是確定反射信號在所有可能方向上的強度。根據具體的問題，基本的微分方程可能會有所不同。在隱身飛機的設計中，最主要的方程是亥姆霍茲方程。為了求解該方程，研究人員使用矩量法。在流體流動的情況下，問題通常涉及求解拉普拉斯方程或泊松方程。在這里，邊界積分解被稱為面板法，得名于離散和近似一個結構，如飛機的四邊形。一般來說，這些方法被稱為邊界元方法。這些方法的使用產生了大小為O(N)×O(N)的密集線性系統，其中N是使用的邊界點（或面板）的數量。看到3N×3N大小并不奇怪，因為每個邊界元素有3個物理量。

解決這類系統的一個典型方法是使用邏輯單元分解。矩陣的每一項都計算為兩個邊界元的相互作用。通常，必須計算許多積分。在許多情況下，計算矩陣所需的時間要比求解所需的時間大得多。隱身技術的建設者對雷達截面感興趣，他們正在使用直接高斯消去方法來求解密集線性系統。這些系統總是對稱的和復雜的，但不是厄米的。對于線性系統的解決方案，需要考慮系數矩陣。任何直接方法都是高斯消元法的一種變體。如上所述，對于稀疏矩陣，它位于包含非零元素的帶中。為了最小化分解所需的存儲，研究集中在尋找合適的矩陣排序。在許多情況下，通過矩陣的對稱置換對方程進行重新排序不會改變系統的數值屬性，并且可能會大大節省存儲空間。通常，直接方法不利用線性系統的數值特性，因此它們的執行時間主要受輸入矩陣的結構特性的影響。與其嘗試通過減少帶寬來最小化填充，不如嘗試一種直接的方法。“嵌套剖析”排序遞歸地將矩陣圖一分為二，從而將其分成不相交的子圖。更準確地說，給定一個圖，該算法依賴于“分隔符”的存在：一組節點，使得其他節點落入兩個相互不連接的子圖中。首先分解這些子圖，然后分解分隔符的填充，可能低于其他排序。可以看出，對于二維空間維度的偏微分方程，存儲要求在矩陣本身的對數因子內，即非常接近最優值。這個方法對于矩形網格上的偏微分方程很容易，但是如果有細致網格結構，它可以被進一步被推廣。然而，對于3個空間維度的問題，嵌套剖分方法不再是最優的。解剖型方法的一個優點是它們會導致大量的非耦合矩陣問題。因此，在一定程度上，這些方法的并行化很容易。但是，樹中較高級別的節點很快就會少于可用處理器的數量。除此之外，它們也是算法中較大的子問題，從而使方法的并行化復雜化。另一個實際問題是分隔符組的選擇。在典型情況下，這是微不足道的，但在實踐中，特別是并行時，這是一個嚴重的問題，因為兩個結果子圖的平衡取決于這個選擇。最近，所謂的“第二特征向量方法”為此變得流行。

5 結束語

線性代數作為一種基礎的數學工具，通過對幾何的解析，線性代數能夠被進行具體的表示。線性代數主要的研究數學對象對象：向量和方程還有矩陣。這三者的關系非常密切，所以我們在掌握一種理論的時候，應該套用其他曾經學習過的知識來幫助轉移其中的理論，這是學習線性代數時需要掌握的一項重要技能。線性代數作為一種重要的數學工具，體現了數學中的一些思想。比如說線性代數中行列式的公式展開證明就可以從某些更簡單的情況開始論證。線性代數中的內容也與高等數學中的一些內容不謀而合，可以與其他學科甚至建立聯系，只要建立聯系線性代數的學習，就不會像原來那么瑣碎，會將知識形成一整個體系。在線性代數的學習中我們應該努力提高自己的分析能力與并且做到知識點的銜接與聯系、轉換。總的來說，對于線性代數的知識，它的邏輯性、嚴密性還有實用性都非常強，對于學習線性代數，必須要把線性代數的內在聯系搞清楚，完全理解所學知識，并將其應用到實際生活中，這樣也許才能真正理解線性代數。在現實生活中，我們要學會運用線性代數做到解決生活中的問題和一些事情。如本文所述，在具體工程計算中，直接方法具有一些令人滿意的計算特性。最重要的是，他們解決問題的時間是可以預測的，無論是先驗的，還是在確定矩陣排序之后。這是因為該方法不依賴于系數矩陣的數值性質，而僅依賴于其結構。另一方面，占用內存可能很大，隨之而來的是執行時間。對于大型應用程序，實際大小問題的存儲要求可能會令人望而卻步。在未來，我們將進一步討論直接法形成對比的迭代法，迭代方法的存儲需求要低得多。通常，存儲和每次迭代的成本是矩陣存儲的數量級。然而，迭代次數很大程度上取決于線性系統的屬性，并且最多只能知道一個階估計；對于困難的問題，由于局部誤差的積累，這些方法甚至可能不會收斂。在某種的意義上，每次迭代中的迭代方法定位問題解的近似值，測量近似值與真實解之間的誤差，并基于誤差測量通過構造下一次迭代來改進近似值。這個過程重復，直到誤差測量被認為足夠小。