開始前...

 

在自己下手刻 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,

此處便不一一列舉。

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()