A multiplicação de matrizes e seu custo

Compor transformações

O produto $AB$ é a transformação obtida aplicando primeiro $B$ e depois $A$: $(AB)\mathbf{x}=A(B\mathbf{x})$. A entrada $(i,j)$ do produto é a linha $i$ de $A$ multiplicada escalarmente pela coluna $j$ de $B$, então os tamanhos precisam combinar: uma matriz $m\times n$ vezes uma $n\times p$ dá uma $m\times p$. O produto é associativo, $(AB)C=A(BC)$, e distributivo sobre a soma, mas em geral não é comutativo: $AB\neq BA$, porque a ordem de duas ações importa.

Calcular $AB$ para uma matriz $m\times n$ e uma $n\times p$ custa $mnp$ multiplicações-somas (cerca de $2mnp$ operações de ponto flutuante). Para duas matrizes $n\times n$ são $n^3$: dobrar $n$ multiplica o trabalho por oito. Uma matriz vezes um vetor custa só $n^2$. Como o produto é associativo, a posição dos parênteses não muda o resultado, mas pode mudar muito o custo.

• Regra dos tamanhos: $(m\times n)(n\times p)=(m\times p)$; os tamanhos internos devem coincidir.
• Não comutativo: $AB\neq BA$ em geral, então nunca troque os fatores.
• Custo: $mnp$ multiplicações-somas; matriz vezes vetor $n^2$, matriz vezes matriz $n^3$.

Lab: o que é avaliado

• O produto AB20 pts
• O produto BA15 pts
• O tamanho de um produto10 pts
• Contar multiplicações-somas15 pts
• Duas formas de agrupar20 pts
• Por que o agrupamento importa20 pts