ضرب سلسلة مصفوفات

ضرب سلسلة مصفوفات هو ليس فقط عملية ضرب ومحصلة ولكن يلزم ان يفهم القارئ اولا ماهو الهدف من المصفوفة حتي يستطيع ان يبدع في هذا المجال. للشرح المبسط نأخذ المثال التالي: فرضا ان لديك صوت لمدة ثانية والصوت يتغير وقد تم أخذ عينية من الصوت كل عشر من الثانية. عليه يكون لديك عشرة ارقام تمثل تغير الصوت في هذة الثانية. يمكن كتابة الأرقام بجاور بعضهم في شكل مصفوفة احادية. الآن نفترض اننا نريد إجراء عملية حسابية لتغيير ارتفاع الصوت، ابسط شيء سوف تقول نضرب المصفوفة في رقم ثابت.

الشكل الأولي للمصفوفة المثالية

$I_n=\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right].$

مثلا : الصوت كل عشر من الثانية ممثل برقم [5 3 1 3 5 7 6 5 2 3] اتجاه الكتابة من اليسار الي اليمين. لتعلية الصوت كل الوقت بنفس المقدار يلزم ضرب مقدار الصوت كل عشر من الثانية في رقم ثابت وليكن 4 اضعاف النتيجة: [5 3 1 3 5 7 6 5 2 3] * 4 = [20 12 4 12 20 28 24 20 8 12]

مثال اخر للتوضيح: افرض اننا نحتاج ان نزيد الصوت ارتفاعا ولكن ليس كل الوقت بنفس المقدار كما في المثال السابق ولكن أول ثلاثة اعشار من الثانية بمقدار 3 اضعاف ثم ثاني ثلاثة اعشار بقدار 8 ثم اخر أربعة اعشار بمقدار 5 اضغاف ابسط وسلية هي ضرب المصفوفات

الصوت : [5 3 1 3 5 7 6 5 2 3] الزيادة: [5 5 5 5 8 8 8 3 3 3]

رياضيا لا يمكن كتابة شكل الزيادة كمصفوفة عرضية لذلك تكتب كمصفوفه طولية

الزيادة :

[3
3
3
8
8
8
5
5
5
5 ]

المحصلة تكون ضرب الصف في الصوت في عمود الزيادة بمعني كل عنصر يضرب في العنصر المقابل

الحل = [25 15 5 15 40 42 48 15 6 9]

ضرب سلسلة مصفوفات هي مسألة استمثالية، يمكن حلها باستعمال البرمجة الديناميكية. بمعلومية تعاقب معين من المصفوفات، يتعين علينا البحث عن أفضل السبل لضربها ببعض. المسألة ليست في الحقيقة إجراء عملية الضرب، بل هي مجرد اتخاذ الترتيب المناسب لإجراء عملية الضرب.

لدينا العديد من الخيارات بفضل خاصية التجميع للضرب. بعبارة، بغض النظر عن كيفية إدراج الأقواس ستكون النتيجة واحدة. مثلاً، لو أن لدينا أربع مصفوفات A, B, C, and D، فسنجد أن:

(ABC)D = (AB)(CD) = A(BCD) = A(BC)D =....

مع ذلك سنلاحظ أن عملية ترتيب هذه الأقواس يؤثر على عدد العمليات البسيطة المراد استعمالها في حساب عملية الضرب، أو «الكفاءة». لنفرض مثلاً أن لدينا A هي مصفوفة، 10 × 30، B هي مصفوفة 30 × 5 مصفوفة, وC هي مصفوفة a 5 × 60. حينئذ،

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 عملية

A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 عملية.

يبدو جلياً أن الطريقة الأولى أكثر كفاءة ونكون بها قد عينّا الطريقة الأمثل.

خوارزم برمجة ديناميكية

لنفترض أننا بصدد إيجاد أقل تكلفة، أو أقل عدد من العمليات الحسابية، اللازمة لضرب المصفوفات. لو كنا بصدد ضرب مصفوفتين فقط فإن هناك طريقة واحدة لضربها ببعض، وعليه فإن أقل تكلفة هي تكلفة القيام بهذه العملية. يمكننا تحديد أقل تكلفة باتباع هذا الخوارزم التكراري:

• نأخذ المصفوفات المتعاقبة ونفصلها إلى تعاقبين فرعيين.
• نبحث عن أقل تكلفة لازمة لضرب هذين التعاقبين.
• نقوم بإضافة هذه التكاليف لبعضها، وبإضافة تكلفة ضرب نتيجة التعاقبين.
• نكرر هذه العملية لكل موضع قابل لفصل المصفوفات المتعاقبة، ونأخذ أقل تكلفة بين جميع المحاولات.

شفرة برمجية بلغة السي:

Matrix-Chain-Order(int p[])
{
  n = p.length - 1;
  for (i = 1; i <= n; i++) 
    m[i,i] = 0;

  for (L=2; L<=n; L++) { // L is chain length
    for (i=1; i<=n-L+1; i++) {
      j = i+L-1;
      m[i,j] = MAXINT;
      for (k=i; k<=j-1; k++) {
        q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j];//Matrix Ai has the dimension p[i-1] x p[i].
        if (q <m[i,j]) {
          m[i,j] = q;
          s[i,j] = k;
        }
      }
    }
  }
}

شفرة بلغة سي "C"

يمكن الحصول على نسخة كاملة من برنامج مكتوب بلغة سي على الويب هنا

شفرة بلغة ال Matlab

أفضل لغات البرمجة لاجراء العمليات الحسابية هي ماتلاب Matlab و يكون البرنامج كالتالي

sound=[5 3 1 3 5 7 6 5 2 3]; increase=[5 5 5 5 8 8 8 3 3 3]; result=sound.*increase

المراجع

• Thomas H. Cormen, Charles E. Leiserson, رونالد ريفست, and كليفورد شتاين. مقدمة في الخوارزميات (كتاب), Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 15.2: Matrix-chain multiplication, pp. 331–339.
• Viv. Dynamic Programming. A 1995 introductory article on dynamic programming.
• G. Baumgartner, D. Bernholdt, D. Cociorva, R. Harrison, M. Nooijen, J. Ramanujam and P. Sadayappan. A Performance Optimization Framework for Compilation of Tensor Contraction Expressions into Parallel Programs. 7th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS '02). Fort Lauderdale, Florida. 2002.
• Heejo Lee, Jong Kim, Sungje Hong, and Sunggu Lee. Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems. IEEE Trans. on Parallel and Distributed Systems, Vol. 14, No. 4, pp. 394–407, Apr. 2003