Randomized Algorithms in Matrix Multiplication: Freivalds Algorithm and Beyond
Delve into the world of randomized algorithms with a focus on Freivalds Algorithm related to matrix multiplication. Explore how this approach offers a faster solution compared to deterministic methods. Discover the history, applications, and implications of these algorithms in the realm of matrix operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Another Randomized Algorithm Freivalds Algorithm related to Matrix Multiplication
Randomized Algorithms Quicksort makes effective use of random numbers, but is no faster than Mergesort or Heapsort. Here we will see a problem that has a simple randomized algorithm faster than any known deterministic solution.
Matrix Multiplication Multiplying n n matrices (n = 2 in this example) ? ? ? ?= ?? + ?? ?? + ?? ?? + ?? ?? + ?? ? ? ? ? Complexity of straightforward algorithm: (n3) time (There are 8 multiplications here; in general, n multiplications for each of n2 entries) Coppersmith & Winograd showed how to do it in time O(n2.376) in 1989. Williams improved this to O(n2.3729) in 2011. Progress!
History of Matrix Multiplication Algorithms Running time: O(n )
Freivalds Variant Given n n matrices A, B, and C, determine whether AB = C Applications Determining if a matrix is idempotent, i.e., A2 = A. Idempotent matrices have nice properties: they only having eigenvalues 0 and 1, they are diagonalizable, and Ak = A for any positive integer k. Determining if a matrix is orthogonal, i.e., ATA = I. Orthogonal matrices have nice properties: the rows form an orthonormal basis, and the determinant is either 1 or -1.
Freivalds Algorithm (1977) Given n n matrices A, B, and C determine whether AB = C Method: Choose x {0,1}nrandomly and uniformly (bit vector of length n) If ABx Cx then report AB C else report AB = Cprobably
Running Time ABx = A(Bx), so to determine whether ABx Cx we have 3 instances of n n matrix times n-vector These are O(n2) time operations if done straightforwardly Total running time O(n2) Fastest deterministic solution known: O(n2.3729)
How Often Is It Wrong? Case 1: AB = C. ThenP(ABx = Cx)= 1. Case 2: AB C . Then P(ABx = Cx) , as follows: Assume AB C Then AB - C 0, so there exist i, j with (AB - C)ij 0 Let (d1, d2, ,dn) be i-th row of AB - C; dj 0 P((AB - C) x = 0) ? P( ?=1 = P(xj = 1 dkx?= 0) dj ? ?dk x?)
Decreasing the Probability of Error By iterating with k random, independent choices of x, we can decrease probability of error to 1/2k, using time O(kn2). Interesting comparison Quicksort is always correct, and runs slowly with small probability. Frievalds algorithm is always fast, and incorrect with small probability.
