We present a simple matrix multiplication algorithm that multiplies two input matrices with rows (in one matrix) and columns (in the other matrix) within a small diameter d (distances are measured using the Hamming distance). This algorithm runs in time O(dn~2) for matrices of size n × n. We then propose a more general clustering-based matrix multiplication algorithm. For a given integer k ≤ n, this algorithm first uses a clustering algorithm that places rows of one input matrix and separately columns of the other input matrix into k clusters with approximately the smallest possible radius (cluster size) s (within a factor of two of the minimum possible). Second, it uses our first algorithm as a subroutine to multiply the original input matrices. We have implemented this algorithm. The time complexity of this implementation is O((k + s)n~2). We also describe how to achieve O((log k + s)n~2 + k~2n) worst case time complexity.
展开▼
机译：我们介绍了一种简单的矩阵乘法算法，其乘以来自行（在一个矩阵中）的两个输入矩阵（在一个矩阵中）和小直径D内的列（在另一个矩阵中）（使用汉明距离测量距离）。该算法在尺寸n×n的矩阵中运行时间O（DN〜2）。然后，我们提出了一种更通用的基于聚类的矩阵乘法算法。对于给定的整数k≤n，该算法首先使用群集算法，该群集算法将一个输入矩阵的行和其他输入矩阵的分别与大约最小可能的半径（簇大小）S（簇大小）（在两个倍数内）最低可能）。其次，它使用我们的第一算法作为子程序来乘以原始输入矩阵。我们已经实施了该算法。该实现的时间复杂性是O（（k + s）n〜2）。我们还描述了如何实现O（（log k + s）n〜2 + k〜2n）最坏情况的时间复杂性。
展开▼
