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

ขั้นตอนวิธีของเฟรย์วัลส์ (Freivalds' algorithm) เป็นขั้นตอนวิธีแบบสุ่ม (randomised algorithm) ที่รูซินส์ มาร์ตินส์ เฟรย์วัลส์ (Rusins Martins Freivalds) นักวิทยาศาสตร์ชาวลัตเวีย นำเสนอขึ้นสำหรับใช้ตรวจสอบความเท่ากันของผลคูณของเมทริกซ์กับเมทริกซ์ต้นแบบ
== แนวคิดเบื้องต้น ==
ในบรรดาปัญหาทั้งหมดในเชิงคณิตศาสตร์ มีปัญหาจำนวนมากที่มีขั้นตอนที่สามารถตรวจคำตอบได้เร็วกว่าการหาคำตอบ เช่น  ปัญหาเอ็นพี และมีปัญหาจำนวนมากมายที่ขั้นตอนวิธีแก้ปัญหาที่ใช้ขั้นตอนวิธีแบบสุ่มให้ประสิทธิภาพดีกว่าขั้นตอนวิธีที่ตรงไปตรงมา ขั้นตอนวิธีของเฟรย์วัลส์ เป็นขั้นตอนวิธีหนึ่งที่ใช้ขั้นตอนวิธีแบบสุ่ม เพื่อลดเวลาในการตรวจสอบคำตอบของการคูณเมทริกซ์ โดยให้เมทริกซ์ต้นฉบับ และผลคูณของเมทริกซ์ต้นฉบับเป็นข้อมูลนำเข้าของขั้นตอนวิธี ตัวขั้นตอนวิธีก็จะตรวจสอบความเท่ากันจากนั้นคืนค่าว่าเมทริกซ์ต้นฉบับ กับผลคูณของเมทริกซ์ต้นฉบับที่รับมาเป็นข้อมูลนำเข้ามีค่าเท่ากันหรือไม่ ทั้งนี้ขั้นตอนวิธีนี้ตั้งอยู่บนพื้นฐานของความน่าจะเป็น จึงทำให้มีความน่าจะเป็นที่ตัวขั้นตอนวิธีแบบสุ่มนี้จะตอบผิดไปจากความเป็นจริง เช่น ตอบว่า ใช่ ผลคูณของเมทริกซ์ต้นฉบับ เท่ากันกับเมทริกซ์ต้นฉบับที่ได้รับเป็นข้อมูลนำเข้า ทั้งที่จริงๆ แล้ว ผลคูณของเมทริกซ์ต้นฉบับอาจจะไม่เท่ากันกับข้อมูลนำเข้าก็ได้ ทำให้ขั้นตอนวิธีนี้ดูจะไร้ประโยชน์ เพราะดูไม่ต่างจากการเดาสุ่ม แต่ที่จริงแล้วขั้นตอนวิธีนี้สามารถลดความน่าจะเป็นในการตอบผิดได้โดยการทำซ้ำ ซึ่งจะทำให้ความน่าจะเป็นในการตอบผิดมีค่าน้อยกว่าการสุ่มมาก
== ขั้นตอนวิธี ==
=== ข้อมูลนำเข้า ===
เมทริกซ์จตุรัส 3 เมทริกซ์ มีขนาด n\times n ได้แก่ A, B, C.
=== ข้อมูลส่งออก ===
ตอบ ใช่ ถ้า A\times B = C
ตอบ ไม่ใช่ ถ้า A\times B\neq C
=== วิธีการ ===
สุ่ม เวกเตอร์ \vec{r} ขนาด n\times 1.
คำนวณ \vec{P}=A\times (B\vec{r})-C\vec{r}.
ตรวจสอบว่า\vec{P} เป็นเวกเตอร์ศูนย์หรือไม่ คืนค่า ใช่ ถ้า\vec{P} เป็นเวกเตอร์ศูนย์ คืนค่า ไม่ใช่ถ้า\vec{P} ไม่ได้เป็นเวกเตอร์ศูนย์
== ความซับซ้อนเชิงเวลา ==
ทำงานใน  O(n2)  ซึ่งเร็วกว่าการคูณเมทริกซ์แล้วเปรียบเทียบทีละตัว (ทำงานใน O(n3) ) รวมถึงเร็วกว่า ขั้นตอนวิธีของ Coppersmith-Winograd ซึ่งเป็นขั้นตอนวิธีในการหาผลคูณของเมทริกซ์ที่เร็วที่สุดในปัจจุบัน (ทำงานใน O(n2.376)) มาก
== วิเคราะห์ความผิดพลาด ==
ขั้นตอนวิธีนี้รับประกันว่า ถ้า A\times B = C แล้วความน่าจะเป็นในการตอบผิดจะเป็น 0, ถ้า A\times B\neq C แล้วความน่าจะเป็นในการตอบผิดมีค่าไม่เกิน \frac{1}{2}
* พิจารณากรณีที่ A\times B = C
: \vec{P}=A\times (B\vec{r})-C\vec{r}=\vec{0} สำหรับทุก \vec{r} ที่เป็นไปได้ดังนั้นความน่าจะเป็นในการตอบผิดเป็น 0
* พิจารณากรณีที่ A\times B\neq C
: กำหนดให้ \vec{D}=A\times B -C เนื่องจาก A\times B\neq C แสดงว่าจะมีค่า i,j บางค่าที่ d_{ij}\neq 0
: \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}
: p_{i} = \Sigma d_{ij}\cdot r_{j} = d_{ij} + K
: โดย กฎของเบย์ (Bayes' theorem)
: 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 ]
:: Pr[ p_{i} = 0 | K = 0 ] = Pr[ r_{j} = 0 ] = \frac{1}{2}
:: Pr[ p_{i} = 0 | K \neq 0 ] 
: Pr[ p_{i} = 0 ] 
: Pr[ p_{i} = 0 ] 
: Pr[ p_{i} = 0 ] 
: เพราะฉะนั้น Pr[ \vec{P} = \vec{0} ] 
== หมายเหตุ ==
แม้ว่าขั้นตอนวิธีนี้อาจมีความผิดพลาดสูงได้ถึง \tfrac{1}{2} แต่ในการใช้งานจริงสามารถลดความผิดพลาดได้ การทำงานขั้นตอนวิธีนี้ซ้ำหลาย ๆ ครั้งโดยใช้ \vec{r} ที่แตกต่างกัน จะช่วยลดความน่าจะเป็นในการตอบผิดลงไปได้
สมมุติว่าต้องการทำขั้นตอนวิธีนี้ซ้ำกัน n ครั้ง พบว่าความน่าจะเป็นในการตอบผิดมีค่า ≤ \tfrac{1}{2^{n}} ซึ่งมีค่าลดลงเป็นฟังก์ชันเลขชี้กำลังเมื่อเทียบกับค่า n
== เชิงอรรถ ==
== อ้างอิง ==
Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pp. 839–842.
Freivalds, R. (1979), “Fast Probabilistic Algorithms”, MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1979, pp. 59-63. [http://www.springerlink.com/content/p679q6712h1047jp/]
พีชคณิตเชิงเส้น
ขั้นตอนวิธีแบบสุ่ม
ทฤษฎีเมทริกซ์