矩陣計算(一):基礎數值算法

什麼是矩陣的數值計算方法?

矩陣計算都是建立在線性代數運算的層次之上的,例如點積(Dot Product)涉及加法和乘法的標量運算,矩陣向量乘法(Matrix-Vector Multiplication)由點積組成,矩陣-矩陣乘法(Matrix-Matrix Multiplication)相當於矩陣-向量乘積的集合。所有這些操作都可以用算法的形式或線性代數的語言來描述。

本文的主要目的是介紹幾種常見矩陣運算過程的數值計算形式,這種方式是從計算機計算角度去看整個過程,更重視計算的復雜程度。

幾種基礎且常見矩陣運算的數值算法

兩個向量的點積就是分別把兩個向量的對應元素相乘然後求和,舉個例子:

a= begin{bmatrix} 1quad2 end{bmatrix}^{T}b= begin{bmatrix} 3quad4 end{bmatrix}^{T} ,則 a^{T}b= begin{bmatrix} 1&2\ end{bmatrix} begin{bmatrix} 3\4 end{bmatrix} =1times3+2times4=11

在計算機中,如果有向量 x、yin R^{n} ,那麼它們倆點積 c=x^{T} y 的計算方式如下:

從上圖的算法中可以清楚地看出,兩個 n 維向量的點積包括 n 次乘法和 n 次加法,省去常數項以後,可得點積運算的計算復雜度為 O(n) ,這表明點積的計算復雜度與向量的規模大小成正比。

兩個向量的外積和兩個向量的內積過程是相反的,內積的過程會使向量的維度降低,而外積則是一個升維操作,舉個例子:

begin{bmatrix} 1\2\ 3end{bmatrix} begin{bmatrix} 4&5 end{bmatrix}=begin{bmatrix} 4&5\ 8&10\ 12&15 end{bmatrix}

本來的兩個向量都是一維向量,經過外積操作以後,變成瞭一個二維矩陣。外積具體的物理意義往後會有文章進行專門的講解,這裡我們還是主要關註其計算過程。

如果 Ain R^{mtimes n}xin R^{m}yin R^{n} ,那麼兩個向量的外積 A=x y^{T} 算法如下:

整個過程經歷瞭 mtimes n 次循環過程,其算法復雜度為 O(mn)

矩陣和向量的乘法可以從兩個角度去看。一是看作是由多個向量的點積操作的集合;二是可以看成矩陣列的線性組合。

  • 點積操作的集合

說矩陣與向量乘積是點積操作集合的原因是,在這個過程中每一步都在進行著點積的操作,先看個例子:

begin{bmatrix} 1&2\ 3&4\ 5&6 end{bmatrix} begin{bmatrix} 7\8 end{bmatrix}= begin{bmatrix} 1times7+2times8\ 3times7+4times8\ 5times7+6times8 end{bmatrix} =begin{bmatrix} 23\53\83 end{bmatrix}

這個例子中,一共進行瞭三次點積的操作,分別是 begin{bmatrix} 1&2\ end{bmatrix} begin{bmatrix} 7\8 end{bmatrix}begin{bmatrix} 3&4\ end{bmatrix} begin{bmatrix} 7\8 end{bmatrix}begin{bmatrix} 5&6\ end{bmatrix} begin{bmatrix} 7\8 end{bmatrix} ,所以我們稱它是點積操作的集合。

如果有矩陣 Ain R^{mtimes n} ,向量 xin R^{n} ,那麼矩陣和向量的乘積 y=Ax 計算方式如下:

顯而易見,該算法的復雜度為 O(mn) ,因為它需要對矩陣的每一行都進行一次點積操作。

  • 矩陣列的線性組合

現在我們用另一種角度去看矩陣和向量積的運算,還是剛才那個例子,我們可以換種計算方式,例如:

begin{bmatrix} 1&2\ 3&4\ 5&6 end{bmatrix} begin{bmatrix} 7\8 end{bmatrix}= 7timesbegin{bmatrix} 1\ 3\ 5end{bmatrix}+8timesbegin{bmatrix}2\4\6end{bmatrix} =begin{bmatrix} 23\53\83 end{bmatrix}

這種方式就是矩陣列的線性組合。它其實是一種分解的思想,在後面的矩陣乘法中還會見到類似的分解。當然,後續我們也會對這種做法的物理意義進行探討。接下來同樣來看一下這個過程的計算方法:

利用矩陣列的線性組合的形式去計算矩陣向量的乘積,隻是換瞭一種角度去看待這個問題,但算法復雜度並沒有發生改變,依然是 O(mn)

在上面的介紹中,我們主要介紹瞭三種不同的形式:內積、外積和列的線性組合。接下來,我們把這三種形式應用到矩陣乘法上,從不同角度去看矩陣乘法。

  • 內積角度

從內積的角度看矩陣乘法,其實就是說新矩陣的每一個元素都是由內積操作得到的:

begin{bmatrix} 1&2\ 3&4end{bmatrix} begin{bmatrix} 5&6\ 7&8end{bmatrix} = begin{bmatrix} 1times 5+2times7&1times6+2times8\ 3times 5+4times7&3times6+4times8end{bmatrix}

整個矩陣計算的過程其實就是計算 begin{bmatrix} 1&2\ end{bmatrix} begin{bmatrix} 5\7 end{bmatrix}begin{bmatrix} 1&2\ end{bmatrix} begin{bmatrix} 6\8 end{bmatrix}begin{bmatrix} 3&4\ end{bmatrix} begin{bmatrix} 5\7 end{bmatrix}begin{bmatrix} 3&4\ end{bmatrix} begin{bmatrix} 6\8 end{bmatrix} 這四個內積。

  • 外積角度

向量的外積運算在前文有過介紹,這裡我們直接給出矩陣乘法的外積形式:

begin{bmatrix} 1&2\ 3&4end{bmatrix} begin{bmatrix} 5&6\ 7&8end{bmatrix} =begin{bmatrix} 1\ 3end{bmatrix}begin{bmatrix} 5&6end{bmatrix}+ begin{bmatrix} 2\ 4end{bmatrix}begin{bmatrix} 7&8end{bmatrix}

這種正向的過程並不是外積帶給我們的最大好處,相反逆向的過程對我們的啟發更大,它在矩陣分解中發揮著重要的作用。

  • 列的線性組合角度

在這個視角中,新矩陣的每一列都被看作是一個線性組合的形式:

begin{bmatrix} 1&2\ 3&4end{bmatrix} begin{bmatrix} 5&6\ 7&8end{bmatrix} =begin{bmatrix} 5begin{bmatrix} 1\ 3end{bmatrix}+7begin{bmatrix} 2\ 4end{bmatrix}, 6begin{bmatrix} 1\ 3end{bmatrix}+8begin{bmatrix} 2\ 4end{bmatrix}end{bmatrix}

看完瞭矩陣乘法的三種形式,接下來我們還是去關註一下具體的計算過程。

如果有矩陣 Ain R^{mtimes r}Bin R^{ rtimes n}Cin R^{mtimes n}C 為零矩陣,那麼矩陣 C=AB 計算過程如下:

這種計算方式的復雜度為 O(mnr) 。算法中的每個循環索引都有特定的角色(下標 i 表示行, j 表示列, k 表示點積)。然而,循環的順序是任意的。

FLOPs

量化與計算相關工作量的一種方法是計算運行次數,即 flop 。計算機每運行一次四則運算(加法、減法、乘法或者除法中的一種),都叫做進行瞭一次 flop 。例如,在矩陣乘法中的核心步驟:

C(i,j)=C(i,j)+A(i,k)B(k,j)

該步驟包含瞭一次加法和一次乘法,所以這個步驟進行瞭兩次 flop 。如果 Ain R^{mtimes r}Bin R^{ rtimes n} ,那麼這個語句將會被執行 mnr 次,總的執行次數就是 2mnr 。下表總結瞭常見矩陣運算所需要進行的 flop 次數。

這就是本文的全部,接下來還會繼續更新矩陣計算的相關內容!!!!

赞(0)