線性代數/主題：計算行列式的速度/解法

解法

大多數這些問題假設可以訪問計算機。

問題 1

計算機系統生成隨機數（當然，這些只是偽隨機數，因為它們是由演算法生成的，但它們通過了許多合理的統計隨機性測試）。

1. 用隨機數填充一個$5\!\times \!5$ 陣列（例如，在範圍$[0..1)$ 內）。檢視它是否為奇異矩陣。重複此實驗幾次。奇異矩陣是頻繁出現的還是罕見的（在這個意義上）？
2. 計時您的計算機代數系統計算十個$5\!\times \!5$ 隨機數陣列的行列式。找到每個陣列的平均時間。針對$15\!\times \!15$ 陣列、$25\!\times \!25$ 陣列和$35\!\times \!35$ 陣列重複前面的專案。（請注意，當一個數組為奇異時，有時可以很快地發現它，例如如果第一行等於第二行。根據您對第一部分的答案，您是否認為奇異系統在您的平均值中扮演重要角色？）
3. 繪製輸入大小與平均時間的關係圖。

答案

1. 在 Octave 中，rank(rand(5))找到一個$5\!\times \!5$ 矩陣的秩，該矩陣的元素在$[0..1)$ 區間內（均勻分佈）。此迴圈執行測試$5000$ 次octave:1> for i=1:5000
   > if rank(rand(5))<5 printf("That's one."); endif
   > endfor
   產生（經過幾秒鐘後）返回提示，沒有任何輸出。Octave 指令碼
   
   function elapsed_time = detspeed (size)
   a=rand(size);
   tic();
   for i=1:10
   det(a);
   endfor
   elapsed_time=toc();
   endfunction
   
   
   導致此會話。
   
   octave:1> detspeed(5)
   ans = 0.019505
   octave:2> detspeed(15)
   ans = 0.0054691
   octave:3> detspeed(25)
   ans = 0.0097431
   octave:4> detspeed(35)
   ans = 0.017398
   
2. 以下是資料（略微四捨五入）和圖表。

   ${\begin{array}{r|ccccccccc}{\textit {matrix\ rows}}&15&25&35&45&55&65&75&85&95\\\hline {\textit {time\ per\ ten}}&0.0034&0.0098&0.0675&0.0285&0.0443&0.0663&0.1428&0.2282&0.1686\end{array}}$

   （此資料來自上述指令碼二十次執行的平均值，因為隨機選擇的矩陣可能恰好需要異常長或短的時間。即使如此，計時也不能過於依賴；這只是一個實驗。）

   

問題 2

使用上面討論的兩種方法，手動計算每個行列式。

1. ${\begin{vmatrix}2&1\\5&-3\end{vmatrix}}$
2. ${\begin{vmatrix}3&1&1\\-1&0&5\\-1&2&-2\end{vmatrix}}$
3. ${\begin{vmatrix}2&1&0&0\\1&3&2&0\\0&-1&-2&1\\0&0&-2&1\end{vmatrix}}$

對於每種方法，分別計算每種情況下使用的乘法和除法的次數。（在計算機中，乘法和除法比加法和減法需要更多時間，因此演算法設計人員會更多地關注它們。）

答案

操作的次數取決於操作的具體執行方式。

1. 行列式為 $-11$。進行行簡化需要一個樞軸，有兩個乘法（$-5/2$ 乘以 $2$ 加上 $5$，以及 $-5/2$ 乘以 $1$ 加上 $-3$)，對角線上的乘積還需要一次乘法。排列展開需要兩次乘法（$2$ 乘以 $-3$ 以及 $5$ 乘以 $1$）。
2. 行列式為 $-39$。計算操作次數是例行公事。
3. 行列式為 $4$。

問題 3

你能想出一個 $10\!\times \!10$ 陣列，讓你的計算機系統需要最長時間才能簡化？最短時間？

答案

一個開始的方法是使用 Octave 比較：det(rand(10));，與det(hilb(10));，與det(eye(10));，與det(zeroes(10));。你可以像這樣計時它們：tic(); det(rand(10)); toc().

問題 4

編寫剩下的 FORTRAN 程式，以直接實現透過高斯方法計算行列式。（不要測試零樞軸。）比較你程式碼的速度和你的計算機代數系統中使用的程式碼的速度。

答案

這是一個簡單的例子。

DO 5 ROW=1, N
PIVINV=1.0/A(ROW,ROW)
DO 10 I=ROW+1, N
DO 20 J=I, N
A(I,J)=A(I,J)-PIVINV*A(ROW,J)
20 CONTINUE
10 CONTINUE
5 CONTINUE

問題 5

FORTRAN 語言規範要求陣列“按列”儲存，也就是說，整個第一列連續儲存，然後是第二列，等等。給定的程式碼片段是否利用了這一點，或者它是否可以重寫以使其更快，透過利用計算機從連續位置獲取資料的速度更快這一事實？

答案

是的，因為 $J$ 在最內層迴圈中。