标签: sparse-matrix

我正在使用Gauss-Seidel方法编写稀疏矩阵求解器.通过剖析,我已经确定我的程序的大约一半时间花在解算器中.性能关键部分如下:

size_t ic = d_ny + 1, iw = d_ny, ie = d_ny + 2, is = 1, in = 2 * d_ny + 1;
for (size_t y = 1; y < d_ny - 1; ++y) {
    for (size_t x = 1; x < d_nx - 1; ++x) {
        d_x[ic] = d_b[ic]
                - d_w[ic] * d_x[iw] - d_e[ic] * d_x[ie]
                - d_s[ic] * d_x[is] - d_n[ic] * d_x[in];
        ++ic; ++iw; ++ie; ++is; ++in;
    }
    ic += 2; iw += 2; …

我有一个非常大的矩阵(100M行乘100M列),它有很多重复的值,彼此相邻.例如:

8 8 8 8 8 8 8 8 8 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 …

我正在使用R进行文本分类任务,并且我获得了一个文档项矩阵,其大小为22490×120,000(仅有400万个非零条目,小于1%的条目).现在我想通过利用PCA(主成分分析)来降低维数.遗憾的是,R无法处理这个巨大的矩阵,所以我将这个稀疏矩阵存储在"矩阵市场格式"的文件中,希望使用其他一些技术来做PCA.

所以任何人都可以给我一些有用库(无论编程语言)的提示,它可以轻松地用这个大规模矩阵做PCA,或者自己做一个简单的PCA,换句话说,首先计算协方差矩阵,然后计算协方差矩阵的特征值和特征向量.

我想要的是计算所有PC(120,000),并且只选择前N台PC,它们占90%的差异.显然,在这种情况下,我必须先给出一个阈值,将一些非常小的方差值设置为0(在协方差矩阵中),否则,协方差矩阵将不会稀疏,其大小将是120,000乘120,000,这是用一台机器无法处理.此外,负载(特征向量)将非常大,并且应以稀疏格式存储.

非常感谢您的帮助!

注意:我使用的是具有24GB RAM和8个CPU内核的机器.

我有一个50000字符串向量的列表,包含6000个独特字符串的各种组合.

目标:我想在"相对频率"(table(x)/length(x))中对它们进行转换,并将它们存储在稀疏矩阵中.低内存消耗比速度更重要.目前记忆是瓶颈.(即使源数据大约有~50 mb,目标格式的数据~10mb - >转换似乎效率低下,......)

生成样本数据

dims <- c(50000, 6000)
nms <- paste0("A", 1:dims[2])
lengths <- sample(5:30, dims[1], replace = T)
data <- lapply(lengths, sample, x = nms, replace = T)

可能的尝试:

1)sapply()简化为稀疏矩阵？

library(Matrix)  
sparseRow <- function(stringVec){
  relFreq <- c(table(factor(stringVec, levels = nms)) / length(stringVec))
  Matrix(relFreq, 1, dims[2], sparse = TRUE)
}
sparseRows <- sapply(data[1:5], sparseRow)
sparseMat <- do.call(rbind, sparseRows)

问题:我的瓶颈似乎是sparseRows因为行没有直接组合成稀疏矩阵.(如果我在完整样本上运行上面的代码,我得到一个Error: cannot allocate vector of size 194 Kb Error during wrapup: memory exhausted (limit …

每过一段时间,我去操纵csr_matrix,但我总是忘了怎样的参数indices,并indptr共同构建一个稀疏矩阵.

我正在寻找一个清晰直观的解释,说明在使用符号定义稀疏矩阵时如何与参数和参数进行indptr交互.dataindicescsr_matrix((data, indices, indptr), [shape=(M, N)])

我可以从scipy文档中看到该data参数包含所有非零数据,并且该indices参数包含与该数据相关联的列(因此,在文档中给出的示例中indices等于col).但是我们怎么能用清晰的语言解释indptr参数呢？

我一直在玩康威的生命游戏,最近发现了一些非常快速的实现,如Hashlife和Golly.(在这里下载Golly - http://golly.sourceforge.net/)

我无法理解的一件事是编码器如何实现无限网格？我们无法保持无限的任何东西,如果你跑得很好并且让几个滑翔机飞过边缘,等待几分钟然后向外缩放,你会看到滑翔机仍在那里空间逃跑,所以在神的名字中如何以编程方式处理这个无限的概念？是否存在记录良好的模式或什么？

非常感谢

如何scipy.sparse根据元素将矩阵提升为幂？numpy.power根据其手册,应该这样做,但它在稀疏矩阵上失败:

>>> X
<1353x32100 sparse matrix of type '<type 'numpy.float64'>'
        with 144875 stored elements in Compressed Sparse Row format>

>>> np.power(X, 2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File ".../scipy/sparse/base.py", line 347, in __pow__
    raise TypeError('matrix is not square')
TypeError: matrix is not square

同样的问题X**2.转换为密集阵列有效,但浪费了宝贵的秒数.

我有同样的问题np.multiply,我用稀疏矩阵的multiply方法解决了,但似乎没有pow方法.

最近一直在阅读Hadoop和HBase,并且遇到了这个术语 -

HBase是一个开源,分布式,稀疏,面向列的存储......

稀疏是什么意思？它与稀疏矩阵有关吗？我猜它是可以有效存储的数据类型的属性,因此,想要了解更多.

还有一个称为密​​度阵列的对应物.这是什么意思？我做了一些搜索,但没有得到准确的信息.

我正在努力实现以下等式:

X =(Y.T * Y + Y.T * C * Y) ^ -1

Y是(nxf)矩阵,C是(nxn)对角线; n约为300k,f在100到200之间变化.作为优化过程的一部分,这个等式将使用近1亿次,因此必须非常快速地处理.

Y是随机初始化的,C是一个非常稀疏的矩阵,对角线上300k中只有少数数字与0不同.由于Numpy的对角线函数创建了密集矩阵,我创建了C作为稀疏csr矩阵.但是当试图解决方程式的第一部分时:

r = dot(C, Y)

由于内存限制,计算机崩溃.我决定然后尝试将Y转换为csr_matrix并进行相同的操作:

r = dot(C, Ysparse)

这种方法耗时1.38毫秒.但是这个解决方案有点"棘手",因为我使用稀疏矩阵来存储密集的矩阵,我想知道它真的有多高效.

所以我的问题是,是否有一些方法可以将稀疏的C和密集的Y相乘,而不必将Y变为稀疏并提高性能？如果不知何故C可以表示为对角线密集而不消耗大量内存,这可能会导致非常有效的性能,但我不知道这是否可行.

我感谢您的帮助!