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

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

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

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

ขั้นตอนวิธี

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

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

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

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

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

วิธีการ

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

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

ทำงานใน O(n²) ซึ่งเร็วกว่าการคูณเมทริกซ์แล้วเปรียบเทียบทีละตัว (ทำงานใน O(n³) ) รวมถึงเร็วกว่า ขั้นตอนวิธีของ Coppersmith-Winograd ซึ่งเป็นขั้นตอนวิธีในการหาผลคูณของเมทริกซ์ที่เร็วที่สุดในปัจจุบัน (ทำงานใน O(n^2.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[r_{j}=1]={\frac {1}{2}}$

$Pr[p_{i}=0]<={\frac {1}{2}}\cdot Pr[K=0]+{\frac {1}{2}}\cdot Pr[K\neq 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[{\vec {P}}={\vec {0}}]<=Pr[p_{i}=0]<={\frac {1}{2}}$

หมายเหตุ

แม้ว่าขั้นตอนวิธีนี้อาจมีความผิดพลาดสูงได้ถึง ${\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. [1]