A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
type: Item
instance of: scholarly article
title: A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
zbMATH Open document ID: 0770.65029
DOI: 10.1016/0020-0190(93)90224-W
author: Tracy Kimbrel
author: Rakesh Kumar Sinha
published in: Information Processing Letters
publication date: 1993-05-16T00:00:00Z
review text: The following problem is considered: given three \(n\times n\) matrices \(A\), \(B\) and \(C\), how difficult is it to verify whether \(AB=C\)? Freivalds' probabilistic algorithm to verify matrix products using \(O(n^ 2)\) multiplications and additions, and \(n\) bits of randomness is known. This algorithm selects a vector \(v\) at random from \(\{-1,1\}^ n\). It then computes the products \(A(Bv)\) and \(Cv\), and accepts (reports that \(AB\neq C\)) if and only if \(ABv\neq Cv\). A similar method is proposed in this paper, but the vector \(v\) is chosen from a set of less than \(4n\) vectors, requiring only \(\lceil log_ 2n\rceil+1\) random bits. In section 2 the simplest version of the algorithm for integer matrices is presented. Section 3 shows how to improve the bit complexity. Section 4 extends the algorithm to matrices over finite fields and Section 5 shows how to reduce the error probability.
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 167743
zbMATH Keywords: design of algorithms
zbMATH Keywords: Freivalds' probabilistic algorithm
zbMATH Keywords: matrix products
zbMATH Keywords: bit complexity
zbMATH Keywords: error probability
reviewed by: I. Dimov
MaRDI profile type: Publication
cites work: Q4195937
cites work: Q3856819
cites work: Q3919787
cites work: A sublinear additive sieve for finding prime number
full work available at URL: 0020-0190(93)90224-w
OpenAlex ID: W2051391952
description: scientific article; zbMATH DE number 167743