data-structures - "New Yale"稀疏矩阵格式的详细信息？

Question

有一些用 Fortran 语言编写的 Netlib 代码可以对稀疏矩阵执行转置和乘法。该库使用 Bank-Smith(某种程度上)、“老耶鲁”和“新耶鲁”格式。

不幸的是，我没能找到关于“新耶鲁”的更多细节。我实现了我认为符合描述的内容 given in the paper ，我可以适本地获取和设置条目。

但结果不正确，让我怀疑我是否实现了与论文中的描述相符但不是 Fortran 代码所期望的东西。

所以有几个问题:

行长度应该包括对角线条目吗？例如，如果您有 M=[1,1;0,1]，它看起来应该是这样的:

IJA = [3,4,4,1]
A   = [1,1,X,1] // where X=NULL

似乎如果对角线条目包含在行长度中，你会得到这样的东西:

IJA = [3,5,6,1]
A   = [1,1,X,1]

这没有多大意义，因为 IJA[2]=6 应该是 IJA/A 数组的大小，但它是论文看起来的样子说。

矩阵应该使用从 1 开始的索引吗？

毕竟是 Fortran 代码。也许我的 IJA 和 A 应该是这样的:

IJA = [4,5,5,2]
A   = [1,1,X,1] // still X=NULL

还有什么我想念的吗？

是的，这很含糊，但我把它放在那里，以防有人以前弄乱过这段代码，愿意自愿提供任何额外信息。其他任何人都可以随意忽略最后一个问题。

我知道这些问题可能看起来微不足道，但我认为也许一些 Fortran 人员可以为我提供一些见解。我不习惯在一个基于 one 的系统中思考，虽然我已经使用 f2c 将代码转换为 C，但它仍然像 Fortran 一样编写。

Answer 1

我看不出你是如何从那篇论文中推导出这些向量的。首先是旧耶鲁格式:

M = [7,16;0,-12]

然后，A 以行的形式包含 M 的所有非零值: A = [7,16,-12]

和IA存储每行第一个元素在A中的位置，JA存储所有值在A中的列索引A:

IA = [1,3,4]
JA = [1,2,2]

新格式:A 首先有对角线值，一个零，然后是剩余的非零元素(我放了 | 来阐明对角线和非零元素之间的分隔对角线):

A = [7,-12,0 | 16]

IA 和 JA 组合在 IJA 中，但据我从论文中得知，您需要考虑新的A 的排序(我已经放置了 | 以阐明 IA 和 JA 之间的分隔):

IJA = [1,2,3 | 2]

所以，应用到你的情况 M = [1,1;0,1]，我得到

A   = [1,1,0 | 1]
IJA = [1,2,3 | 2]

第一行的第一个元素是A中的第一个元素，第二行的第一个元素是A中的第二个元素，然后我把3 因为他们说一行的长度由 IA(I)-IA(I+1) 决定，所以我确保差值是 1。然后是非零非对角线元素的列索引，即 2。