Álgebra Linear Computacional – Produto Matricial

Definição: $$A_{m\times p}$$ e $$B_{p\times n}$$ são duas matrizes. O produto é definido como a matriz $$C=AB$$, cujos elementos são da seguinte forma:

\[c_{ij}=\sum^{p}_{k=1}a_{ik}b_{kj}\].

Equivalência 1: A i-ésima linha da matriz $$C$$ corresponde à combinação linear das linhas de $$B$$, com os coeficientes da i-ésima linha de $$A$$.

De fato, os elementos da i-ésima linha de $$C$$ são da forma:

\[[c_{i1},…,c_{ip}]=[(a_{i1}b_{11}+…+a_{ip}b_{p1}), (a_{i1}b_{12}+…+a_{ip}b_{p2}),…,(a_{i1}b_{1n}+…+a_{ip}b_{pn})]  = \]

\[[a_{i1}b_{11},…,a_{i1}b_{1n}]+[a_{i2}b_{21},…,a_{i2}b_{22}]+…+[a_{ip}b_{p1},…,a_{ip}b_{pn}]=\]

\[a_{i1}\cdot [b_{11},…,b_{1n}]+a_{i2}\cdot[b_{21},…,b_{22}]+…+a_{ip}\cdot[b_{p1},…,b_{pn}]=\]

\[a_{i1}\cdot B^{(1)}+a_{i2}\cdot B^{(2)}+…+a_{in}\cdot B^{(n)}\].

Onde $$B^{(i)}$$ é a i-ésima linha da matriz $$B$$.

Equivalência 2: A j-ésima coluna da matriz $$C$$ corresponde à combinação linear das colunas de $$A$$, com os coeficientes da j-ésima coluna de $$B$$.

Com efeito, os elementos da coluna (j) da matriz $$C$$ são da forma apresentada a seguir:

\[C_{j}=[c_{1j},…,c_{mj}]=[(a_{11}b_{1j}+…+a_{1p}b_{pj}),…,(a_{m1}b_{1j}+…+a_{mp}b_{pj})]=\]

\[ b_{1j}[a_{11},…,a_{m1}]+…+b_{pj}[a_{1p},…,a_{mp}]=b_{1j}A_{1}+…+b_{pj}A_{p}\].

Onde $$A_{s}$$ é a coluna de $$A$$ com índice $$s$$.

Note que o produto matricial pode ser reescrito desta maneira:

\[AB=[\sum^{p}_{s=1}b_{s1}A_{s};…;\sum^{p}_{s=1}b_{sn}A_{s}]\]

Algoritmo (ikj): este algoritmo aproveita a Equivalência 1, demonstrada. Fixando o índice da linha (i),a respectiva linha de C receberá, no primeiro  (k), a multiplicação da linha (k) de B pelo escalar $$a_{ik}$$. Nos próximos passos de (k), este valor é somado às próximas multiplicações de linhas de B pelos respectivos escalares.

Para teste computacionais, faremos $$m=p=n$$, uma vez que a complexidade polinomial cúbica pode ser calculada para $$max\{m,n,p\}$$.

for i = 1:n
for k = 1:n
const=A(i,k); //armazena o k-esimo termo da i-ésima linha de A

for j = 1:n
C(i,j) = C(i,j) + const*B(k,j);  
end
end
end

Algoritmo (jki): este algoritmo aproveita a Equivalência 2. Fixada a coluna (j), a matriz $$C$$ é preenchida com as combinações lineares das colunas da matriz $$A$$. Primeiro,fixa a linha (i), e percorre todos os elementos da coluna de $$A$$.

for j =1:n
for k = 1:p

const = B(k,j);
for i = 1:m
C(i,j) = C(i,j) + A(i,k)*const;
end
end
end

Desempenho computacional

Algoritmos implementados: comportamento polinomial cúbico.