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
 Cộng, trừ ma trận:
- 2 ma trận chỉ có thể cộng hoặc trừ cho nhau nếu
chúng có cùng kích thước.
Nhân ma trận:
- Có thể nhân 2 ma trận với nhau nếu số cột của
ma trận 1 = số hàng của ma trận 2  Kết quả sẽ là
ma trận có số hàng của ma trận 1 và cột ma trận 2
- Ví dụ: Nhân 2 ma trận có kích thước 3x4 và 4x7
 được ma trận có kích thước 3x7
Nhân ma tr
Nhân ma tr

*H
k,j
;
Đánh giá thuật toán:
- Số phép cộng: n
3
- Số phép nhân: n
3
 O(n
3
)
Thu
Thu
ậ
ậ
t to
t to
á
á
n Strassen
n Strassen
- Thuật toán Strassen ứng dụng với ma trận vuông
- Thuật toán Strassen áp dụng giải thuật chia để trị
- Chia nhỏ ma trận A, B thành những ma trận con
A
0
,A
1
,…
A ×

×
××
×B
2
A
0
×
××
×B
1
+A
1
×
××
×B
3
A
2
×
××
×B
0
+A
3
×
××
×B
2
A
2

)
P
2
= (A
21
+ A
22
) * B
11
P
3
= A
11
* (B
12
- B
22
)
P
4
= A
22
* (B
21
- B
11
)
P
5
= (A

1
+ P
4
- P
5
+ P
7
C
12
= P
3
+ P
5
C
21
= P
2
+ P
4
C
22
= P
1
+ P
3
- P
2
+ P
6
Thu

ậ
t to
t to
á
á
n Strassen
n Strassen
 Đánh giá giải thuật:
- Thuật toán Strassen có độ phức tạp O(n
log7
) =
O(n
2,81
)
PHƯƠNG TRÌNH
PHƯƠNG TRÌNH
TUY
TUY
Ế
Ế
N T
N T
Í
Í
NH
NH
Phương tr
Phương tr
ì
ì