Java Vector inner products

Question

我有一个m维向量的数组列表(存储为简单数组)v1, v2 ... vn.

我必须重复计算我从这些向量中选择的两个向量之间的内积

一种方法是在它的所有组件中使用一个简单的for循环。

double sum=0;
for(int i=0; i<m; i++)
    sum+=v1[i]*v2[i];

这几乎是我打算在我的数据上执行的唯一的线性代数操作。

1. 导入像JAMA或la4j这样的线性库，将所有内容存储为矩阵，并计算内部乘积会更有效吗?(这些甚至不是大的矩阵乘法，只是一维向量之间的内积)

2. 如何la4j(等)实现点积?难道它不会遍历每个索引并将每个组件对相乘吗?

Answer 1

la4j是开源的，看一下代码。使用AbstractVector的内部积比您自己的代码效率低，因为它实例化了额外的操作对象，这里是OoPlaceInnerProduct。

然而:在大多数情况下，我仍然更喜欢使用现有的、经过良好测试的向量数学包，而不是实现我自己的。(Knuth:"我们应该忘记小效率，大约97%的时间:过早优化是万恶之源")

注意多线程也没有帮助。即使是高效的LAPACK包也使用与您的相同的代码。

Answer 2

关于la4j库:即将发布的0.5.0版本使用轻量级稀疏迭代器，因此您不应该担心在稀疏向量中迭代零值。下面是API示例

Vector a = new BasicVector(...); // dense
Vector b = new CompressedVector(...); // sparse
double dot = a.innerProduct(b);

可以组合任何可能的对:sparse-dense, sparse-sparse, dense-dense, dense-sparse。la4j库将始终根据您的数据使用最有效的算法。

Answer 3

如果你想计算所有的内积，我建议这样做:在矩阵A中，将向量存储为行，在矩阵B中，将它们存储为cols。那么在A*B中，你将得到位置(i,j) v_i和v_j的内积。

技巧在于普通的矩阵乘法需要n^3的时间，但一些聪明的算法有更有效的方法，但只适用于~ 30个或更多的向量