خوارزمية فريفالدز

خوارزمية فريفالدز (نسبةً إلى روسينش مارتينش فريفالدز ) هي خوارزمية احتمالية عشوائية تُستخدم للتحقق من ضرب المصفوفات . بفرض وجود ثلاث مصفوفات من الرتبة n × n  ${\displaystyle A}$،${\displaystyle B}$، و${\displaystyle C}$تتمثل إحدى المشكلات العامة في التحقق مما إذا${\displaystyle A\times B=C}$ستقوم خوارزمية بسيطة بحساب الناتج${\displaystyle A\times B}$قم بتوضيح ذلك وقارن كل حد على حدة لمعرفة ما إذا كان هذا الناتج يساوي${\displaystyle C}$ومع ذلك، فإن أفضل خوارزمية معروفة لضرب المصفوفات تعمل في${\displaystyle O(n^{2.372})}$الوقت. تستخدم خوارزمية فريفالدز العشوائية لتقليل هذا الوقت المحدد لـ${\displaystyle O(n^{2})}$^{[ 1 ]} باحتمالية عالية. في${\displaystyle O(kn^{2})}$الوقت الذي يمكن للخوارزمية فيه التحقق من ضرب المصفوفات باحتمالية فشل أقل من${\displaystyle 2^{-k}}$.

لنفترض أن المرء يرغب في تحديد ما إذا كان:

${\displaystyle AB={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\stackrel {?}{=}}{\begin{bmatrix}6&5\\8&7\end{bmatrix}}=C.}$

يتم اختيار متجه عشوائي مكون من عنصرين، تكون قيم مدخلاته إما 0 أو 1 – على سبيل المثال ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$ - وتستخدم لحساب:

${\displaystyle {\begin{aligned}A\times (B{\vec {r}})-C{\vec {r}}&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\\&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1\\3\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}11\\15\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}0\\0\end{bmatrix}}.\end{aligned}}}$

ينتج عن هذا المتجه الصفري، مما يشير إلى إمكانية أن يكون AB = C. ومع ذلك، إذا كان المتجه في تجربة ثانية${\displaystyle {\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}}$عند اختيارها، تصبح النتيجة:

${\displaystyle A\times (B{\vec {r}})-C{\vec {r}}={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}-1\\-1\end{bmatrix}}.}$

والنتيجة غير صفرية، مما يثبت أن AB ≠ C في الواقع.

يوجد أربعة متجهات ثنائية العناصر من نوع 0/1، ونصفها يعطي المتجه الصفري في هذه الحالة (${\displaystyle {\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}}$و${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$وبالتالي، فإن احتمال اختيار هذه القيم عشوائيًا في تجربتين (والاستنتاج الخاطئ بأن AB=C) هو 1/2 ^أو 1/4. في الحالة العامة، قد تكون نسبة r التي تُعطي المتجه الصفري أقل من 1/2، وسيتم استخدام عدد أكبر من التجارب (مثل 20)، مما يجعل احتمال الخطأ ضئيلاً للغاية.

لنفترض أن p تساوي احتمال الخطأ. ندعي أنه إذا كان A × B = C ، فإن p = 0، وإذا كان A × B ≠ C ، فإن p ≤ 1/2.    

الحالة أ × ب ≠ ج  

يترك${\displaystyle D}$بحيث

${\displaystyle {\vec {P}}=D\times {\vec {r}}=(p_{1},p_{2},\dots ,p_{n})^{T}}$

أين

${\displaystyle D=A\times B-C=(d_{ij})}$.

منذ${\displaystyle A\times B\neq C}$لدينا أن بعض عناصر${\displaystyle D}$غير صفري. لنفترض أن العنصر${\displaystyle d_{ij}\neq 0}$بحسب تعريف ضرب المصفوفات ، لدينا:

${\displaystyle p_{i}=\sum _{k=1}^{n}d_{ik}r_{k}=d_{i1}r_{1}+\cdots +d_{ij}r_{j}+\cdots +d_{in}r_{n}=d_{ij}r_{j}+y}$.

لبعض الثوابت${\displaystyle y}$باستخدام نظرية بايز ، يمكننا التقسيم على${\displaystyle y}$:

${\displaystyle \Pr[p_{i}=0]=\Pr[p_{i}=0|y=0]\cdot \Pr[y=0]\,+\,\Pr[p_{i}=0|y\neq 0]\cdot \Pr[y\neq 0]}$

1

نستخدم ذلك:

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

${\displaystyle \Pr[p_{i}=0|y\neq 0]=\Pr[r_{j}=1\land d_{ij}=-y]\leq \Pr[r_{j}=1]={\frac {1}{2}}}$

وبإدخال هذه القيم في المعادلة ( 1 )، نحصل على:

${\displaystyle {\begin{aligned}\Pr[p_{i}=0]&\leq {\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot \Pr[y\neq 0]\\&={\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot (1-\Pr[y=0])\\&={\frac {1}{2}}\end{aligned}}}$

لذلك،

${\displaystyle \Pr[{\vec {P}}=0]=\Pr[p_{1}=0\land \dots \land p_{i}=0\land \dots \land p_{n}=0]\leq \Pr[p_{i}=0]\leq {\frac {1}{2}}.}$

وبهذا يكتمل البرهان.

يُظهر تحليل خوارزمي بسيط أن وقت تشغيل هذه الخوارزمية هو${\displaystyle O(n^{2})}$(باستخدام ترميز Big O ). وهذا يتفوق على وقت تشغيل الخوارزمية الحتمية الكلاسيكية البالغ${\displaystyle O(n^{3})}$(أو${\displaystyle O(n^{2.372})}$في حالة استخدام ضرب المصفوفات السريع ). كما يُظهر تحليل الخطأ أنه في حالة تشغيل الخوارزمية${\displaystyle k}$في بعض الأحيان، يكون هامش الخطأ أقل من${\displaystyle 1/2^{k}}$يمكن تحقيق ذلك، وهي كمية صغيرة للغاية. كما أن الخوارزمية سريعة عمليًا نظرًا لتوافر تطبيقات سريعة لضرب المصفوفات في المتجهات. لذلك، يمكن استخدام الخوارزميات العشوائية لتسريع خوارزمية حتمية بطيئة جدًا .

كثيراً ما تظهر خوارزمية فريفالدز في مقدمات الخوارزميات الاحتمالية بسبب بساطتها وكيف توضح تفوق الخوارزميات الاحتمالية عملياً في بعض المشاكل.

• مبرهنة شوارتز-زيبيل