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

**ขั้นตอนวิธีของเฟรย์วัลส์** () เป็นขั้นตอนวิธีแบบสุ่ม (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/

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