我们有一个存储稀疏矩阵的应用程序。该矩阵的条目主要存在于矩阵的主对角线周围。我想知道是否有任何有效的算法（或现有的库）可以有效地处理这种稀疏矩阵？优选地，这将是一个通用实现，其中每个矩阵条目可以是用户定义的类型。
针对问题/回复进行编辑：
当我说主要围绕主对角线时，我的意思是大多数矩阵的特征将是大多数条目都聚集在主对角线之外，但是靠近对角线的地方可能有零值，远离对角线的地方可能有非零值对角线。我想要对这里的“大多数”情况有效的东西。
我会用这个做什么？我需要能够有效地访问行中的所有值或列中的所有值。存储的值将是布尔值。一个例子是：
这都是以前用链表完成的，但实现起来非常混乱。我希望使用稀疏矩阵可以改进算法，但事实证明很难找到“正确”类型的稀疏矩阵算法。
ps 感谢您迄今为止的回复
您可以使用基于单元格的 [row,col] 的索引。由于数据在对角线上，将行索引和相关列索引与数据一起存储的典型方法不是最佳的。这是一些您可以用来执行此操作的代码：
public class SparseMatrix<T>
{
public int Width { get; private set; }
public int Height { get; private set; }
public long Size { get; private set; }
private Dictionary<long, T> _cells = new Dictionary<long, T>();
public SparseMatrix(int w, int h)
{
this.Width = w;
this.Height = h;
this.Size = w * h;
}
public bool IsCellEmpty(int row, int col)
{
long index = row * Width + col;
return _cells.ContainsKey(index);
}
public T this[int row, int col]
{
get
{
long index = row * Width + col;
T result;
_cells.TryGetValue(index, out result);
return result;
}
set
{
long index = row * Width + col;
_cells[index] = value;
}
}
}
static void Main()
{
var sm = new SparseMatrix<int>(512, 512);
sm[42, 42] = 42;
int val1 = sm[13, 13];
int val2 = sm[42, 42];
Console.WriteLine("VAL1 = " + val1); // prints out 0
Console.WriteLine("VAL2 = " + val2); // prints out 42
Console.ReadLine();
}
请注意，当 T 是结构时，您可能必须调用 IsCellEmpty，因为获取单元格的内容不会为空，并且将具有该类型的默认值。您还可以扩展代码以根据Size属性和_cells.Count.
编辑：
好吧，如果您对速度感兴趣，您可以权衡空间与速度。与其只有一本字典，不如拥有三本！它使您的空间增加了三倍，但它使以您想要的任何方式进行枚举变得非常容易。这是一些新的代码，表明：
public class SparseMatrix<T>
{
public int Width { get; private set; }
public int Height { get; private set; }
public long MaxSize { get; private set; }
public long Count { get { return _cells.Count; } }
private Dictionary<long, T> _cells = new Dictionary<long, T>();
private Dictionary<int, Dictionary<int, T>> _rows =
new Dictionary<int, Dictionary<int, T>>();
private Dictionary<int, Dictionary<int, T>> _columns =
new Dictionary<int, Dictionary<int, T>>();
public SparseMatrix(int w, int h)
{
this.Width = w;
this.Height = h;
this.MaxSize = w * h;
}
public bool IsCellEmpty(int row, int col)
{
long index = row * Width + col;
return _cells.ContainsKey(index);
}
public T this[int row, int col]
{
get
{
long index = row * Width + col;
T result;
_cells.TryGetValue(index, out result);
return result;
}
set
{
long index = row * Width + col;
_cells[index] = value;
UpdateValue(col, row, _columns, value);
UpdateValue(row, col, _rows, value);
}
}
private void UpdateValue(int index1, int index2,
Dictionary<int, Dictionary<int, T>> parent, T value)
{
Dictionary<int, T> dict;
if (!parent.TryGetValue(index1, out dict))
{
parent[index2] = dict = new Dictionary<int, T>();
}
dict[index2] = value;
}
}
如果要遍历所有条目，请使用_cells. 如果您想要给定列的所有行，请使用_columns. 如果您想要给定行中的所有列，请使用_rows.
如果您想按排序顺序进行迭代，您可以开始将 LINQ 添加到组合中和/或使用带有封装条目的内部类的排序列表（它必须存储行或列并实现IComparable<T>排序才能工作） .
我想一个Dictionary<int, Dictionary<int, object >>就足够了。
我没有使用它，但Nmath Matrix处理这些（不是免费的）。
此外，.NET 的极限优化数值库（不是免费的）。
这是一个免费的：Math.NET 项目（特别是MathNet.Numerics.LinearAlgebra.Sparse 命名空间）
这里有两个问题：
“主要围绕主对角线”太模糊了。如果元素位于带中，则使用带本身的带状存储，作为偏离主对角线的向量。如果元素随机分散在主对角线附近，则要么使用带状形式，其中可能在带状部中包含一些零，要么使用纯稀疏形式，仅存储元素及其在数组中的位置。
你将如何处理矩阵？如果您的目标仅仅是高效存储，那么带状表单将是高效的，可以快速访问任何元素。如果您将使用矩阵进行线性代数，但不会超过矩阵向量的乘积，那么带状形式仍然可以出色地工作。如果您使用矩阵矩阵乘法或矩阵分解，其中填充成为问题，那么纯稀疏形式可能更合适。例如，两个带状矩阵的乘积将有额外的带，因此两个三对角矩阵的乘积将是五对角矩阵。对于因式分解，重新排序有时有助于最小化填充。（AMD 是一种选择，Approximate Minimum Degree permutation，但还有其他方案。）
这是通用数据结构模式的列表。每种都有其优点和缺点，并且适用于出现稀疏矩阵的稍微不同类型的问题。您可能希望在现有数据结构（例如 List<> 和 Dictionary<> ）之上实现它们。
我认为这可以通过使用一个持有普通数组的类来完成，保存在矩阵行之间应用的水平偏移量并定义一行的条带，例如有效条目的数量。因此，对于仅定义对角线和两个相邻元素的大型矩阵，您将创建一个 3 * 行数的数组并将 3 存储为条带宽度。偏移量取决于矩阵的大小。
我不知道有什么免费的已经这样做了。