作者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