Projeto: Custo real da LU
Quanto, de fato, demora a decomposição LU
Vamos lá?
Em outra aula, vimos qual o custo computacional, em termos do número de operações, da decomposição LU. Será que este resultado teórico pode ser validado com um experimento? Será que o tempo de execução de uma implementação da decomposição LU é determinado apenas pelo número de operações realizadas?
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
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
Para tanto podemos conduzir um experimento controlado. Registre o tempo de execução da decomposição LU para matrizes
Para o desenvolvimento deste projeto, siga o roteiro, no menu lateral.
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.
- Escreva um programa em Octave que, fornecido dois valores, digamos
e realize os seguintes passos: (1) crie uma matriz aleatória de ordem e (2) repita 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çõestic
etoc
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 , 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). - 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
pequenos, digamos e progrida de forma significativa até valores grande de digamos (a depender da capacidade do seu computador). Espace os valores de de forma adequada e representativa (use o bom senso). A título de sugestão considere 20 valores distintos para dentro do intervalo a ser analisado. - Descubra os coeficientes
e que fornecem o melhor ajuste no sentido de quadrados mı́nimos dos dados coletados à expressão
Aqui precisamos de certo cuidado. A função 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 , então ou seja, definido podemos determinar pelo método de quadrados mínimos lineares os coeficientes e que melhor ajustam a função aos dados . Determinados e observe que e - 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.
- O valor determinado para
foi próximo de 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?