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

ขั้นตอนวิธีของเฟรย์วัลส์ (แม่แบบ:Langx) เป็นขั้นตอนวิธีแบบสุ่ม (randomised algorithm) ที่รูซินส์ มาร์ตินส์ เฟรย์วัลส์ (Rusins Martins Freivalds) นักวิทยาศาสตร์ชาวลัตเวีย นำเสนอขึ้นสำหรับใช้ตรวจสอบความเท่ากันของผลคูณของเมทริกซ์กับเมทริกซ์ต้นแบบ

แนวคิดเบื้องต้น

ในบรรดาปัญหาทั้งหมดในเชิงคณิตศาสตร์ มีปัญหาจำนวนมากที่มีขั้นตอนที่สามารถตรวจคำตอบได้เร็วกว่าการหาคำตอบ เช่น ปัญหาเอ็นพี และมีปัญหาจำนวนมากมายที่ขั้นตอนวิธีแก้ปัญหาที่ใช้ขั้นตอนวิธีแบบสุ่มให้ประสิทธิภาพดีกว่าขั้นตอนวิธีที่ตรงไปตรงมา ขั้นตอนวิธีของเฟรย์วัลส์ เป็นขั้นตอนวิธีหนึ่งที่ใช้ขั้นตอนวิธีแบบสุ่ม เพื่อลดเวลาในการตรวจสอบคำตอบของการคูณเมทริกซ์ โดยให้เมทริกซ์ต้นฉบับ และผลคูณของเมทริกซ์ต้นฉบับเป็นข้อมูลนำเข้าของขั้นตอนวิธี ตัวขั้นตอนวิธีก็จะตรวจสอบความเท่ากันจากนั้นคืนค่าว่าเมทริกซ์ต้นฉบับ กับผลคูณของเมทริกซ์ต้นฉบับที่รับมาเป็นข้อมูลนำเข้ามีค่าเท่ากันหรือไม่ ทั้งนี้ขั้นตอนวิธีนี้ตั้งอยู่บนพื้นฐานของความน่าจะเป็น จึงทำให้มีความน่าจะเป็นที่ตัวขั้นตอนวิธีแบบสุ่มนี้จะตอบผิดไปจากความเป็นจริง เช่น ตอบว่า ใช่ ผลคูณของเมทริกซ์ต้นฉบับ เท่ากันกับเมทริกซ์ต้นฉบับที่ได้รับเป็นข้อมูลนำเข้า ทั้งที่จริงๆ แล้ว ผลคูณของเมทริกซ์ต้นฉบับอาจจะไม่เท่ากันกับข้อมูลนำเข้าก็ได้ ทำให้ขั้นตอนวิธีนี้ดูจะไร้ประโยชน์ เพราะดูไม่ต่างจากการเดาสุ่ม แต่ที่จริงแล้วขั้นตอนวิธีนี้สามารถลดความน่าจะเป็นในการตอบผิดได้โดยการทำซ้ำ ซึ่งจะทำให้ความน่าจะเป็นในการตอบผิดมีค่าน้อยกว่าการสุ่มมาก

ขั้นตอนวิธี

ข้อมูลนำเข้า

เมทริกซ์จตุรัส 3 เมทริกซ์ มีขนาด $n\times n$ ได้แก่ $A,B,C.$

ข้อมูลส่งออก

ตอบ ใช่ ถ้า $A\times B=C$

ตอบ ไม่ใช่ ถ้า $A\times B\ne C$

วิธีการ

1. สุ่ม เวกเตอร์ $\overrightarrow{r}$ ขนาด $n\times 1$.
2. คำนวณ $\overrightarrow{P}=A\times (B\overrightarrow{r})-C\overrightarrow{r}$.
3. ตรวจสอบว่า$\overrightarrow{P}$ เป็นเวกเตอร์ศูนย์หรือไม่ คืนค่า ใช่ ถ้า$\overrightarrow{P}$ เป็นเวกเตอร์ศูนย์ คืนค่า ไม่ใช่ถ้า$\overrightarrow{P}$ ไม่ได้เป็นเวกเตอร์ศูนย์

ความซับซ้อนเชิงเวลา

ทำงานใน O(n²) ซึ่งเร็วกว่าการคูณเมทริกซ์แล้วเปรียบเทียบทีละตัว (ทำงานใน O(n³) ) รวมถึงเร็วกว่า ขั้นตอนวิธีของ Coppersmith-Winograd ซึ่งเป็นขั้นตอนวิธีในการหาผลคูณของเมทริกซ์ที่เร็วที่สุดในปัจจุบัน (ทำงานใน O(n^2.376)) มาก

วิเคราะห์ความผิดพลาด

ขั้นตอนวิธีนี้รับประกันว่า ถ้า $A\times B=C$ แล้วความน่าจะเป็นในการตอบผิดจะเป็น 0, ถ้า $A\times B\ne C$ แล้วความน่าจะเป็นในการตอบผิดมีค่าไม่เกิน $\frac{1}{2}$

• พิจารณากรณีที่ $A\times B=C$

$\overrightarrow{P}=A\times (B\overrightarrow{r})-C\overrightarrow{r}=\overrightarrow{0}$ สำหรับทุก $\overrightarrow{r}$ ที่เป็นไปได้ดังนั้นความน่าจะเป็นในการตอบผิดเป็น 0

• พิจารณากรณีที่ $A\times B\ne C$

กำหนดให้ $\overrightarrow{D}=A\times B-C$ เนื่องจาก $A\times B\ne C$ แสดงว่าจะมีค่า i,j บางค่าที่ $d_{ij}\ne 0$

$\overrightarrow{P}=A\times (B\overrightarrow{r})-C\overrightarrow{r}=D\overrightarrow{r}=\left[\begin{array}{ccccc}{p}_1& p_2& p_3& \cdots & p_n\end{array}\right]$

$p_i=\mathrm{\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\ne 0]\cdot Pr[K\ne 0]$

$Pr[p_i=0|K=0]=Pr[r_j=0]=\frac{1}{2}$

$Pr[p_i=0|K\ne 0]<=Pr[r_j=1]=\frac{1}{2}$

$Pr[p_i=0]<=\frac{1}{2}\cdot Pr[K=0]+\frac{1}{2}\cdot Pr[K\ne 0]$

$Pr[p_i=0]<=\frac{1}{2}\cdot Pr[K=0]+\frac{1}{2}\cdot (1-Pr[K=0])$

$Pr[p_i=0]<=\frac{1}{2}$

เพราะฉะนั้น $Pr[\overrightarrow{P}=\overrightarrow{0}]<=Pr[p_i=0]<=\frac{1}{2}$

หมายเหตุ

แม้ว่าขั้นตอนวิธีนี้อาจมีความผิดพลาดสูงได้ถึง $\frac{1}{2}$ แต่ในการใช้งานจริงสามารถลดความผิดพลาดได้ การทำงานขั้นตอนวิธีนี้ซ้ำหลาย ๆ ครั้งโดยใช้ $\overrightarrow{r}$ ที่แตกต่างกัน จะช่วยลดความน่าจะเป็นในการตอบผิดลงไปได้

สมมุติว่าต้องการทำขั้นตอนวิธีนี้ซ้ำกัน $n$ ครั้ง พบว่าความน่าจะเป็นในการตอบผิดมีค่า ≤ $\frac{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. [1]แม่แบบ:ลิงก์เสีย