A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits (Q1209332)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
scientific article

    Statements

    A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits (English)
    0 references
    0 references
    0 references
    16 May 1993
    0 references
    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.
    0 references
    design of algorithms
    0 references
    Freivalds' probabilistic algorithm
    0 references
    matrix products
    0 references
    bit complexity
    0 references
    error probability
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers