Edison.X. Blog

開始前...

在自己下手刻 matrix library 前，請細思：

要自己刻的原因是什麼？因工作需求？因作業需求？還是純粹興趣？

思考完後，或許不需要再看此系列文，反之要做的事情可能是，

去評估一套適合解決手邊問題之 library。

不易解之問題

矩陣問題在線性代數裡佔了不少篇幅，也有不少問題以矩陣模式解之較為合適。

然而在計算機領域，實際解決矩陣問題時，有不少實際狀況必須考量，

較為有名的幾個問題，其中在 CS 領域裡筆者認為「不算好解」的會在後面打 *

另在 (7), (8) 是實作面較為麻煩之事。

(1) 乘法效率 *

如何低於 O(n^3)

(2) 乘法效率 *

一串 matrix 相乘 (如 ABCD) ，相乘次序為何 (如 AB(CD) , A(BC)D )，才能使得在結果正確情況下，乘法次數最少、效率最高？

(3) ill-condition 問題

消除 ill-condition ，這算是較簡單解決之問題。

(4) 消去法效率

消去法種類必須如何低於 O(n^3)

(5) 大型矩陣問題 *

一些較大問題變數個數不小，若在記憶體容量不足之情況下，是否有辦法將大型矩陣切成數個小型矩陣再進行求解動作。

(6) 稀疏矩陣問題 *

稀疏矩陣在資料結構之表示法並不難，難的是如何使其執行效率高。

(7) 如何包成 friendly use class ?

實際包成 class 後發現主要幾個問題點：該用 shallow copy / deep copy、繼承架構該如何設計 、包成 class 後實作上會有不少 side effect 影響效率 (特別是隱喻之 Constructor 便會耗去不少時間) 等，在考量 friendly、effective、multi-thread 情況下，這問題會愈變愈複雜。

(8) 例外處理

目前絕大多數之數值分析在探討時任何 matrix 問題確實會做些基本之例外處理，但一些問題之例外處理並不容易完全處理掉。

Free library

然而實際上也有不少免費 matrix library 已提供，如

1. Matrix Template Library 4 (MLT4)  * (不少人用過覺得不錯)

2. C++ Matrix Template Class Library

3. Matrix Expression Templates (MET)

4. Sparse Lib++ * (少數專門處理稀疏矩陣)

5. CAM Matrix / Vector / Array Classes

6. Netmat

7. High Mat C++

(聲明，筆者沒用過任何 matrix library，據說 MLT4 還不錯)

其他有些 Graphic Library ( OpenGL  還是 OpenCV ) 可能也有提供，

也可能有些 library 效能更佳沒紀錄到，也可能有些是 non-Free，

此處便不一一列舉。