Category:Matrix product verification

From LiteratePrograms
Jump to: navigation, search

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.

hijacker
hijacker
hijacker
hijacker

Pages in category "Matrix product verification"

This category contains only the following page.