NHÂN MA TR
NHÂN MA TR
N
N
Ph
Phé
ép to
p toá
án trên ma tr
n trên ma tr
n
n
Cng, trma trn:
- 2 ma trn ch!có thcng ho"c tr#cho nhau nu
chúng có cùng kích thưc.
Nhân ma trn:
- Có thnhân 2 ma trn vi nhau nu sct c$a
ma trn 1 = shàng c$a ma trn 2 Kt qus%là
ma trn có shàng c$a ma trn 1 và ct ma trn 2
- Ví d: Nhân 2 ma trn có kích thưc 3x4 và 4x7
ư&c ma trn có kích thưc 3x7
Nhân ma tr
Nhân ma tr
n
n
Tính cht ca nhân ma trn:
- Nhân ma trn không có tính giao hoán
- Ví d: Cho 2 ma trn vuông A và B Kt qu
A*B # B*A
Ví d:Cho 2 ma trn 2x3 * 3x4 Kt quma
trn (2x4)
Nhân ma tr
Nhân ma tr
n
n
Thut toán: Nhân 2 ma trn G(n x n) và H(n x n)
Kt quR(n x n)
for (int i =1;i<n;i++)
for (int j=1;j<n;j++)
R
i,j
= 0;
for (int k=1;k<n;k++)
R
i,j
=R
i,j
+G
i,k
*H
k,j
;
ánh giá thut toán:
- Sphép cng: n
3
- Sphép nhân: n
3
O(n
3
)
Thu
Thu
t to
t toá
án Strassen
n Strassen
- Thut toán Strassen ng dng vi ma trn vuông
- Thut toán Strassen áp dng gii thut chia  tr
- Chia nh'ma trn A, B thành nh(ng ma trn con
A
0
,A
1
,…
A×
××
×B = R
×
××
×
=
A
0
×
××
×B
0
+A
1
×
××
×B
2
A
0
×
××
×B
1
+A
1
×
××
×B
3
A
2
×
××
×B
0
+A
3
×
××
×B
2
A
2
×
××
×B
1
+A
3
×
××
×B
3