如何有效地构造一个大型SparseArray？包这个？

html5 • • 问答 • 38 阅读

问题

Julia 是否有一种有效的方法从给定的条目列表 (u,v,w)构建一个巨大的稀疏矩阵，其中一些可以具有相同的位置(u,v)，在这种情况下，它们的权重 w 必须是总和。因此u,v,w是输入向量，我希望创建一个w[i]在 position 处具有值的稀疏矩阵u[i],v[i]。例如，Mathematica 代码

n=10^6;   m=500*n;   
u=RandomInteger[{1,n},m];   
v=RandomInteger[{1,n},m];   
w=RandomInteger[{-9, 9}, m];   AbsoluteTiming[
SetSystemOptions["SparseArrayOptions"->{"TreatRepeatedEntries"->1}]; 
a= SparseArray[{u,v}[Transpose] -> w, {n,n}]; ]

需要 135 秒和 60GB 的 RAM。等效的 Python 代码

import scipy.sparse as sp   
import numpy as np
import time
def ti(): return time.perf_counter() 
n=10**6; m=500*n;
u=np.random.randint(0,n,size=m);            
v=np.random.randint(0,n,size=m);            
w=np.random.randint(-9,10,size=m); t0=ti(); 
a=sp.csr_matrix((w,(u,v)),shape=(n,n),dtype=int); t1=ti(); print(t1-t0)

需要 36 秒和 20GB，但不支持 (2)。等效的 Julia 代码

using SparseArrays;
m=n=10^6; r=500*n;   
u=rand(1:m,r);   
v=rand(1:n,r);   
w=rand(-9:9,r);
function f() a=sparse(u,v,w,m,n,+); end;   
@time f()

需要 155 秒和 26GB（@time 宏错误地报告它只使用了 15GB）。

有没有办法使这种结构更有效？是否有任何Julia 软件包在这方面做得更好？

背景

我为线性代数和同调代数计算创建了一个包。我在 Mathematica 中做到了，因为SparseArray实现 (0) 有

  1. 非常高效（快速且低 RAM 使用率），
  2. 支持精确分数作为矩阵条目。
  3. 支持多项式作为矩阵项。

然而，它不是

  1. 并行化
  2. 开源
  3. 启用 GPU 或集群。

出于各种长期原因，我正在考虑迁移到不同的编程语言。

我试过 Python SciPy.sparse，但它不满足（2）。我不确定 C++ 库是否支持 (2)。作为测试，我尝试对大小为 10^9 的浮点数组进行排序，并比较 Mathematica、Pythonnumpy和 Julia的性能ThreadsX。后者给我留下了难以置信的印象（比 numpy 快 3 倍，比 Mathematica 快 10 倍）。我正在考虑迁移到 Julia，但我希望首先确保我的库会比在 Mathematica 中表现得更好。

PS我怎样才能实现我的f()上面在调用时不打印/输出任何东西？

PPS 我也在这里问过这个问题。

以上是如何有效地构造一个大型SparseArray？包这个？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>