อัลกอริทึมของ Freivalds (ตั้งชื่อตามRūsiņš Mārtiņš Freivalds ) เป็นอัลกอริทึมแบบสุ่มเชิง ความน่าจะเป็น ที่ใช้ในการตรวจสอบการคูณเมทริกซ์ โดยกำหนดเมทริกซ์ขนาดn × nสามเมทริกซ์  ${\displaystyle A}$,${\displaystyle B}$, และ${\displaystyle C}$ปัญหาทั่วไปประการหนึ่งคือการตรวจสอบว่า${\displaystyle A\times B=C}$อัลกอริทึมแบบง่ายๆจะคำนวณผลคูณ${\displaystyle A\times B}$ระบุอย่างชัดเจนและเปรียบเทียบทีละข้อว่าผลิตภัณฑ์นี้เท่ากับหรือไม่${\displaystyle C}$อย่างไรก็ตามอัลกอริทึมการคูณเมทริกซ์ที่เป็นที่รู้จักดีที่สุดนั้นทำงานด้วย${\displaystyle O(n^{2.372})}$เวลา อัลกอริทึมของ Freivalds ใช้การสุ่มเพื่อลดขอบเขตเวลาดังกล่าวลง${\displaystyle O(n^{2})}$^{[ 1 ]}ด้วยความน่าจะเป็นสูงใน${\displaystyle O(kn^{2})}$เวลาที่อัลกอริธึมสามารถตรวจสอบผลคูณเมทริกซ์ได้ด้วยความน่าจะเป็นของความล้มเหลวน้อยกว่า${\displaystyle 2^{-k}}$.

สมมติว่าเราต้องการตรวจสอบว่า:

${\displaystyle AB={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\stackrel {?}{=}}{\begin{bmatrix}6&5\\8&7\end{bmatrix}}=C.}$

เลือกเวกเตอร์แบบสุ่มที่มีสององค์ประกอบ โดยแต่ละองค์ประกอบมีค่าเท่ากับ 0 หรือ 1 –สมมติว่าเป็น เวกเตอร์นี้ ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$ –และใช้ในการคำนวณ:

${\displaystyle {\begin{aligned}A\times (B{\vec {r}})-C{\vec {r}}&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\\&={\begin{bmatrix}2 &3\\3&4\end{bmatrix}}{\begin{bmatrix}1\\3\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}11\\15\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}0\\0\end{bmatrix}}.\end{aligned}}}$

ผลลัพธ์ที่ได้คือเวกเตอร์ศูนย์ ซึ่งบ่งชี้ถึงความเป็นไปได้ที่ AB = C อย่างไรก็ตาม หากในการทดลองครั้งที่สอง เวกเตอร์${\displaystyle {\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}}$หากเลือกตัวเลือกนี้ ผลลัพธ์ที่ได้จะเป็นดังนี้:

${\displaystyle A\times (B{\vec {r}})-C{\vec {r}}={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}-1\\-1\end{bmatrix}}.}$

ผลลัพธ์ที่ได้ไม่ใช่ศูนย์ ซึ่งพิสูจน์ได้ว่า AB ≠ C อย่างแท้จริง

มีเวกเตอร์ 0/1 สององค์ประกอบอยู่สี่เวกเตอร์ และครึ่งหนึ่งของเวกเตอร์เหล่านั้นจะให้เวกเตอร์ศูนย์ในกรณีนี้ (${\displaystyle {\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}}$และ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$ดังนั้น โอกาสที่จะสุ่มเลือกสิ่งเหล่านี้ในการทดลองสองครั้ง (และสรุปผิดว่า AB=C) คือ 1/2 ^หรือ 1/4 ในกรณีทั่วไป สัดส่วนของrที่ให้เวกเตอร์ศูนย์อาจน้อยกว่า 1/2 และจะใช้จำนวนการทดลองที่มากขึ้น (เช่น 20 ครั้ง) ซึ่งทำให้ความน่าจะเป็นของข้อผิดพลาดน้อยลงมาก

ให้pเท่ากับความน่าจะเป็นของความผิดพลาด เราอ้างว่า ถ้าA × B = Cแล้วp = 0 และถ้าA × B ≠ Cแล้วp ≤ 1/2    

กรณีA × B ≠ C  

อนุญาต${\displaystyle D}$โดยที่

${\displaystyle {\vec {P}}=D\times {\vec {r}}=(p_{1},p_{2},\dots ,p_{n})^{T}}$

ที่ไหน

${\displaystyle D=A\times BC=(d_{ij})}$.

เนื่องจาก${\displaystyle A\times B\neq C}$เรามีองค์ประกอบบางอย่างของ${\displaystyle D}$มีค่าไม่เป็นศูนย์ สมมติว่าองค์ประกอบนั้น${\displaystyle d_{ij}\neq 0}$ตามนิยามของการคูณเมทริกซ์เราจะได้ว่า:

${\displaystyle p_{i}=\sum _{k=1}^{n}d_{ik}r_{k}=d_{i1}r_{1}+\cdots +d_{ij}r_{j}+\cdots +d_{in}r_{n}=d_{ij}r_{j}+y}$.

สำหรับค่าคงที่บางค่า${\displaystyle y}$โดยใช้ทฤษฎีบทของเบย์สเราสามารถแบ่งกลุ่มตาม${\displaystyle y}$:

${\displaystyle \Pr[p_{i}=0]=\Pr[p_{i}=0|y=0]\cdot \Pr[y=0]\,+\,\Pr[p_{i}=0|y\neq 0]\cdot \Pr[y\neq 0]}$

1

เราใช้สิ่งนั้น:

${\displaystyle \Pr[p_{i}=0|y=0]=\Pr[r_{j}=0]={\frac {1}{2}}}$

${\displaystyle \Pr[p_{i}=0|y\neq 0]=\Pr[r_{j}=1\land d_{ij}=-y]\leq \Pr[r_{j}=1]={\frac {1}{2}}}$

เมื่อแทนค่าเหล่านี้ลงในสมการ ( 1 ) เราจะได้:

${\displaystyle {\begin{aligned}\Pr[p_{i}=0]&\leq {\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot \Pr[y\neq 0]\\&={\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot (1-\Pr[y=0])\\&={\frac {1}{2}}\end{aligned}}}$

ดังนั้น,

${\displaystyle \Pr[{\vec {P}}=0]=\Pr[p_{1}=0\land \dots \land p_{i}=0\land \dots \land p_{n}=0]\leq \Pr[p_{i}=0]\leq {\frac {1}{2}}.}$

การพิสูจน์เสร็จสมบูรณ์แล้ว

การวิเคราะห์เชิงอัลกอริทึมอย่างง่ายแสดงให้เห็นว่าเวลาในการทำงานของอัลกอริทึม นี้ คือ${\displaystyle O(n^{2})}$(ในสัญกรณ์ Big O ) วิธีนี้เร็วกว่าเวลาการทำงานของอัลกอริธึมเชิงกำหนด แบบคลาสสิกซึ่งอยู่ที่${\displaystyle O(n^{3})}$(หรือ${\displaystyle O(n^{2.372})}$หากใช้การคูณเมทริกซ์แบบเร็ว ) การวิเคราะห์ข้อผิดพลาดยังแสดงให้เห็นว่า หากเรียกใช้อัลกอริทึม${\displaystyle k}$ครั้ง โดยมีขอบเขตความคลาดเคลื่อนน้อยกว่า${\displaystyle 1/2^{k}}$สามารถทำได้ ซึ่งเป็นปริมาณที่เล็กมากในเชิงเลขชี้กำลัง อัลกอริทึมนี้ยังทำงานได้รวดเร็วในทางปฏิบัติ เนื่องจากมีการใช้งานที่รวดเร็วสำหรับการคูณเมทริกซ์กับเวกเตอร์อย่างแพร่หลาย ดังนั้น การใช้อัลกอริทึมแบบสุ่ม จึง สามารถเร่งความเร็วอัลกอริทึมแบบกำหนดที่ ช้ามาก ได้

อัลกอริทึมของ Freivalds มักถูกกล่าวถึงในบทนำเกี่ยวกับอัลกอริทึมเชิงความน่าจะเป็นเนื่องจากความเรียบง่ายและวิธีการที่แสดงให้เห็นถึงความเหนือกว่าของอัลกอริทึมเชิงความน่าจะเป็นในทางปฏิบัติสำหรับปัญหาบางอย่าง

• ทฤษฎีบท Schwartz–Zippel