Sistemas Lineares
AX=B
A11 A12 A13 ... A1N
X1 = B1
A21 A22 A23 ... A2N
X2
B2
.....................................
...
...
AN1 AN2 AN3 ... ANN
XN
BN
Eliminação de Gauss: transformar a matriz A numa matriz triangular
superior e resolver o sistema equivalente.
Algoritmo (matriz distribuída por colunas):
Paralelização (matriz A distribuída por colunas)
DO i=1, N
IF (tenho coluna i)
broadcast(ipivot,A(i,i)); elimina;
ELSE
receive(A(i,i)); elimina;
END IF
END DO
Resolve o sistema linear por backsubstitution
Paralelização da resolução de um sistema linear com matriz triangular
Algoritmo Série: N3 operações de vírgula flutuante
Algoritmo Paralelo:
i) resolver o primeiro subsistema dimensão N/P;
ii) broadcast N/P elementos da solução;
iii) fazer (N/P)2 op. Vírg. Flut. em simultâneo
iv) repetir para outros blocos