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

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

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

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

ขั้นตอนวิธี

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

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

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

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

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

วิธีการ

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

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

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

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

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

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

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

• พิจารณากรณีที่ ${\displaystyle A\times B\neq C}$ 

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

${\displaystyle {\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}}}$ 

${\displaystyle p_{i}=\Sigma d_{ij}\cdot r_{j}=d_{ij}+K}$ 

โดย กฎของเบย์ (Bayes' theorem)

${\displaystyle 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]}$ 

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

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

${\displaystyle Pr[p_{i}=0]<={\frac {1}{2}}\cdot Pr[K=0]+{\frac {1}{2}}\cdot Pr[K\neq 0]}$ 

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

${\displaystyle Pr[p_{i}=0]<={\frac {1}{2}}}$ 

เพราะฉะนั้น ${\displaystyle Pr[{\vec {P}}={\vec {0}}]<=Pr[p_{i}=0]<={\frac {1}{2}}}$ 

หมายเหตุ

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

สมมุติว่าต้องการทำขั้นตอนวิธีนี้ซ้ำกัน ${\displaystyle n}$  ครั้ง พบว่าความน่าจะเป็นในการตอบผิดมีค่า ≤ ${\displaystyle {\tfrac {1}{2^{n}}}}$  ซึ่งมีค่าลดลงเป็นฟังก์ชันเลขชี้กำลังเมื่อเทียบกับค่า ${\displaystyle n}$ 

เชิงอรรถ

1. . คลังข้อมูลเก่า เก็บจาก แหล่งเดิม เมื่อ 2009-01-05. สืบค้นเมื่อ 2011-09-08.
2. Raghavan, Prabhakar (1997). "Randomized algorithms". ACM Computing Surveys (CSUR). 28. doi:10.1145/234313.234327. สืบค้นเมื่อ 2011-09-20.

อ้างอิง

• 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]^{[ลิงก์เสีย]}