O Relatório Algebra Linear - Matrizes Esparsas

DANIEL DE LIMA PEREIRA 2017020165
THIAGO AUGUSTO MACEDO CARVALHO 2017020263
GABRIEL DE OLIVEIRA PINTO 2016015779

MÉTODOS DE ORDENAÇÃO

Comparação entre os métodos de ordenação e Fatoração através do Software MATLAB®

Relatório apresentado como requisito parcial de aprovação na disciplina Álgebra Linear Aplicada (ELE204) do curso de Engenharia Elétrica da Universidade Federal de Itajubá.

ITAJUBÁ

2017

SUMÁRIO

1. Introdução        3

2. Formulação Matemática        3

3. Resultados Numéricos        3

4. Conclusões        5

5. Referências Bibliográficas        6

---

1. INTRODUÇÃO

        Algumas matrizes utilizadas nos modelos matemáticos são de grande dimensão e muito esparsas, com isso, uma grande dificuldade surge ao tentar armazenar os dados, fazendo-se necessário a utilização de técnicas de programação para o armazenamento e manipulação destes elementos. Essas técnicas são denominadas como técnicas de esparsidade. Para isso, se faz necessária a utilização de grafos e matrizes simétricas, fazendo também uso de listas de adjacências, tabelas de conexões e listas encadeadas.

        Aplicadas as técnicas de esparsidade nas matrizes, deve-se também analisar as fatorações LU destes sistemas esparsos, o que deixará claro a importância dos esquemas de ordenação que têm como intuito minimizar a criação dos fill-ins – novos elementos não nulos – nos sistemas triangulares.

1. FORMULAÇÃO MATEMÁTICA

        Para a realização deste trabalho utilizou-se a plataforma MATLAB, fazendo uso de determinadas funções deste software para a fatoração, ordenação e análise dos dados cedidos pelo professor, comparando também a diferença entre os tempos de implementação de cada código. Segue abaixo as funções utilizadas para a realização do trabalho. O código encontra-se anexado a este relatório.

• tic toc: calcula o tempo de execução de determinada função;
• qr(): realiza a fatoração QR de determinada matriz;
• spy(): fornece a esparsidade da matriz;
• lu(): realiza a fatoração LU de determinada matriz;
• amd(): realiza a ordenação de grau mínimo;
• colamd(): realiza a ordenação de grau mínimo aproximada das colunas de determinada matriz;
• colperm(): Ordenação de coluna dispersa com base em contagem diferente de zero;

1. RESULTADOS NUMÉRICOS

        Realizadas todas as análises exigidas pelo docente, os seguintes resultados foram encontrados:

• Fatoração QR

Sem permutação:

mat_ieee14 - 0.040901s

mat_ieee30 - 0.084482s

mat_sin340 - 0.189510s

mat_sin730 - 1.561533s

Com permutação (amd):

mat_ieee14 - 0.025232s.

mat_ieee30 - 0.025456s

mat_sin340 - 0.057127s

mat_sin730 - 0.358958s

Com permutação (colamd):

mat_ieee14 - 0.021375s

mat_ieee30 - 0.025923s

mat_sin340 - 0.063628s

mat_sin730 - 0.358424s

Com permutação (colperm):

mat_ieee14 - 0.027094s

mat_ieee30 - 0.021390s

mat_sin340 - 0.070470s

mat_sin730 - 0.449398s

• Fatoração LU

Sem permutação:

mat_ieee14 - 0.011182s

mat_ieee30 - 0.010429s

mat_sin340 - 0.037747s

mat_sin730 - 0.217735s

Com permutação (amd):

mat_ieee14 - 0.026182s

mat_ieee30 - 0.024184s

mat_sin340 - 0.050610s

mat_sin730 - 0.243206s

Com permutação (colamd):

mat_ieee14 - 0.022182s

mat_ieee30 - 0.020871s

mat_sin340 - 0.049880s

mat_sin730 - 0.277510s

Com permutação (colperm):

mat_ieee14 - 0.020169s

mat_ieee30 - 0.020653s

mat_sin340 - 0.050084s

mat_sin730 - 0.244129s

        

        As imagens das fatorações de cada matriz encontram-se anexadas a este relatório.

1. CONCLUSÕES

        Finalizado o trabalho, foi possível concluir que utilizando a fatoração LU sem permutação o processo é mais rápido, enquanto fazendo uso da fatoração QR com permutação, é necessária uma menor quantidade de tempo. Entretanto, no uso da fatoração LU sem ordenação o número de fill-ins criados é muito maior, desta forma, fazendo valer a pena utilizar a ordenação também na fatoração LU.

---

1. REFERÊNCIAS BIBLIOGRÁFICAS

COSTA, Antônio J. A. Simões; DE ALMEIDA, Kátia C. Métodos de Ordenação e de Armazenamento de Matrizes Esparsas, p. 1.

---

ANEXOS

Mat1=mat_ieee14
Mat2=mat_ieee30
Mat3=mat_sin340
Mat4=mat_sin730

tic;
[Q,R] = qr(Mat1);
toc;
Spy (Q);
Spr (R);

[L,U] = lu(Mat1);
Spy (L);
Spy (U);

tic;
[Q,R] = qr(Mat2);
toc;
Spy (Q);
Spr (R);

[L,U] = lu(Mat2);
Spy (L);
Spy (U);

tic;
[Q,R] = qr(Mat3);
toc;
Spy (Q);
Spr (R);

[L,U] = lu(Mat3);
Spy (L);
Spy (U);

tic;
[Q,R] = qr(Mat4);
toc;
Spy (Q);
Spr (R);

[L,U] = lu(Mat4);
Spy (L);
Spy (U);

S1= Mat1'* Mat1
S2= Mat2'* Mat2
S3= Mat3'* Mat3
S4= Mat4'* Mat4

p1= amd(S1);
p2= amd(S2);
p3= amd(S3);
p4= amd(S4);

tic;
[Q,R]= qr(Mat1(p1,p1));
toc;
Spy (Q);
Spr (R);