作者doom8199 (～口卡口卡 修～)
看板MATLAB
標題Re: [問題] 大量矩陣算行列式值
時間Sat Mar 15 14:46:27 2014
※ 引述《sky0204b (北腿爹爹)》之銘言：
: 各位大大,
: 小弟是matlab新手,
: 現在有個問題需要處理,
: 問題如下
: 有30組8維向量,
: 我要從30組中任取八組,
: 組成一個8x8的矩陣,並且算它的行列式值,
: 並找出所有組合中最大的,
: 所以資料量非常大,C30取8...
: 不知道matlab有沒有比較快的解法呢?
: 大家可以來討論看看!
---
可以把這個問題抽象化:
在 |R^8 中，想從 30個向量挑選 其中8個向量
使得 8個向量所張開的 "平行多面體體積" 為最大
若原 po 不介意使用 greedy alg.
可以這樣子做:
考慮 V = {v1, v2, ..., v30} in |R^8
且定義由 S = {v_i1, v_i2, ..., v_in} 所展開的平行多面體"體積"
為 V(S) := sqrt[(A^T)A]
其中 A = [v_i1 | v_i2 |...| v_in] , n <= 8
<1> 先從 30 組挑選其中兩組 S2 = {v_i1, v_i2}
使得 V(S2) 最大
<2> 從 剩下的 28 組挑選其中一個向量 v_i3
使得 V(S3) 最大， 其中 S3 = S2 + {v_i3}
= {v_i1, v_i2, v_i3}
<3> 從 剩下的 27 組挑選其中一個向量 v_i4
使得 V(S4) 最大， 其中 S4 = S3 + {v_i4}
= {v_i1, v_i2, v_i3, v_i4}
一路算下來，就能得到 S8
----
當然這種算法不能保證 S8 是裏頭組出來的 determinant 最大
你可以由這個方向去改良演算法
除了這個
也能根據估計 determinant 的上下界來排除不必要的向量
(如 Hadamard's ineq.)
若你的向量有其它特殊性質 (如 2-norm = 1)
對這個問題的簡化應該也有幫助才是
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.61.82.125
1F：推 sky0204b:感謝大大回應!! 03/20 17:21