是否有比O(N²)更好的算法来确定矩阵是否对称？

Question

算法要求

输入是一个M大小的任意方阵N×N,只适合内存.

算法的输出必须是trueif if M[i,j] = M[j,i]all j?i,false否则.

明显的解决方案

1. 检查转置是否等于矩阵本身(M^T=M).最容易在许多环境中编程,但(通常)消耗两倍的内存,并且需要N²比较最坏的情况.因此,这是O(N²)并具有高峰值存储器.

2. 检查下三角形部分是否等于上三角形部分.当然,算法返回发现的第一个不等式.这将使最坏的情况(最坏的情况是,矩阵确实是对称的)需要N²/2 - N比较,因为不需要检查对角线.因此虽然它比选项1好,但它仍然是O(N²).

题

虽然很难看出它是如何可能的(N²所有元素都必须以某种方式进行比较),是否有一个算法执行此检查比O(N²)更好？

或者,如果有证据表明这种算法不存在:如何最有效地为多核CPU(Intel或AMD)实现这一点,同时考虑缓存友好性,最佳分支预测,其他特定于编译器的事情.专业化等？

这个问题主要源于学术兴趣,尽管我认为如果矩阵描述线性系统,实际应用可以确定使用什么求解器AX=b...

Answer 1

由于您必须检查除对角线以外的所有元素,因此复杂度IMO不能优于O(n ^ 2).

Answer 2

对于密集矩阵,答案是明确的"否",因为任何未经检查的(非对角线)元素可能与它们的转置对应元素不同.

对于稀疏矩阵的标准表示,相同的推理表明通常不能比输入大小做得更好.

但是,相同的推理不适用于任意矩阵表示.例如,您可以存储矩阵的对称和反对称分量的稀疏表示,通过检查反对称元素是否具有任何组件,可以在O(1)时间内轻松检查对称性.