问题标签 [sparse-matrix]

我试图找出解决五对角矩阵的最佳方法。有什么比高斯消除更快的吗？

我正在实现一个模板化的 sparse_vector 类。它就像一个向量，但它只存储与其默认构造值不同的元素。

因此，sparse_vector 将为值不是 T() 的所有索引存储延迟排序的索引值对。

我的实现基于数字库中现有的稀疏向量——尽管我的也将处理非数字类型 T。我看着boost::numeric::ublas::coordinate_vector和eigen::SparseVector。

两家店：

他们为什么不简单地使用

我的主要问题是这两个系统的优缺点是什么，最终哪个更好？

对的向量为您管理 size_ 和 capacity_，并简化了随附的迭代器类；它也有一个内存块而不是两个，因此它会导致一半的重新分配，并且可能具有更好的引用局部性。

另一种解决方案可能会更快地搜索，因为在搜索期间缓存行仅填充索引数据。如果 T 是 8 字节类型，也可能有一些对齐优势？

在我看来，对向量是更好的解决方案，但两个容器都选择了另一个解决方案。为什么？

首先，我是一个 Java 初学者，所以我不确定这是否可能！基本上我有一个巨大的（3+百万）关系数据数据源（即A是B+C+D的朋友，B是D+G+Z的朋友（但不是A - 即不互惠的）等），我想要在这个（不一定是连接的）有向图中找到每个循环。

我找到了Finding all cycles in graph的线程，这让我想到了Donald Johnson 的（基本）循环查找算法，至少从表面上看，它看起来像我所追求的（我要试试当我周二回到工作岗位时 - 认为同时询问不会有什么坏处！）。

我快速浏览了Johnson算法的Java实现代码（在那个线程中），看起来关系矩阵是第一步，所以我想我的问题是：

a) Java 是否能够处理 3+million*3+million 矩阵？（计划用二元稀疏矩阵表示 A-friends-with-B）

b) 我需要找到每个连通子图作为我的第一个问题，还是循环查找算法会处理不相交的数据？

c) 这实际上是解决问题的合适方法吗？我对“基本”周期的理解是，在下图中，不是选择 ABCDEF，而是选择 ABF、BCD 等，但这并不是世界末日。

d) 如有必要，我可以通过加强关系中的相互性来简化问题 - 即 A-friends-with-B <==> B-friends-with-A，如果真的有必要，我可以减少数据大小，但是实际上，它总是在 100 万左右。

z) 这是 P 任务还是 NP 任务？！我咬得比我能咀嚼的多吗？

谢谢大家，任何帮助表示赞赏！安迪

这个很棒的 SO 答案指向了一个很好的稀疏求解器Ax=b，但是我有这样的限制，即x每个元素x都是.>=0<=N

此外，A它很大（大约 2e6x2e6），但<=4每行元素非常稀疏。

有什么想法/建议吗？我正在寻找类似 MATLABlsqlin但具有巨大稀疏矩阵的东西。

我本质上是在尝试解决稀疏矩阵上的大规模有界变量最小二乘问题：

编辑： 在CVX中：

我必须创建一个分辨率非常大的图像，但是图像相对“稀疏”，只有图像中的某些区域需要绘制。

例如下面的代码

我最后创建的 PNG 图像只有大约 200~300 MB。

问题是如何避免在开始时创建 5GB BufferedImage？我确实需要一个大尺寸的图像，但颜色信息非常稀疏。

BufferedImage 是否有任何 Stream 以便它不会占用太多内存？

我正在尝试在一个非常大的矩阵上进行一些 k 均值聚类。

该矩阵大约有 500000 行 x 4000 列，但非常稀疏（每行只有几个“1”值）。

整个东西不适合内存，所以我把它转换成一个稀疏的 ARFF 文件。但是 R 显然无法读取稀疏的 ARFF 文件格式。我也将数据作为纯 CSV 文件。

R 中是否有任何包可用于有效加载此类稀疏矩阵？然后，我将使用 cluster 包中的常规 k-means 算法继续进行。

非常感谢

我有一个非常大的矩阵（100M 行 x 100M 列），其中有很多相邻的重复值。例如：

我想要一个数据结构/算法来尽可能紧凑地存储这样的矩阵。例如，上面的矩阵应该只占用 O(1) 空间（即使矩阵被拉伸到任意大），因为只有恒定数量的矩形区域，每个区域只有一个值。

重复发生在行和下列中，因此逐行压缩矩阵的简单方法还不够好。（这将需要最少 O(num_rows) 空间来存储任何矩阵。）

矩阵的表示也需要逐行访问，以便我可以对列向量进行矩阵乘法。

我正在研究解决一个 PDE 问题，并且 3D 离散域可以在 6 个边界中的每一个上具有不同的边界条件（或全部相同）。

将此稀疏矩阵转换为压缩格式的最佳方法是什么？企业社会责任会是我在这里唯一的选择吗？我考虑过使用 ellpack，但我不确定它是如何改变边界条件的。

考虑 3d 空间的 2D 矩阵表示......它将主要以对角线为主，有 7 个对角线，但这些对角线可能会沿着边界发生变化。似乎我不能使用存储值的格式，以及每次都相同的对角线偏移量。

显然，我试图将这个问题设置为对我的 CG 求解器更加缓存友好，它正在做很多向量矩阵乘法

我有一个表示 3D 矩形空间的稀疏矩阵。沿着一些边界，我知道价值将是什么（它是一个常数）。其他边界可能是反射的、差异的等。

我是否应该将问题设置为好像所有边界都是微分，然后返回并将解向量 b 中的节点设置为常数？

谢谢！

我认为这是一个很常见的问题，但我不知道这个过程叫什么，所以我会用一个例子来描述它。这个概念是我想将一个稀疏数据集加入一个完整的系列，例如一周中的几天、一年中的几个月或任何有序集（例如，用于排名）。稀疏数据中的空位置将与完整系列一起显示为 NULL。

假设我在 SQL Server 中运行以下查询以了解月销售额。

但是，如果仅在今年 5 月和 8 月发生销售，则返回结果将如下所示：

我希望我的返回结果集如下所示：

我知道这样做的唯一方法是：

有没有更好的方法来创建完整的日期和字母数字系列来加入数据？这叫什么？

谢谢！