matrix_multiplication_by_blocks_presentation_es

Vista previa del material en texto

Multiplicación de matrices por bloques
Egor Maximenko
http://www.egormaximenko.com
Seminario “Matrices y operadores”
Escuela Superior de F́ısica y Matemáticas
Instituto Politécnico Nacional
México
2020-09-09
http://www.egormaximenko.com
1 Notación para submatrices
2 Partición de una matriz en bloques
3 Multiplicación de matrices por bloques
4 Ejemplos y aplicaciones
Plan
1 Notación para submatrices
2 Partición de una matriz en bloques
3 Multiplicación de matrices por bloques
4 Ejemplos y aplicaciones
Notación para los componentes de una matriz
Si A ∈Mm×n(C), j ∈ {1, . . . ,m}, k ∈ {1, . . . , n},
entonces Ajk es el componente de A en el j-ésimo renglón y la k-ésima columna.
Ejemplo.
A ∈M2×3(C), A =
[
A11 A
1
2 A
1
3
A21 A
2
2 A
2
3
]
.
Notación para los componentes de una matriz
Si A ∈Mm×n(C), j ∈ {1, . . . ,m}, k ∈ {1, . . . , n},
entonces Ajk es el componente de A en el j-ésimo renglón y la k-ésima columna.
Ejemplo.
A ∈M2×3(C), A =
[
A11 A
1
2 A
1
3
A21 A
2
2 A
2
3
]
.
Submatrices
A =
 A11 A12 A13 A14 A15A21 A22 A23 A24 A25
A31 A
3
2 A
3
3 A
3
4 A
3
5
 ,
A1,32,3,5 =
[
A12 A
1
3 A
1
5
A32 A
3
3 A
3
5
]
En general, si A ∈Mm×n(C),
1 ≤ j1 < j2 < . . . < jp ≤ m, 1 ≤ k1 < k2 < . . . < kq ≤ n,
A
j1,...,jp
k1,...,kq
:=
[
Ajrks
]p,q
r ,s=1
.
Submatrices
A =
 A11 A12 A13 A14 A15A21 A22 A23 A24 A25
A31 A
3
2 A
3
3 A
3
4 A
3
5
 , A1,32,3,5 =
[
A12 A
1
3 A
1
5
A32 A
3
3 A
3
5
]
En general, si A ∈Mm×n(C),
1 ≤ j1 < j2 < . . . < jp ≤ m, 1 ≤ k1 < k2 < . . . < kq ≤ n,
A
j1,...,jp
k1,...,kq
:=
[
Ajrks
]p,q
r ,s=1
.
Submatrices
A =
 A11 A12 A13 A14 A15A21 A22 A23 A24 A25
A31 A
3
2 A
3
3 A
3
4 A
3
5
 , A1,32,3,5 =
[
A12 A
1
3 A
1
5
A32 A
3
3 A
3
5
]
En general, si A ∈Mm×n(C),
1 ≤ j1 < j2 < . . . < jp ≤ m, 1 ≤ k1 < k2 < . . . < kq ≤ n,
A
j1,...,jp
k1,...,kq
:=
[
Ajrks
]p,q
r ,s=1
.
Submatrices
A =
 A11 A12 A13 A14 A15A21 A22 A23 A24 A25
A31 A
3
2 A
3
3 A
3
4 A
3
5
 , A1,32,3,5 =
[
A12 A
1
3 A
1
5
A32 A
3
3 A
3
5
]
En general, si A ∈Mm×n(C),
1 ≤ j1 < j2 < . . . < jp ≤ m, 1 ≤ k1 < k2 < . . . < kq ≤ n,
A
j1,...,jp
k1,...,kq
:=
[
Ajrks
]p,q
r ,s=1
.
Submatrices
A =
 A11 A12 A13 A14 A15A21 A22 A23 A24 A25
A31 A
3
2 A
3
3 A
3
4 A
3
5
 , A1,32,3,5 =
[
A12 A
1
3 A
1
5
A32 A
3
3 A
3
5
]
En general, si A ∈Mm×n(C),
1 ≤ j1 < j2 < . . . < jp ≤ m, 1 ≤ k1 < k2 < . . . < kq ≤ n,
A
j1,...,jp
k1,...,kq
:=
[
Ajrks
]p,q
r ,s=1
.
Plan
1 Notación para submatrices
2 Partición de una matriz en bloques
3 Multiplicación de matrices por bloques
4 Ejemplos y aplicaciones
Partición de una matriz en bloques
A =
E F
G H

r
m − r
s n − s
.
A1,...,r1,...,s = E , A
j
k = E
j
k (1 ≤ j ≤ r , 1 ≤ k ≤ s),
A1,...,rs+1,...,n = F , A
j
k = F
j
k−s (1 ≤ j ≤ r , s + 1 ≤ k ≤ n),
Ar+1,...,m1,...,s = G , A
j
k = G
j−r
k (r + 1 ≤ j ≤ m, 1 ≤ k ≤ s),
Ar+1,...,ms+1,...,n = H , A
j
k = F
j−r
k−s (r + 1 ≤ j ≤ m, s + 1 ≤ k ≤ n).
Plan
1 Notación para submatrices
2 Partición de una matriz en bloques
3 Multiplicación de matrices por bloques
4 Ejemplos y aplicaciones
Multiplicación de matrices por bloques
Proposición
Sean
A =
[
E F
G H
]
, B =
[
V W
X Y
]
.
Entonces
AB =
[
EV + FX EW + FY
GV + HX GW + HY
]
.
Otra forma de la misma regla
A =
[
A1,...,r1,...,s A
1,...,r
s+1,...,n
Ar+1,...,m1,...,s A
r+1,...,m
s+1,...,n
]
, B =
[
B1,...,s1,...,t B
1,...,s
t+1,...,p
B s+1,...,n1,...,t B
s+1,...,n
t+1,...,p
]
.
Entonces
(AB)1,...,r1,...,t = A
1,...,r
1,...,sB
1,...,s
1,...,t + A
1,...,r
s+1,...,nB
s+1,...,n
1,...,t ,
(AB)1,...,rt+1,...,p = A
1,...,r
1,...,sB
1,...,s
t+1,...,p + A
1,...,r
s+1,...,nB
s+1,...,n
t+1,...,p ,
(AB)r+1,...,m1,...,t = A
r+1,...,m
1,...,s B
1,...,s
1,...,t + A
r+1,...,m
s+1,...,n B
s+1,...,n
1,...,t ,
(AB)r+1,...,mt+1,...,p = A
r+1,...,m
1,...,s B
1,...,s
t+1,...,p + A
r+1,...,m
s+1,...,n B
s+1,...,n
t+1,...,p .
Demostremos que
(AB)1,...,rt+1,...,p︸ ︷︷ ︸
L
= A1,...,r1,...,sB
1,...,s
t+1,...,p + A
1,...,r
s+1,...,nB
s+1,...,n
t+1,...,p︸ ︷︷ ︸
R
.
L y R son matrices r × (p − t).
Ljk = (AB)
j
t+k =
n∑
u=1
AjuB
u
t+k =
s∑
u=1
AjuB
u
t+k +
n∑
u=s+1
AjuB
u
t+k
=
s∑
u=1
AjuB
u
t+k +
n−s∑
v=1
Ajv+sB
v+s
t+k
=
s∑
u=1
(A1,...,r1,...,s)
j
u(B
1,...,s
t+1,...,p)
u
k +
n−s∑
v=1
(A1,...,rs+1,...,n)
j
v (B
s+1,...,n
t+1,...,p )
v
k = R
j
k .
Plan
1 Notación para submatrices
2 Partición de una matriz en bloques
3 Multiplicación de matrices por bloques
4 Ejemplos y aplicaciones
Ejemplo: el producto de dos matrices
triangulares inferiores por bloques
[
E 0r×(n−s)
G H
][
V 0(n−s)×(p−t)
X Y
]
=
[
EV 0r×(p−t)
GV + HX HY
]
.
Ejemplo: en el producto de una matriz por un vector
separar el último renglón y la última columna
M =
[
A u
v> ω
]
, x =
[
y
ζ
]
.
Entonces
Mx =
[
Ay + uζ
v>y + ωζ
]
.
Ejemplo: multiplicación de matrices diagonales por bloques
 P1 0 00 P2 0
0 0 P3

 Q1 0 00 Q2 0
0 0 Q3
 =
 P1Q1 0 00 P2Q2 0
0 0 P3Q3
 .
Aqúı se usa una versión más general de la regla.
Algunas aplicaciones
Una demostración del teorema de Jacobi sobre el menor complementario.
Inversión de matrices por bloques:[
A B
C D
]−1
=
[
A−1 + A−1BS−1CA−1 −A−1BS−1
−S−1CA−1 S−1
]
, S := D − CA−1B .
Fórmula para la inversa de la suma (Woodbury):
(A + UCV )−1 = A−1 − A−1U
(
C−1 + VA−1U
)−1
VA−1.
El algoritmo de Strassen para multiplicar matrices.
	Notación para submatrices
	Partición de una matriz en bloques
	Multiplicación de matrices por bloques
	Ejemplos y aplicaciones