Algoritmo e esforço computacional

O custo de algoritmos para resolução de sistemas lineares é tradicionalmente medido contando-se quantas operações de ponto flutuante são realizadas. Assim, podemos comparar algoritmos distintos, para um mesmo problema, em termos do esforço computacional que cada um demanda.

No caso do algoritmo para a resolução de sistemas triangulares, como essa tarefa é usualmente realizada como um passo interno de algoritmos maiores, conhecer o custo computacional deste permite computar o custo computacional daqueles.

Para a contagem do número de operações é útil conhecer três identidades básicas: $$ \begin{align*} \displaystyle{\sum_{k=1}^n}\, 1 &= n \\[6pt] \displaystyle{\sum_{k=1}^n}\, k &= \displaystyle{n(n+1)\over 2} \\[6pt] \displaystyle{\sum_{k=1}^n}\, k^2 &= \displaystyle{n(n+1/2)(n+1)\over 3} \end{align*} $$

Na contagem de operações de ponto flutuante, contribuem igualmente todas as operações aritméticas (somas, subtrações, produtos e divisões). Outras operações básicas, como o cálculo de uma raiz quadrada, também são contadas de forma equivalente, pois, mesmo sendo mais caras, em processadores moderno, seu custo é da ordem do custo de operações aritméticas.

Sob a hipótese que os elementos da diagonal da matriz $A$ do sistema linear são não nulos, um algoritmo para resolver um sistema triangular superior está apresentado a seguir.

O número de operações de ponto flutuante para este algoritmo é computado como $$ \begin{align*} 1 + \sum_{k=1}^{n-1} \left[ \left(\sum_{j=k+1}^n 2\right) + 1\right] & = 1 + \sum_{k=1}^{n-1} \left[ 2(n-k) +1\right]\\ & = 1 + (2n+1)(n-1) - 2\sum_{k=1}^{n-1} k \\ & = 2n^2 -n -2 {(n-1)n\over 2} = n^2. \end{align*} $$

Ordem: Dizemos que uma função $f:\mathbb{N}\to\mathbb{R}$ é da ordem de $n^p$ se existe constante $C$, finita, tal que $$\lim_{n\to \infty} \frac{f(n)}{n^p} = C.$$ Neste caso, denotamos $f(n) = {\cal O}(n^p)$.

Apesar da contagem acima ter sido feita de forma rigorosa, é usual que nos interessemos apenas pelo termo de ordem mais alta no resultado. Por exemplo, é suficiente saber que outro algoritmo demanda $2n^2 + {\cal O}(n)$ para concluir que esse outro algoritmo seria menos vantajoso que o apresentado aqui.

Por fim, é preciso destacar que a contagem do número de operações de ponto flutuante que um algoritmo consome em sua execução não é o único fator que influencia seu desempenho. Em computadores modernos, principalmente quando falamos de computação em dispositivos dedicados, como GPU's por exemplo , outros aspectos, como acesso a memória e nível de concorrência das operações são muito importantes, as vezes até sobrepujando uma eventual desvantagem no número de operações de ponto flutuante.

1. Escreva um algoritmo para a encontrar a resolução de um sistema linear triangular inferior e conte o número de operações de ponto flutuante realizadas quando o sistema tem $n$ equações e $n$ incógnitas.

2. Como ficaria o algoritmo no caso de um sistema triangular superior com $m$ equações e $n$ incógnitas, para $m\lt n$? Quantas operações esse algoritmo consumiria?

3. Será que o tempo de execução de um algoritmo é realmente proporcional ao número de operações de ponto flutuante? Usando o Octave, crie sistemas triangulares de diferentes ordens e resolva-os usando o algoritmo apresentado. Construa uma tabela relacionando a ordem da matriz, $n,$ o tempo de execução, $t(n),$ e o número de operações de ponto flutuante realizadas, $n^2.$ Veja se é possível afirmar que $t(n) \approx \alpha n^2,$ para alguma constante de proporcionalidade $\alpha.$ Você precisará testar com valores de $n$ grandes para que a medição do tempo seja significativa.
Dica: confira as funções rand, triu, tic, e toc.