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

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

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

ขั้นตอนวิธี

ข้อมูลนำเข้า 
เมทริกซ์จตุรัส 3 เมทริกซ์ มีขนาด  ได้แก่

ข้อมูลส่งออก 
ตอบ ใช่ ถ้า 

ตอบ ไม่ใช่ ถ้า

วิธีการ 
 สุ่ม เวกเตอร์  ขนาด .
 คำนวณ .
 ตรวจสอบว่า เป็นเวกเตอร์ศูนย์หรือไม่ คืนค่า ใช่ ถ้า เป็นเวกเตอร์ศูนย์ คืนค่า ไม่ใช่ถ้า ไม่ได้เป็นเวกเตอร์ศูนย์

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

วิเคราะห์ความผิดพลาด 
ขั้นตอนวิธีนี้รับประกันว่า ถ้า  แล้วความน่าจะเป็นในการตอบผิดจะเป็น 0, ถ้า  แล้วความน่าจะเป็นในการตอบผิดมีค่าไม่เกิน 
 พิจารณากรณีที่ 
  สำหรับทุก  ที่เป็นไปได้ดังนั้นความน่าจะเป็นในการตอบผิดเป็น 0
 พิจารณากรณีที่ 
 กำหนดให้  เนื่องจาก  แสดงว่าจะมีค่า i,j บางค่าที่ 
 
 
 โดย กฎของเบย์ (Bayes' theorem)
 
 
 
 
 
 
 เพราะฉะนั้น

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

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

เชิงอรรถ

อ้างอิง 
 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. 

พีชคณิตเชิงเส้น
ขั้นตอนวิธีแบบสุ่ม
ทฤษฎีเมทริกซ์