Category:Matrix product verification
A frequently used introductory example of randomized algorithms is matrix product verification, where we are given two matrices A and B and a matrix C and asked whether AB = C. With currently known matrix multiplication algorithms, the obvious approach of multiplying out AB takes Ω(n2.37) time. Simple randomized algorithms that instead compute A(Bx) and compare it to Cx for certain randomly chosen vectors x can show equality with high probability in only O(n2) time.
These implementations are based primarily on R. Frievald's 1979 paper "Fast probabilistic algorithms" as surveyed in Tracy Kimbel and Rakesh Sinha's A Probabilistic Algorithm for Verifying Matrix Products Using O(n2) Time and log2n + O(1) Random Bits.hijackerhijacker
Pages in category "Matrix product verification"
This category contains only the following page.