Projeto: Custo real da LU

Neste projeto queremos verificar se o tempo gasto no cálculo da decomposição LU é proporcional ao número de operações de ponto flutuante.

Quando estudamos a decomposição LU em uma aula anterior, contamos o número de operações de ponto flutuante necessárias para o cáculo das matrizes $L$ e $U$, em termos da ordem da matriz. Se $A \in\mathbb{R}^{n\times n},$ vimos que no cálculo de $L$ e $U$ são consumidas $$ {2\over 3}n^3 + {\cal O}(n^2) $$ operações de ponto flutuante. Quando discutimos o algoritmo da decomposição LU, não nos preocupamos em considerar outros fatores (se é que existem) que poderiam impactar no custo computacional.

Sabendo que o computador realiza um certo número de operações de ponto flutuante por segundo (esse numero é determinado pela velocidade do processador), conjecturamos que o tempo de execução de uma implementação para o cálculo da decomposição LU seja proporcional à quantidade de operações de ponto flutuante. Ou seja, denotando por $T(n)$ o tempo gasto no cálculo da decomposição LU de uma matriz quadrada de ordem $n,$ queremos verificar ou refutar que $$ T(n) \approx a n^3 $$ onde $a$ é uma constante que depende da velocidade do processador do seu computador.

Para tanto podemos conduzir um experimento controlado. Registre o tempo de execução da decomposição LU para matrizes $A$ de diferentes ordens. De posse desses dados, podemos utilizar o método de ajuste de curva por quadrados mínimos para determinar constantes $a$ e $b$ tais que $T(n)$ seja ajustado por $an^b$. Caso nossa conjectura esteja correta, $b$ deveria ser aproximadamente $3$. Vamos descobrir?

Para o desenvolvimento deste projeto, siga o roteiro, no menu lateral.

$\newcommand{\fl}{\mbox{fl}}$

Comece medindo o tempo de execução da decomposição LU. Para isso, o primeiro a decidir é qual implementação analisar. Podemos estudar uma implementação que nós mesmos tenhamos feito ou analisar a implementação da decomposição LU que encontramos em um pacote computacional como o Octave. De qualquer forma, normalmente o cálculo da decomposição é rápido. Para reduzir imprecisões ou flutuações nos tempos medidos, repita diversas vezes o mesmo cálculo da decomposição e calcule a média dos tempos medidos em cada execução. Isto tornará os resultados mais confiáveis.

Durante os teste, para que os resultados sejam mais confiáveis, é melhor você se certificar que não há outros programas consumindo poder de processamento de seu computador. Fechar todos os demais programas é uma boa medida.

1. Escreva um programa em Octave que, fornecido dois valores, digamos $n$ e $k,$ realize os seguintes passos: (1) crie uma matriz aleatória de ordem $n$ e (2) repita $k$ vezes o cálculo da decomposição LU dessa matriz. Esse programa deve retornar o tempo médio gasto nas decomposições LU. Para medir o tempo de execução use as funções tic e toc do Octave. Por exemplo:
   
   

   n = 100;
   A = rand(n,n);
   tic; [L,U,P] = lu(A); tempo_s = toc
   tempo_s = 2.4140e-03
   

   Tome o cuidado de medir apenas o tempo gasto na decomposição LU e não na geração da matriz aleatória. Além disso, uma vez gerada a matriz de ordem $n$, utilize-as em todas as replicatas (não é necessário gerar uma nova matriz para cada execução, dado que é razoável supor que os valores das entradas da matriz não alteram o custo computacional).
2. Crie uma tabela com os tempos médios de cálculo da decomposição LU em função da ordem da matriz de entrada. Para tanto, comece com valores de $n$ pequenos, digamos $100$ e progrida de forma significativa até valores grande de $n,$ digamos $100.000$ (a depender da capacidade do seu computador). Espace os valores de $n$ de forma adequada e representativa (use o bom senso). A título de sugestão considere 20 valores distintos para $n$ dentro do intervalo a ser analisado.
3. Descubra os coeficientes $a$ e $b,$ que fornecem o melhor ajuste no sentido de quadrados mı́nimos dos dados coletados à expressão $T(n) = an^b.$
   
   Aqui precisamos de certo cuidado. A função $an^b$ não é uma combinação linear de funções conhecidas. Logo, para podermos aplicar a técnica de ajuste de curvas por quadrados mínimos lineares precisamos linearizar a função (veja a aula sobre linearização).
   
   Se $T(n) = an^b$, então $$ z(n) \equiv \log(T(n)) = \log(an^b) = \log(a) + b \log(n) \equiv c_1 + c_2\log(n), $$ ou seja, definido $z(n) \equiv \log(T(n))$ podemos determinar pelo método de quadrados mínimos lineares os coeficientes $c_1$ e $c_2$ que melhor ajustam a função $$ c_1 + c_2 \log(n) $$ aos dados $z(n) \equiv \log(T(n))$. Determinados $c_1$ e $c_2,$ observe que $a = e^{c_1}$ e $b=c_2.$
4. Faça o gráfico da função ajustada sobreposta aos valores tabelados. O ajuste foi bom? Averigue a qualidade do ajuste, qualitativamente e quantitativamente.
5. O valor determinado para $b$ foi próximo de $3$ como a pensávamos? Se sim, comprovamos que o número de operações de ponto flutuante é o fator determinante no tempo computacional da execução do algoritmo. Se não, então deve haver outros fatores que também influenciam o tempo de execução do método. Quais poderiam ser estes fatores?