(שאלה רלוונטית לסטודנטים משנת 2025/2026)
בשאלה זו נציג אלגוריתם להכפלת שתי מטריצות ריבועיות A,B מסדר n×n מעל שדה פשוט. ניחו לשם פשטות כי n הינו חזקה של 2. תוצאת המכפלה הינה מטריצה C=A×B מסדר n×n, שמקיימת Ci,j=∑1≤k≤nAi,k×Bk,j. נפרק כל מטריצה ל-4 תתי-מטריצות מסדר 2n×2n, כדלקמן:
A=(acbd),B=(efgh),C=(rtsu)
מהגדרת כפל מטריצות:
r=a×e+b×f,s=a×g+b×ht=c×e+d×f,u=c×g+d×h
האלגוריתם מחשב את 7 המטריצות הבאות:
P3=(c+d)×e,P5=(a+d)×(e+h),P1=a×(g−h)P4=d×(f−e),P6=(b−d)×(f+h),P2=(a+b)×hP7=(a−c)×(e+g)
(א) הסבירו כיצד לחשב את r,s,t,u באמצעות פעולות חיבור וחיסור בלבד על P1,...,P7 (ללא הכפלת מטריצות). לדוגמה: u=−P7+P5+P1−P3 (אסורה הכפלת מטריצות).
(ב) בדקו כמה הכפלות של סקלרים דרושות סה"כ לאלגוריתם הרקורסיבי שתואר בשאלה זו. (ניתן לפתור את סעיף ב' גם אם טועים בסעיף א'.)