ขั้นตอนวิธีของเฟรย์วัลส์

ขั้นตอนวิธีของเฟรย์วัลส์  เป็นขั้นตอนวิธีแบบสุ่ม (randomised algorithm) ที่รูซินส์ มาร์ตินส์ เฟรย์วัลส์ (Rusins Martins Freivalds) นักวิทยาศาสตร์ชาวลัตเวีย นำเสนอขึ้นสำหรับใช้ตรวจสอบความเท่ากันของผลคูณของเมทริกซ์กับเมทริกซ์ต้นแบบ
แนวคิดเบื้องต้น.
ในบรรดาปัญหาทั้งหมดในเชิงคณิตศาสตร์ มีปัญหาจำนวนมากที่มีขั้นตอนที่สามารถตรวจคำตอบได้เร็วกว่าการหาคำตอบ เช่น ปัญหาเอ็นพี และมีปัญหาจำนวนมากมายที่ขั้นตอนวิธีแก้ปัญหาที่ใช้ขั้นตอนวิธีแบบสุ่มให้ประสิทธิภาพดีกว่าขั้นตอนวิธีที่ตรงไปตรงมา ขั้นตอนวิธีของเฟรย์วัลส์ เป็นขั้นตอนวิธีหนึ่งที่ใช้ขั้นตอนวิธีแบบสุ่ม เพื่อลดเวลาในการตรวจสอบคำตอบของการคูณเมทริกซ์ โดยให้เมทริกซ์ต้นฉบับ และผลคูณของเมทริกซ์ต้นฉบับเป็นข้อมูลนำเข้าของขั้นตอนวิธี ตัวขั้นตอนวิธีก็จะตรวจสอบความเท่ากันจากนั้นคืนค่าว่าเมทริกซ์ต้นฉบับ กับผลคูณของเมทริกซ์ต้นฉบับที่รับมาเป็นข้อมูลนำเข้ามีค่าเท่ากันหรือไม่ ทั้งนี้ขั้นตอนวิธีนี้ตั้งอยู่บนพื้นฐานของความน่าจะเป็น จึงทำให้มีความน่าจะเป็นที่ตัวขั้นตอนวิธีแบบสุ่มนี้จะตอบผิดไปจากความเป็นจริง เช่น ตอบว่า ใช่ ผลคูณของเมทริกซ์ต้นฉบับ เท่ากันกับเมทริกซ์ต้นฉบับที่ได้รับเป็นข้อมูลนำเข้า ทั้งที่จริงๆ แล้ว ผลคูณของเมทริกซ์ต้นฉบับอาจจะไม่เท่ากันกับข้อมูลนำเข้าก็ได้ ทำให้ขั้นตอนวิธีนี้ดูจะไร้ประโยชน์ เพราะดูไม่ต่างจากการเดาสุ่ม แต่ที่จริงแล้วขั้นตอนวิธีนี้สามารถลดความน่าจะเป็นในการตอบผิดได้โดยการทำซ้ำ ซึ่งจะทำให้ความน่าจะเป็นในการตอบผิดมีค่าน้อยกว่าการสุ่มมาก
ขั้นตอนวิธี.
ข้อมูลนำเข้า.
เมทริกซ์จตุรัส 3 เมทริกซ์ มีขนาด <math>n\times n</math> ได้แก่ <math>A, B, C.</math>
ข้อมูลส่งออก.
ตอบ ใช่ ถ้า <math>A\times B = C</math>
ตอบ ไม่ใช่ ถ้า <math>A\times B\neq C</math>
ความซับซ้อนเชิงเวลา.
ทำงานใน O(n2) ซึ่งเร็วกว่าการคูณเมทริกซ์แล้วเปรียบเทียบทีละตัว (ทำงานใน O(n3)) รวมถึงเร็วกว่า ขั้นตอนวิธีของ Coppersmith-Winograd ซึ่งเป็นขั้นตอนวิธีในการหาผลคูณของเมทริกซ์ที่เร็วที่สุดในปัจจุบัน (ทำงานใน O(n2.376)) มาก
วิเคราะห์ความผิดพลาด.
ขั้นตอนวิธีนี้รับประกันว่า ถ้า <math>A\times B = C</math> แล้วความน่าจะเป็นในการตอบผิดจะเป็น 0, ถ้า <math>A\times B\neq C</math> แล้วความน่าจะเป็นในการตอบผิดมีค่าไม่เกิน <math>\frac{1}{2}</math>
* พิจารณากรณีที่ <math>A\times B = C</math>
 <math>\vec{P}=A\times (B\vec{r})-C\vec{r}=\vec{0}</math> สำหรับทุก <math>\vec{r}</math> ที่เป็นไปได้ดังนั้นความน่าจะเป็นในการตอบผิดเป็น 0
* พิจารณากรณีที่ <math>A\times B\neq C</math>
 กำหนดให้ <math>\vec{D}=A\times B -C</math> เนื่องจาก <math>A\times B\neq C</math> แสดงว่าจะมีค่า i,j บางค่าที่ <math>d_{ij}\neq 0</math>
 <math>\vec{P} =A\times (B\vec{r})-C\vec{r}=D\vec{r}=\begin{bmatrix} p_{1} & p_{2} & p_{3} & \cdots & p_{n} \end{bmatrix}</math>
 <math>p_{i} = \Sigma d_{ij}\cdot r_{j} = d_{ij} + K</math>
 โดย กฎของเบย์ (Bayes' theorem)
 <math>Pr[ p_{i} = 0 ] = Pr[ p_{i} = 0 | K = 0 ]\cdot Pr[ K = 0 ] + Pr[ p_{i} = 0 | K \neq 0 ]\cdot Pr[ K \neq 0 ]</math>
 <math>Pr[ p_{i} = 0 | K = 0 ] = Pr[ r_{j} = 0 ] = \frac{1}{2}</math>
 <math>Pr[ p_{i} = 0 | K \neq 0 ] <= Pr[ r_{j} = 1 ] = \frac{1}{2}</math>
 <math>Pr[ p_{i} = 0 ] <= \frac{1}{2}\cdot Pr[ K = 0 ] + \frac{1}{2}\cdot Pr[ K \neq 0 ]</math>
 <math>Pr[ p_{i} = 0 ] <= \frac{1}{2}\cdot Pr[ K = 0 ] + \frac{1}{2}\cdot (1-Pr[ K = 0 ])</math>
 <math>Pr[ p_{i} = 0 ] <= \frac{1}{2}</math>
 เพราะฉะนั้น <math>Pr[ \vec{P} = \vec{0} ] <= Pr[ p_{i} = 0 ] <= \frac{1}{2}</math>
หมายเหตุ.
แม้ว่าขั้นตอนวิธีนี้อาจมีความผิดพลาดสูงได้ถึง <math>\tfrac{1}{2}</math> แต่ในการใช้งานจริงสามารถลดความผิดพลาดได้ การทำงานขั้นตอนวิธีนี้ซ้ำหลาย ๆ ครั้งโดยใช้ <math>\vec{r}</math> ที่แตกต่างกัน จะช่วยลดความน่าจะเป็นในการตอบผิดลงไปได้
สมมุติว่าต้องการทำขั้นตอนวิธีนี้ซ้ำกัน <math>n</math> ครั้ง พบว่าความน่าจะเป็นในการตอบผิดมีค่า ≤ <math>\tfrac{1}{2^{n}}</math> ซึ่งมีค่าลดลงเป็นฟังก์ชันเลขชี้กำลังเมื่อเทียบกับค่า <math>n</math>
เชิงอรรถ.
<templatestyles src="Reflist/styles.css" />