Efficiently Correcting Matrix Products

Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama

Abstract: Matrix multiplication is a fundamental operation in scientific computing, yet verifying and correcting errors in large-scale products remains a challenge. While Freivalds' algorithm provides an $O(n^2)$ verification method, it lacks the ability to locate or fix errors. This paper introduces the first efficient, output-sensitive algorithms for correcting up to $k$ errors in a matrix product. By leveraging combinatorial group testing and algebraic sketching, these methods achieve correction in as little as $\tilde{O}(n^2 + kn)$ time, significantly outperforming full recomputation when the number of errors is small.

Introduction

In modern high-performance computing and distributed systems, hardware faults or communication errors can lead to corrupted results in matrix multiplication ($C = A \times B$). Since 1977, Freivalds' algorithm has been the gold standard for verifying the correctness of a product $C'$ in $O(n^2)$ time. However, a negative result from Freivalds' test necessitates a full recomputation of the product, which takes $O(n^\omega)$ time (where $\omega \approx 2.37$). This paper addresses the "correction problem": how to efficiently identify and fix erroneous entries without starting from scratch.

Algorithmic Approaches to Error Correction

The authors propose three distinct methodologies to bridge the gap between verification and recomputation.

Combinatorial Methods

The first approach uses deterministic combinatorial techniques. By shuffling columns using sequences of prime numbers, the algorithm ensures that erroneous entries are isolated into specific "strips." Once isolated, these errors can be identified via simple sum-checks and recomputed individually. This method draws a direct parallel to combinatorial group testing, where a small number of "defective" items are identified through group observations.

Visualizing the isolation of erroneous entries into strips for correction.

A randomized variant of this combinatorial approach employs sampling to detect erroneous rows and columns. To handle scenarios where the total number of errors $k$ is unknown, the algorithm uses a "guessing and doubling" strategy to iteratively refine its search.

Algebraic Sketching

The most advanced technique involves "Compressed Matrix Multiplication." This algebraic approach uses hash functions to map matrix entries into polynomials. By comparing the sketches of the input matrices $A$ and $B$ against the erroneous product $C'$, the errors appear as coefficients in the resulting polynomial. A majority-vote mechanism across multiple hash functions allows the algorithm to recover the correct values with high probability.

Complexity and Results

The primary contribution of this work is a set of complexity bounds that scale with the number of errors $k$. For small $k$ (e.g., $k < n^{0.37}$), the proposed randomized algorithm runs in $\tilde{O}(n^2 + kn)$ time, which is nearly optimal and much faster than recomputing the entire matrix.

Summary of time complexity bounds for matrix product correction across various scenarios.

As shown in the table above, the complexity varies based on whether $k$ is known and whether deterministic or randomized methods are used. The $\tilde{O}(n^2 + kn)$ result for the general randomized case represents a significant theoretical breakthrough in output-sensitive matrix algorithms.

Discussion and Future Work

While these algorithms offer substantial theoretical improvements, several areas remain for future exploration. The current algebraic sketches are primarily proven for complex-valued products; extending these to arbitrary rings is an open challenge. Additionally, while the methods can be adapted for unknown $k$, doing so introduces a logarithmic overhead. Finally, practical implementation in high-performance computing environments is needed to determine the empirical "crossover point" where correction becomes more efficient than standard recomputation in real-world systems.

Summary updated

BibTeX
@article{gasieniec2017efficiently,
  author = {Leszek Gasieniec and Christos Levcopoulos and Andrzej Lingas and Rasmus Pagh and Takeshi Tokuyama},
  title = {{Efficiently Correcting Matrix Products}},
  journal = {Algorithmica},
  year = {2017},
  doi = {10.1007/s00453-016-0202-3},
}
Figure