Questão 05: Considere que você necessite avaliar z=(A+B)(x+y) onde A, B são matrizes conformáveis com os vetores x, y. Considere as seguintes alternativas e determine o número de operações de ponto flutuante de cada uma, indicando qual é a mais econômica ao final. Considere que A é m times n e que x, y são vetores n dimensionais.
a) Primeiro somar A+B, então somar x+y, e depois aplicar a soma (A+B) na soma (x+y).
Solução: O total de elementos em cada matriz é igual a mn. Assim, a soma (A+B) tem o custo O(m n). Para os vetores, a soma (x+y) tem o custo O(n). Esta primeira etapa tem um custo total da ordem de m n+n. A segunda operação (A+B)(x+y), envolve a mutiplicação de uma matriz C=(A+B) por um vetor coluna v=x+y, ou seja, temos o cálculo de m produtos escalares de vetores n dimensionais e m somas de n-1 termos, resultando em um custo de m(n-1) operações. O custo total é de 3 m n+n-m.
b) Distribuir, avaliar cada termo e então somar: z=A x+A y+B x+B y.
Solução: Cada termo (mutliplicação de matriz por vetor) possui o custo computacional de m n+m(n-1) operações. A soma entre os quatro vetores resultantes é realizada com 3 m operações. Custo total é de 4 m n+4 m ( n- 1) +3 m=8 m n-m.

Passo 1

O problema pede para calcular z = (A+B)(x+y) de duas formas e comparar o número de operações de ponto flutuante. O conteúdo envolvido é a contagem de custos em soma de matrizes, soma de vetores e multiplicação de matriz por vetor. Vamos usar que: a soma de duas matrizes m×n custa mn adições; a soma de dois vetores n-dimensionais custa n adições; e a multiplicação de uma matriz m×n por um vetor n-dimensional custa m·n multiplicações e m·(n−1) adições.

Passo 2

Na alternativa (a) fazemos primeiro A+B, depois x+y, e por fim C·v com C = A+B e v = x+y. O custo de cada etapa é:
CustoA+B = mn
Custox+y = n
CustoC,v = mtimes n + mtimes(n-1) = 2mn - m
Somando tudo:
$$
mn + n + (2mn - m) = 3mn + n - m
$$

Passo 3

Na alternativa (b) expandimos z = Ax + Ay + Bx + By. Cada multiplicação de matriz por vetor custa m·n multiplicações + m·(n−1) adições, ou seja, 2mn - m operações. Como há quatro termos, totalizamos 4·(2mn - m) = 8mn - 4m operações para os produtos. Depois somamos quatro vetores resultantes com 3m adições. Assim:
(8mn - 4m) + 3m = 8mn - m

Passo 4

Comparando os custos temos 3mn + n - m versus 8mn - m. Como n é positivo, concluímos que 3mn + n - m < 8mn - m.

Resposta

A opção (a) é mais econômica, com custo de 3mn + n - m operações de ponto-flutuante, em comparação a 8mn - m da opção (b).

Exercícios relacionados