.png){kind=icon}
返回
Complexity of Linear Operators
.png){kind=icon}
PRE
AI
DOI：10.4086/toc.2025.v021a009.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
设A为一个n×n的0/1矩阵，其中包含z个0和u个1，并设x为定义在半群(S, o)上的n维形式变量向量。计算线性算子Ax需要多少次半群运算？使用O(u)次半群运算即可轻松计算Ax。本文主要研究的问题是：能否使用O(z)次半群运算计算Ax？对于半群是可交换的情况，我们给出了一个O(z)上界构造性证明。这表明在可交换设置下，稀疏矩阵的补矩阵可以被与稀疏矩阵一样高效地处理，尽管对应的算法更为复杂。这涵盖了布尔半群和热带半群等具有广泛应用的情况，例如在图论中。另一方面，我们证明了这在一般情况下是不可能的：对于忠实非交换半群，存在一个n×n的0/1矩阵，其每一行恰好有两个0（因此z=2n），其复杂度为O(na(n))，其中a(n)是反阿克曼函数。作为所提出线性规模构造的一个简单应用，我们展示了如何在一个矩阵为0/1矩阵且包含(=)个0（即稀疏矩阵的补矩阵）的情况下，在O(n²)时间内完成两个n×n矩阵在任意半环上的乘法。
Keyword:
algorithms
linear operators
commutativity
range queries
circuit complexity
期刊
T
IF:
0.7
论文数:
10
被引数:
0
机构
引用论文
暂无论文信息