DESENVOLVIMENTO DE UM MODELO DE …uenf.br/Uenf/Downloads/POS-ENGPRODUCAO_2397_1190378971.pdf · DINÂMICO DE DADOS PARA RESOLUÇÃO DE SISTEMAS LINEARES ESPARSOS E SEU USO EM PROBLEMAS

DESENVOLVIMENTO DE UM MODELO DE ARMAZENAMENTO

DINÂMICO DE DADOS PARA RESOLUÇÃO DE SISTEMAS LINEARES

ESPARSOS E SEU USO EM PROBLEMAS DE OTIMIZAÇÃO NÃO

LINEARES

NILO AMÉRICO FONSECA DE MELO

UNIVERSIDADE ESTADUAL DO NORTE FLUMINENSE - UENF

CAMPOS DOS GOYTACAZES - RJ

NOVEMBRO - 2002




LINEARES


“Tese apresentada ao Centro de Ciências e

Tecnologia da Universidade Estadual do Norte

Fluminense, como parte das exigências para

obtenção de título de Doutor em Ciências de

Engenharia”.

Orientador: Prof. José Ramón Arica Chávez

CAMPOS DOS GOYTACAZES - RJ

NOVEMBRO - 2002

ii

Ficha catalográfica feita na Biblioteca do CCT UENF

MELO, Nilo Américo Fonseca.

Desenvolvimento de um Modelo de Armazenamento Dinâmico de Dados para Resolução de Sistemas Lineares Esparsos e seu uso em Problemas de Otimização Não Lineares. / Nilo Américo Fonseca de Melo -- [ Campos dos Goytacazes ], 2002.

x, 174 f. , enc.; 30 cm (CCT/UENF, D. Sc. Ciências de Engenharia - Engenharia de Produção, 2002).

Tese - Universidade Estadual do Norte Fluminense, CCT.

Bibliografia: f. 134 – 136.

1. Matrizes Esparsas. 2.Problemas Lineares Esparsos. 3. Programação não Linear. I. UENF.CCT II. Título.

CDD - 658.5

iii




LINEARES


“Tese apresentada ao Centro de Ciências e

Tecnologia da Universidade Estadual do Norte

Fluminense, como parte das exigências para

obtenção de título de Doutor em Ciências de

Engenharia”.

Aprovada em 21 de novembro de 2002.

Comissão Examinadora

_________________________________________________________ Prof. Carlos Alberto de Jesus Martinhon (Doutor, Eng. Sistemas) - UFF

_________________________________________________________ Prof. Geraldo Galdino de Paula Junior (Doutor, Eng. Sistemas) - UENF

_________________________________________________________ Profª. Gudelia Morales (Doutora, Eng. Sistemas) - UENF

_________________________________________________________ Prof. José Ramón Arica Chávez (Doutor, Eng. Sistemas) – UENF

Orientador

iv

DEDICATÓRIA

À minha filha Mariana.

À minha companheira Érika.

Aos meus pais, avós, irmãos e irmãs.

v

AGRADECIMENTOS

Ao professor José Ramón Arica Chávez, meu orientador, pela dedicação, incentivo e

amizade demonstrada ao longo de todo o desenvolvimento deste trabalho.

Aos professores do LEPROD/CCT/UENF, pelo auxilio

vi

Resumo da Tese apresentada ao CCT/UENF como parte dos requisitos necessários

para a obtenção do grau de Mestre em Ciências de Engenharia

DESENVOLVIMENTO DE UM MODELO DE ARMAZENAMENTO DINÂMICO DE

DADOS PARA RESOLUÇÃO DE SISTEMAS LINEARES ESPARSOS E SEU USO

EM PROBLEMAS DE OTIMIZAÇÃO NÃO LINEARES

Nilo Américo Fonseca de Melo

21 de Novembro de 2002

Orientador: José Ramón Arica Chávez

Área de Concentração: Engenharia de Produção

Neste trabalho, desenvolvemos um modelo dinâmico de armazenamento de

dados para matrizes esparsas onde serão guardados somente os elementos não

nulos da matriz. Tal modelo utiliza o conceito de lista duplamente encadeada de

ponteiros e é aplicado para a resolução de sistemas lineares esparsos utilizando o

processo de Eliminação Gaussiana. O modelo desenvolvido tem como principal

característica a capacidade de alterar o seu tamanho de acordo com a criação ou

eliminação elementos, durante os cálculos computacionais. Técnicas de

pivotamento são utilizadas para garantir uma escolha adequada do elemento pivô.

O processo de pivotamento é constituído pelo intercâmbio de linhas e colunas da

matriz, de acordo com critérios para tentar manter a esparcidade da matriz e a

precisão dos resultados.

Os conceitos anteriores são aplicados para o desenvolvimento de algoritmo

para resolução de problemas de otimização não lineares esparsos, utilizando o

método seqüencial quadrático.

vii

Abstract of the Thesis submitted to the CCT/UENF in partial fulfillment of the

requirements for the degree of Doctor of Sciences.

DEVELOPMENT OF A MODEL OF DYNAMIC STORAGE OF DATA FOR

RESOLUTION OF SPARSE LINEAR SYSTEMS AND HIS USE IN NO LINEAR

OPTIMIZATION PROBLEMS

Nilo Américo Fonseca de Melo

November 21, 2002.

Chair of Committee: José Ramón Arica Chávez

Major Subject: Industrial Engineering

In this work, we developed a dynamic model of data storage for sparse matrix

where only the non-zero elements of the matrix will be kept. Such a model use the

concept of double linked list of pointers and it is applied for the resolution of sparse

linear systems using Gaussian Elimination process. The developed model has as

main characteristic the capacity to alter his size in agreement with the creation or

elimination of elements, during the computer calculations. Pivotal techniques are

used to guarantee an appropriate choice of the element pivot. The pivotal process is

constituted by the exchange of lines and columns of the matrix, in agreement with

criteria trying to maintain the sparsity of the matrix and the precision of the results.

The previous concepts are applied for the algorithm development for resolution

of sparse no linear optimization problems, using the quadratic sequential method.

viii

SUMÁRIO

CAPÍTULO I - INTRODUÇÃO…………………………………….................................. 1

1.1 - Objetivo..............................................................................................................2

1.2 – Estrutura do presente trabalho .......................................................................2

CAPÍTULO II - EXPLORANDO ESPARCIDADE …………………………………........ 4

2.1 – Formas de Explorar a Esparcidade.................................................................4

2.1.1 – Forma Clássica .................................................................................5

2.1.2 – Forma Orientada a computador ........................................................5

CAPÍTULO III - MODELOS DE ARMAZENAMENTO ............................................. 10

3.1 – Um Modelo Simples de Armazenagem de Dados........................................12

3.2 – Um Modelo de Armazenamento Dinâmico (Zlatev 1991) ............................14

3.3 – Armazenamento dos preenchimentos..........................................................19

3.4 – Procedimento de Coleta de Lixo (“Garbage Collection”) ...........................26

3.5 – Espaços Livres ...............................................................................................33

3.6 – O uso de Lista Encadeada no modelo de armazenamento dinâmico........34

3.7 – Outros Modelos de Armazenamento ............................................................38

3.8 – Conceitos Preliminares..................................................................................39

3.8.1 – Variáveis .........................................................................................39

3.8.2 – O Tipo Ponteiro da Linguagem Pascal............................................40

3.8.3 – Listas Lineares ................................................................................41

3.8.3.1 – Encadeamento de Listas ..........................................................41

3.9 – O Modelo de Armazenamento Proposto ......................................................43

3.10 – O cálculo da Eliminação Gaussiana no modelo proposto........................52

CAPÍTULO IV - ESTRATÉGIAS DE PIVOTAMENTO ............................................ 70

4.1 – Pivotamento para Matrizes Densas ..............................................................67

ix

4.2 – Conceitos básicos para construção de estratégias de pivotamento para

matrizes esparsas. ..................................................................................................70

4.3 – Grupo 1: Estratégias de pivotamento com mudanças a priori...................73

4.4 – Grupo 2: Estratégias de pivotamento baseadas no uso da função de custo

de Markowitz............................................................................................................78

4.5 – Grupo 3: Estratégias de pivotamento baseadas em uma minimização local

de preenchimentos .................................................................................................86

4.6 – Escolha da estratégia de Pivotamento.........................................................89

CAPÍTULO V - MÉTODO SEQÜENCIAL QUADRÁTICO ....................................... 94

5.1 – Descrição do Método MSQ............................................................................93

5.2 – Algoritmo Seqüencial Quadrático Básico (PSQ) .........................................96

5.3 - Extensão do algoritmo básico PSQ incluindo Restrições de Desigualdade

..................................................................................................................................97

5.4 – Função de Mérito..........................................................................................100

5.5 – Algoritmo de solução...................................................................................103

CAPÍTULO VI – TESTES E RESULTADOS NUMÉRICOS .................................. 108

CAPÍTULO VII - CONCLUSÕES E RECOMENDAÇÕES ..................................... 130

REFERÊNCIAS BIBLIOGRÁFICAS ..................................................................... 133

ANEXOS ................................................................................................................ 136

x

SIGLAS

CN – Column Number (Número da Coluna)

EG – Eliminação Gaussiana

FPO – Fluxo de Potência Ótimo

CL – Coleta de Lixo

K.K.T. – Karush-Kuhn-Tucker

MSQ – Método Seqüencial Quadrático

NZ –Número de Elementos não Nulos (Non Zero)

PSQ - Programação Seqüencial Quadrática

RN – Row Number (Número da Linha)

xi

1

CAPÍTULO I

INTRODUÇÃO

Existem vários problemas que a sua formulação matemática envolve a

resolução de grandes sistemas de equações lineares, do tipo bAx = , onde muitos

elementos da matriz são nulos. Estes problemas são chamados de problemas de

Grande Porte Esparsos. Existem técnicas específicas para o armazenamento e a

realização dos cálculos para evitar a manipulação destes elementos nulos. Uma

classe de problemas que pode ser usada como exemplo de problemas de grande

porte esparsos é a classe dos problemas de otimização de fluxo em rede, onde

podemos destacar os seguintes exemplos:

A

• Fluxo de petróleo em uma rede composta de tubulações, poços e

pontos de entrega;

• Fluxo de informações em uma rede de computadores;

• Fluxo de energia elétrica em uma rede composta de geradores,

consumidores e cabos de transmissão.

O problema de otimização do fluxo de energia elétrica(Carpentier-1962),

também conhecido como Problema de Fluxo de Potência Ótimo (FPO), foi a principal

motivação para o desenvolvimento do modelo de armazenamento e o método de

resolução de sistemas lineares de equações com matrizes esparsas, assim como

2

sua aplicação na resolução de problemas não lineares esparsos de grande porte

aqui apresentados.

1.1 - Objetivo

O presente trabalho tem como objetivo o desenvolvimento e implementação

de um modelo de armazenamento e de um algoritmo para resolver sistemas de

equações lineares esparsos ( bAx = ) utilizando esta estrutura, desenvolvendo-se,

também, um método para resolução de problemas de otimização não lineares

esparsos.

O método utilizado neste trabalho para solução de problemas de programação

não linear é baseado no Método Seqüencial Quadrático (MSQ). Neste método, o

problema de programação não linear é resolvido através da formulação de uma

seqüência de subproblemas quadráticos cujas soluções convergem a um ponto que

satisfaz as condições de Karush-Kuhn-Tucker (K.K.T.) do problema original.

1.2 – Estrutura do presente trabalho

Neste trabalho, apresentamos o desenvolvimento de um modelo de

armazenamento e um método para resolver sistemas de equações lineares, bem

como a sua aplicação na implementação de um algoritmo para solução de

problemas de otimização não lineares de grande porte utilizando o Método

Seqüencial Quadrático. Está organizado em sete capítulos assim distribuídos:

• Capítulo 1: introdução.

• Capítulo 2: descreve as formas de explorar a esparcidade (a Forma

Clássica e a Forma Orientada a Objeto).

3

• Capítulo 3: apresenta e compara vários modelos de armazenamento e

manipulação de dados para matrizes esparsas, desenvolvendo-se um

novo modelo baseado nas vantagens dos modelos apresentados.

• Capítulo 4: apresenta e compara as técnicas de pivotamento para

matrizes esparsas.

• Capítulo 5: descreve o Método Seqüencial Quadrático e aplica o

modelo de armazenamento de dados desenvolvido no capítulo 3 e as

técnicas de pivotamento mostradas no capítulo 4 para adaptar tal

método para o caso de problemas esparsos.

• Capítulo 6: detalha os resultados computacionais obtidos com a

implementação aplicada a alguns problemas testes.

• Capítulo 7: discute as conclusões e as recomendações para o

aprimoramento do algoritmo apresentado.

4

CAPÍTULO II

EXPLORANDO ESPARCIDADE

Seja uma matriz comum, ou seja, A

não tem nenhuma propriedade ou estrutura especial (A não é necessariamente

simétrica ou definida positiva). A matriz A é chamada de esparsa se muitos

elementos n) ..., 2, 1,j m, ..., ,2 ,1(

))( , , , nAranknmn(mRA mxn =∈∈≥∈ ΝΝ

==∈ iAij são iguais a zero. Nestes casos, o

tempo computacional e o espaço necessário para o armazenamento dos dados do

problema podem ser reduzidos quando alguma técnica de esparcidade é explorada.

Mais ainda: vários problemas esparsos só poderão ser resolvidos com sucesso se

a

a

esparcidade for explorada.

2.1 – Formas de Explorar a Esparcidade

é explorada,

existem duas diferentes formas de tratar a esparcidade de uma matriz:

- forma orientada à computação.

Nos casos em que nenhuma propriedade particular da matriz

- A forma clássica;

A

5

2.1.1 – Forma Clássica

Na forma clássica de explorar a esparcidade, tenta-se armazenar somente

elementos não nulos na memória do computador e trabalhar somente com estes

elementos durante os cálculos computacionais.

Algumas variações da definição anterior podem ser encontradas em muitas

aplicações. Por exemplo: além dos elementos nulos, em algumas aplicações

evitam-se armazenar alguns elementos não nulos, como no caso dos elementos da

diagonal principal da matriz triangular inferior L que se tornarão iguais a 1 durante o

processo de Eliminação Gaussiana (EG).

Deve-se ainda enfatizar que alguns elementos não nulos podem se tornar

iguais a zero, durante os cálculos computacionais. Tais elementos são normalmente

mantidos na memória do computador, quando utilizamos a forma clássica de

explorar a esparcidade. Isto significa que iremos trabalhar com alguns elementos

nulos durante os cálculos computacionais o que implica um acréscimo no tempo

computacional e no espaço necessário para o armazenamento dos dados.

É evidente que a forma clássica de explorar a esparcidade é influenciada pela

precisão dos cálculos, onde os elementos da matriz (especialmente os elementos

nulos) serão calculados utilizando aritmética exata e, mais ainda, todos os cálculos

necessários durante o processo de solução do sistema serão executados da mesma

maneira.

2.1.2 – Forma Orientada a computador

Na forma orientada a computador de explorar a esparcidade, evita-se

trabalhar com elementos não nulos de “pequena” magnitude. Torna-se óbvio que é

preciso definir um critério apropriado para determinar se um elemento deve ser

desprezado. Em geral, a definição de tal critério não é feita tão facilmente. Por

6

outro lado, algumas classes de problemas esparsos somente poderão ser tratadas

nos computadores atuais se for utilizada a forma orientada à computação.

Quando utilizamos computadores de aritmética aproximada, os cálculos

computacionais não serão efetuados utilizando a aritmética exata. Nestes casos,

elementos não nulos são produzidos enquanto cálculos exatos produziriam

elementos nulos.

Para ilustrar as afirmações anteriores, considere a solução do seguinte

sistema de equações algébricas:

Ax=b (2.1) ))( , , ,( 11 nArankRxRbRA nxnxnxn =∈∈∈

Para resolver tal sistema iremos utilizar um processo conhecido como

Eliminação Gaussiana (EG) onde os elementos da matriz A serão decompostos em

duas matrizes triangulares nxnRL ∈ nxnRU ∈ . Os cálculos efetuados durante o

processo EG são baseados nas seguintes f

e

órmulas:

++=== −+ 11

n, ..., 2, s1, sj i, 1,-n ..., 2, 1, s,a )(a a - aa )s(sj

(s)ss

(s)is

)s(ij

)s(ij

(2.2)

n ..., 2, 1,ji, ,Aaa ,a ij(1)ij

)s(ss =∈=≠ 0

onde:

s - estágio do processo de Eliminação Gaussiana já executado.

Os elementos da matriz triangular inferior L são dados por:

n ..., 2,j 1,ji 1,-n ..., 2, 1,j ,aa

l )j(jj

)j(ij

ij ++==−= (2.3)

n, ..., 2, 1,i , == 1 lii (2.4)

(2.5) 1-j ...., 2, 1,i n, ..., 3, 2,j ,lij === 0

7

Os elementos da matriz triangular superior U são dados por:

(2.6) n, ..., 1,i i,j n, ..., 2, 1,i ,a )s(ijij +=== u

1- i ..., 2, 1,j n, ..., 3, 2,i ,uij === 0 (2.7)

Pode-se observar de 2.2 que elementos )a 1+ podem ser não nulos apesar de

)

ij

s(ij

)s(ija serem iguais a zero. Isto acontece quando e são não nulos. O

elemento a criado durante os cálculos da EG, enquanto , é conhecido

como preenchimento (“fill-in”).

nte os cálculos são executados com erros

de arredondamento, desta forma temos:

U = A + E ,

s(isa )s(

sja

01 ≠+ )s( 0=)s(ija

Se os cálculos forem executados usando aritmética exata, então o produto LU

será igual à matriz A . Contudo, geralme

n x nRE ∈L (2.8)

ter fatores L e U mais densos

do que os obtidos com utilização da aritmética exata.

A matriz E é chamada de matriz de perturbação e contém a correção dos

erros de arredondamentos gerados nos cálculos. Técnicas de pivotamento são

normalmente utilizadas no intuito de tentar manter os elementos da matriz E os

menores possíveis e tentar diminuir o número de preenchimentos durante os

cálculos. Quando a aritmética aproximada é utilizada, então o )s(ija pode ser um

elemento não nulo até mesmo quando o valor exato de )s(ija 1+ deveria ser igual a zero

(ou, em outras palavras, preenchimentos podem ser produzidos também por causa

de erros computacionais, erros de arredondamento). Isto significa que se aplicarmos

a forma orientada a computador então poderemos ob

1+

8

É óbvio que se o valor exato de )a 1+ é zero, enquanto o valor calculado é

diferente de zero, então espera-se que o valor calculado seja, de alguma forma,

pequeno. Desta forma poderá ser vantajoso atribuir valores nulos a quando

estes forem menores do que um parâmetro definido. Isto significa que pequenos

elementos serão removidos da memória do computador e não serão envolvidos nos

cálculos. Estes elementos serão ditos eliminados (“dropped”) durante a EG.

s(ij

)s(ija 1+

A maneira mais simples de eliminar um elemento poderá ser descrita a seguir.

Seja T um número não negativo. Então um elemento obtido durante EG é

considerado pequeno e desprezado se:

n) ..., 2, s1,sj n, ..., 2, s1,si 1,-n ..., 2, 1, (s T a )s( ≤+1ij ++=++== (2.9)

á conduzir a

to pode ser feito por um processo de refinamento

iterativo conforme pode ser observado a seguir:

=+==−= +−1 (2.10)

o

O parâmetro T, usado no critério acima, é chamado de tolerância de

eliminação. Torna-se claro que a aplicação de uma tolerância de eliminação nos

cálculos computacionais poder fatores imprecisos L e U. Então, se isto

acontecer, uma aproximação b)LU(x1−= da solução exata bAx será,

normalmente, imprecisa. Algumas vezes é necessário tentar recuperar a precisão

perdida pela eliminação e is

1 1−=

1-p ..., 2, 1,i ,dxx ,r)LU(d ,Axbr ii1iiiii

nde:

ir – vetor de resíduos;

di – vetor de correções;

p – e parada, ver

Stewart (1973), Voevodin (1977), Wilkinson (1963 e 1965);

ri 0

número de iterações definido por algum critério apropriado d

∞→→

i

9

a solução

mais próxima da solução exata, usando um critério de parada apropriado.

m ndo

consideramos T = 0 e aceitando a primeira aproximação como solução final.

tacional será

alcançada somente quando duas condições a seguir forem satisfeitas:

Muitos elementos serão retirados durante a EG.

- to iterativo é convergente e a taxa de convergência é

uficientemente rápida.

A partir de uma solução aproximada 1x poderá ser calculada um

Se a tolerância de eliminação T é suficientemente grande, então os fatores

calculados L e U serão geralmente esparsos e algumas vezes mais esparsos do que

os fatores calculados utilizando a forma clássica (sem a retirada de “pequenos”

elementos). A forma clássica de explorar a esparcidade poderá ser considerada

como um caso particular da forma orientada a co putação, obtida qua

1x

Se um fator de eliminação T grande é utilizado na forma orientada à

computação, então se espera que o armazenamento seja reduzido, porque muitos

elementos serão desconsiderados durante os cálculos computacionais.

Conseqüentemente, o cálculo computacional também será reduzido, isto porque a

redução do tempo computacional para realizar a Eliminação Gaussiana é

normalmente maior do que o aumento do tempo computacional gasto com

acréscimos de iterações, com o refinamento interativo necessário para recuperar a

precisão perdida com um fator de “dropped” T grande. Contudo, é bastante claro

que a redução tanto do armazenamento quanto do tempo compu

-

O processo de refinamen

s

Se estas duas condições não forem satisfeitas, é preferível utilizar a forma

clássica. Exemplos comparando a forma clássica com a forma orientada a

computação podem ser observados em Zlatev (1991), onde algumas formas de

tratar a esparcidade são comparadas pelo espaço necessário para o

armazenamento dos elementos dos fatores L e U e tempo computacional gasto nos

cálculos. Os resultados lá encontrados demonstram que, para algumas classes de

10

rio apropriado de eliminação

T para eliminação de “pequenos” elementos não nulos.

matrizes, a forma clássica é mais eficiente do que a forma orientada à computação.

Contudo, existem classes de matrizes em que a forma orientada à computação

consegue melhores resultados do que a forma clássica, ressaltando que alguns

problemas esparsos somente podem ser tratados nos computadores atuais quando

a forma orientada à computação é utilizada com um crité

11

CAPÍTULO III

MODELOS DE ARMAZENAMENTO

Nos casos de problemas com matrizes esparsas, uma questão importante na

implementação de códigos computacionais é determinar a forma em que os

elementos não nulos da matriz serão armazenados na memória do computador. Um

modelo eficiente de armazenamento deve satisfazer a algumas exigências onde

podemos destacar:

- A redução da quantidade de informação a ser armazenada;

- A simplicidade do modelo de armazenamento sob o ponto de vista do usuário;

- A eficiência na execução de diferentes operações básicas de Álgebra Linear;

Tais exigências trabalham em direções opostas, sendo uma tarefa difícil

encontrar um modelo que atenda, de forma satisfatória, tais requisitos.

Existem vários modelos de armazenamento dos elementos não nulos de uma

matriz esparsa.

Um modelo de armazenamento, observado em ZLATEV (1991), é descrito a

seguir:

12

3.1 – Um Modelo Simples de Armazenagem de Dados

Seja uma matriz A esparsa e seja NZ o número de elementos não nulos de A.

As informações sobre os elementos não nulos de A serão armazenados inicialmente

em três vetores: um de números reais AORIG e dois de números inteiros RNORIG e

CNORIG, de tamanho no mínimo igual a NZ. A notação usada nos nomes dos

vetores será explicada a seguir:

- A letra “A”, utilizada no primeiro vetor, refere-se ao fato de que os elementos

não nulos da matriz A serão armazenados no primeiro vetor.

- “RN” é a abreviatura de “Row Number” (número da linha) e refere-se ao fato

de que os números das linhas dos elementos da matriz A serão armazenados

no vetor RNORIG.

- “CN” é a abreviatura de “Column Number” (número da coluna) e refere-se ao

fato de que os números das colunas dos elementos da matriz A serão

armazenados no vetor CNORIG.

- “ORIG” é a abreviatura de “Original” e refere-se ao fato de que os três vetores

mencionados anteriormente (AORIG, RNORIG e CNORIG) irão armazenar os

elementos não nulos da matriz original A, os seus números de linhas e seus

números de colunas, respectivamente.

Um dos modelos mais simples de armazenamento consiste no

armazenamento dos elementos da matriz A nas primeiras NZ posições do vetor

AORIG, sendo que a ordem em que estes serão estocados é arbitrária. Contudo, se

um elemento ij da matriz A é armazenado na posição K ,ou seja,

AORIG(K)= ij , então os elementos da posição K dos vetores RNORIG e CNORIG

deverão conter a linha e a coluna deste elemento: RNORIG(K)=i e CNORIG(K)=j.

Somente os elementos não nulos da matriz A junto com o número de suas linhas e

colunas serão armazenados nos vetores AORIG, RNORIG e CNORIG,

respectivamente.

a )NZK( ≤≤1

a

13

O modelo de armazenamento apresentado anteriormente pode ser utilizado

em operações em que os elementos da matriz A permanecem inalterados durante

operações básicas de álgebra linear. Operações deste tipo são ditas “estáticas” e o

modelo de armazenamento para tais operações é também conhecido como “modelo

de armazenamento estático”. Alguns exemplos de operações estáticas podem ser

observados a seguir:

- Cálculo do produto entre vetores e matrizes;

- Cálculo do vetor residual do processo de refinamento iterativo ( ); Axbr −=

- Cálculo da norma um de uma matriz;

- Cálculo da Max-norma de uma matriz.

Se os elementos da matriz A variam durante a execução de operações de

álgebra linear, tais operações são ditas “dinâmicas”. Algumas operações dinâmicas

que não produzem novos elementos não nulos (preenchimentos), conhecidas como

operações simplesmente dinâmicas, podem ser eficientemente executadas

utilizando o modelo de armazenamento apresentado anteriormente. Dentre estas

operações podemos destacar:

- Multiplicação de um vetor por uma constante;

- Escalonamento de uma matriz.

Contudo, algumas operações algébricas importantes não podem ser

executadas utilizando o modelo de armazenagem descrito anteriormente. Dentre

estas podemos ressaltar:

- Eliminação Gaussiana;

- Transformações Ortogonais.

Normalmente, tais operações transformam alguns elementos nulos em

elementos não nulos durante os cálculos, isto é, poderão aparecer preenchimentos

14

durante a performance destas operações, alterando o padrão de esparcidade da

matriz. Estas operações são conhecidas como operações essencialmente

dinâmicas.

Nas operações onde os elementos não variam (operações estáticas) ou em

que os elementos variam sem alteração do padrão de esparcidade (operações

simplesmente dinâmicas), os modelos de armazenamento estático, como o

apresentado anteriormente, são largamente utilizados pela sua simplicidade.

Contudo, nas operações essencialmente dinâmicas, é necessário um modelo de

armazenamento que facilite a inclusão de novos elementos imediatamente após a

produção dos mesmos, ao qual denominamos “dinâmico” e será descrito a seguir.

3.2 – Um Modelo de Armazenamento Dinâmico (Zlatev 1991)

Durante operações de Álgebra Linear essencialmente dinâmica,

preenchimentos poderão aparecer independente do algoritmo utilizado. O modelo

de armazenamento deve facilitar o armazenamento destes elementos e,

conseqüentemente, auxiliar no próprio cálculo visando à redução do tempo

computacional.

Para facilitar a explanação iremos considerar durante todo o trabalho a

utilização da Eliminação Gaussiana como método de resolução de um sistema linear

de equações do tipo:

A 1 x mn x m1 =≥∈∈ (3.1) n,rank(A) n,m ,Rb ,RA ,Rx ,bx x n∈=

Assuma que o modelo de armazenamento estático apresentado na Seção 3.1

é inicialmente utilizado para estocar os elementos da matriz A. Em outras palavras,

os elementos da matriz A serão armazenados nas primeiras NZ posições do vetor de

elementos reais AORIG, enquanto o número da linha e da coluna de cada elemento

será armazenado nas posições correspondentes aos vetores de elementos inteiros

15

RNORIG e CNORIG, respectivamente. Considere como exemplo a seguinte matriz

A com 12 elementos não nulos (NZ=12):

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

=

0.90.200000.20.1000.300.30.10

0000.10.20.90.3006.0

A (3.2)

Usando o modelo de armazenamento estático anteriormente mencionado,

teremos:

Posição Vetor 1 2 3 4 5 6 7 8 9 10 11 12 AORIG 9.0 1.0 9.0 2.0 2.0 3.0 6.0 1.0 1.0 2.0 3.0 3.0RNORIG 5 4 1 4 2 3 1 3 2 5 1 3 CNORIG 5 3 5 4 1 5 1 2 2 4 4 3

Podemos observar que os elementos são armazenados sem obedece

nenhuma ordem específica.

O modelo de armazenamento dinâmico de Zlatev irá usar uma rotina

ordenação que, a partir do modelo estático apresentado anteriormente, irá reorde

os elementos dos vetores AORIG, RNORIG e CNORIG para realizar a Elimina

Gaussiana de forma eficiente, utilizando os seguintes vetores e matrizes:

- ALU(NN) – vetor de elementos reais de dimensão NN. Neste v

encontraremos os elementos não nulos da matriz A, sendo que estes se

ordenados pelas linhas em que se encontram, ou seja, primeiro se

armazenados os elementos da primeira linha, em seguida serão armazena

os elementos da segunda linha e assim por diante. Os elementos não n

da matriz A serão armazenados nas primeiras NZ posições;

(3.3)

r a

de

nar

ção

etor

rão

rão

dos

ulos

16

- CNLU(NN1) – vetor de elementos inteiros de dimensão NN1, onde será

armazenado o número das colunas dos elementos do vetor ALU na mesma

posição em que estes se encontram, ou seja, se um elemento aij A∈ é

armazenado na posição K de ALU (ALU(K) = ), onde NZK ≤≤1 , então o

número da coluna deste elemento será armazenado na posição K do vetor

CNLU (CNLU(K

ija

) = j).

- RNLU(NN) – vetor de elementos inteiros de dimensão NN, onde serão

armazenados os números das linhas dos elementos não nulos da matriz A

ordenados por coluna, ou seja, primeiro serão armazenados os números das

linhas dos elementos não nulos da primeira coluna, em seguida serão

armazenados os números das linhas dos elementos não nulos da segunda

coluna, e assim por diante.

- HA(NHA,11) – matriz de elementos inteiros de NHA linhas e 11 colunas, onde

serão armazenadas informações adicionais para execução da EG. As três

primeiras colunas da matriz HA contêm informações sobre os vetores ALU e

CNLU, sendo que a primeira coluna informa a posição no vetor ALU onde

está armazenado o primeiro elemento não nulo da linha, ou seja, HA(i,1)

contém a posição no vetor ALU do primeiro elemento não nulo da linha i. A

terceira coluna informa a posição no vetor ALU onde está armazenado o

último elemento não nulo da linha, ou seja, HA(i,3) contém a posição no vetor

ALU do último elemento não nulo da linha i. A segunda coluna informa a

posição do elemento que será comparado e calculado durante o estágio s da

EG. Esta coluna inicia com a posição do primeiro elemento não nulo da linha

e ao final do estágio esta coluna deverá mostrar as linhas da matriz A que

ainda serão utilizadas na EG (“parte ativa das linhas” da matriz A). As três

colunas seguintes da matriz HA contêm informações sobre o vetor RNLU. A

quarta coluna informa a posição no vetor RNLU onde está armazenado o

número da linha do primeiro elemento não nulo da coluna em questão, ou

seja, HA(i,4) contém a posição no vetor RNLU onde está armazenado o

número da linha do primeiro elemento não nulo da coluna i. A sexta coluna

informa a posição no vetor RNLU onde está armazenado o número da linha

do último elemento não nulo da coluna em questão, ou seja, HA(i,6) contém a

17

≥ e

posição no vetor RNLU onde está armazenado o número da linha do último

elemento não nulo da coluna i. A quinta coluna informa a posição do

elemento que será comparado e calculado durante o estágio s da EG. Esta

coluna inicia com a posição do número da linha do primeiro elemento não

nulo da coluna e ao final do estágio esta coluna deverá mostrar as colunas da

matriz A que ainda serão utilizadas na EG (“parte ativa das colunas” da matriz

A). As demais colunas da matriz HA contêm outras informações para facilitar

a execução da EG.

Os parâmetros NN, NN1, NHA são tais que , N1 NNHA ≥ ,

onde NZ é o número de elementos não nulos da matriz A e N=n é a ordem da matriz

A. Normalmente, os parâmetros NN e NN1 são maiores do que NZ, reservando

espaços livres para o armazenamento de elementos nulos que, durante o cálculo, se

tornaram não nulos (preenchimentos).

NZNN ≥ NZN

O modelo de armazenamento dinâmico, descrito anteriormente, consiste em

dois grupos de vetores. No primeiro grupo de vetores os elementos da matriz A,

juntamente com os seus números de colunas, são ordenados pelas linhas nos

vetores ALU e CNLU, sendo que a informação do primeiro e do último elemento de

cada linha é armazenada nas três primeiras colunas da matriz HA. Os vetores ALU

e CNLU, juntamente com as três primeiras colunas de HA, são conhecidos como

“Lista Ordenada por Linhas” ou “Estrutura Orientada por Linha”. No segundo grupo

de vetores, os números das linhas dos elementos da matriz A são ordenados pelas

colunas no vetor RNLU, a informação do primeiro e do último elemento de cada

coluna é armazenada nas três próximas colunas da matriz HA. O vetor RNLU,

juntamente com as quarta, quinta e sexta colunas de HA, é conhecidos como “Lista

Ordenada por Colunas” ou “Estrutura Orientada por Coluna”

Para exemplificar, considere a matriz (3.2) e os vetores AORIG, RNORIG e

CNORIG da Tabela (3.3). A estrutura dinâmica correspondente seria a seguinte:

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ALU 6.0 3.0 9.0 2.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 CNLU 1 4 5 1 2 2 3 5 3 4 4 5
(3.4)

18

Nº LINHA Linha 1 Linha 2 Linha 3 Linha 4 Linha 5 Espaço Livre

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15RNLU 1 2 2 3 3 4 1 4 5 1 3 5 Nº COLUNA

Coluna 1

Coluna 2

Coluna 3

Coluna 4 Coluna 5 Espaço Livre

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6

1 1 1 3 1 1 2 2 4 4 5 3 3 4 3 6 6 8 5 5 6 4 9 9 10 7 7 9 5 11 11 12 10 10 12 Informações sobre as

posições iniciais e finais dos vetores ALU e CNLU

Informações sobre as posições iniciais e finais dos

vetores RNLU

(3.6)

(3.5)

19

3.3 – Armazenamento dos preenchimentos

Conforme pode ser observado na seção anterior, o modelo de

armazenamento dinâmico é muito mais complexo do que o modelo de

armazenamento estático.

A principal razão para utilizar o modelo dinâmico é a necessidade de

armazenar os preenchimentos que irão surgir durante o processo de Eliminação

Gaussiana ou outras operações de uma forma conveniente. O armazenamento de

tais preenchimentos seria impossível se o modelo estático fosse utilizado. A seguir

será explicado como é feito o armazenamento destes preenchimentos utilizando um

modelo dinâmico de armazenamento.

Seja )s(ij um novo preenchimento criado na linha i e coluna j no estágio s de

uma Eliminação Gaussiana(EG). A EG foi utilizada como exemplo, mas a mesma

idéia pode ser aplicada para outras operações algébricas bastando que algumas

modificações sejam feitas. O processo de armazenamento deste preenchimento é

composto dos seguintes passos:

a

1. Fazer uma cópia dos elementos da linha i no espaço livre do vetor

ALU, depois do último elemento armazenado;

2. Fazer uma cópia dos elementos correspondentes aos números das

colunas dos elementos da linha i no espaço livre do vetor CNLU,

depois do último elemento armazenado;

3. Atualizar o conteúdo das três primeiras colunas da linha i da matriz HA

(HA(i,1), HA(i,2) e HA(i,3)).

4. Armazenar o novo elemento no final da cópia da linha i no vetor ALU e

armazenar o número da coluna deste elemento na mesma posição no

vetor CNLU.

5. A inclusão deste novo elemento no final da linha i irá provocar

modificação do elemento HA(i,3), sendo necessário atualizar esta

matriz.

20

6. As posições ocupadas, antes das operações acima, pelos elementos

da linha i e pelos números de suas colunas são liberadas. Uma

posição liberada é indicada colocando zero no vetor CNLU.

Para exemplificar o processo descrito anteriormente, observe, passo a passo,

as operações no estágio 1 da Eliminação Gaussiana da matriz (3.2). Neste estágio

o elemento será eliminado e serão criados dois preenchimentos ,nas colunas 4 e

5 da linha 2, conforme pode ser observado a seguir.

21a

⎢⎢⎢⎢

⎣

−−=

0.2.2

0.300.30.100.3100.10

(3.7)

que estava armazenado na posição 3 da lista ordenada

nhas c ento gerado na coluna 4 da linha 2 pode ser

do çã

⎥⎥

⎢⎢

0.9000000.100

⎥⎥⎥⎥

⎦

⎤⎡ 0.90.3006.0

A

Como o elemento 21a

por li foi eliminado, o preen him

armazena nesta posi o.

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ALU 6.0 3.0 9.0 -1.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 CNLU 1 4 5 4 2 2 3 5 3 4 4 5 Nº LIN

Livre HA Linha 1 Linha 2 Linha 3 Linha 4 Linha 5 Espaço

Para o armazenamento do preenchimento criado na coluna 5 da linha 2 ser

preciso a realização de alguns passos:

1º passo: Criação de uma cópia da linha i no espaço livre dos vetores ALU e CNLU

depois do último elemento armazenado;

(3.8)

á

,

21

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ALU 6.0 3.0 9.0 -1.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 -1.0 1.0 CNLU 1 4 5 4 2 2 3 5 3 4 4 5 4 2 Nº LINHA Linha 1 Linha 2 Linha 3 Linha 4 Linha 5 Cópia da

Linha 2 Livre

2º passo: Atualizar matriz HA;

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU

3º passo: Armazenar o preenchimento e o número de sua coluna nos vetores ALU

CNLU;

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ALU 6.0 3.0 9.0 -1.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 -1.0 1.0 -3CNLU 1 4 5 4 2 2 3 5 3 4 4 5 4 2 5Nº LINHA Linha 1 Linha 2 Linha 3 Linha 4 Linha 5 Linha 2

4º passo: Atualizar o elemento HA(2,3);

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU
(3.10)
e

.0
(3.12)
(3.9)

(3.11)

22

5º passo: Liberar os espaços ocupados pelos antigos elementos nos vetores ALU e

CNLU;

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ALU 6.0 3.0 9.0 -1.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 -1.0 1.0 -3.0CNLU 1 4 5 0 0 2 3 5 3 4 4 5 4 2 5 Nº LINHA Linha 1 Espaço

Livre Linha 3 Linha 4 Linha 5 Linha 2

O modelo de armazenamento é inicialmente compacto e ordenado. Contudo,

a estrutura, geralmente, não permanece compacta após o início da EG. O que se

mantém ainda compacta é a estrutura dentro de cada linha, ou seja, não existem

posições vagas entre dois elementos de uma mesma linha nos vetores ALU e CNLU.

Podemos observar que os elementos das posições 4 e 5 , que antes das

operações da EG no estágio 1 eram ocupadas por elementos da linha 2, estão livres

(o número dos elementos do vetor CNLU nestas posições é igual a zero). O fato de

haver posições vagas entres as linhas depois do começo da EG indica que, antes de

se fazer uma cópia da linha i no final da estrutura, pode ser vantajoso verificar se

existe posição vaga antes do primeiro (ou depois do último) elemento da linha i.

Nestes casos o preenchimento é armazenado em uma destas posições vagas, a

matriz HA é atualizada de forma conveniente.

O número de cópias de linhas é normalmente reduzido quando se explora

posições livres antes do primeiro ou depois do último elemento das linhas como

descrito anteriormente. Contudo, muitas cópias são realizadas, sendo que a

capacidade dos vetores ALU e CNLU (NN e NN1) pode ser excedida. Se isto

acontecer, então é necessário compactar a estrutura destes dois vetores executando

um procedimento chamado Coleta de Lixo (CL), que será descrito na seção

seguinte. Devemos enfatizar que, o fato de explorar posições livres antes do

primeiro e depois do último elemento da linha, irá reduzir, além do número de cópias

das linhas, o número de procedimentos CL necessário para a EG. Este segundo

efeito é freqüentemente mais importante e significativo do que a redução do número

de cópias das linhas.

(3.13)

23

Um procedimento similar ao aplicado na lista ordenada por linhas (ALU, CNLU

e as três primeiras colunas de HA) pode ser aplicado na lista ordenada por colunas

(RNLU e quarta, quinta e sexta colunas de HA) para acrescentar um preenchimento

na estrutura, conforme pode ser descrito nos seguintes passos:

1. Fazer uma cópia dos elementos dos números das linhas dos

elementos da coluna i no espaço livre do vetor RNLU, depois do

último elemento armazenado;

2. Atualizar o conteúdo da quarta, quinta e sexta colunas da linha i da

matriz HA (HA(i,4), HA(i,5) e HA(i,6)).

3. Armazenar o novo elemento no final da cópia feita no vetor RNLU.

4. A inclusão deste novo elemento, no final da linha i, irá provocar

modificação do elemento HA(i,6), sendo necessário atualizar esta

matriz.

5. Liberar as posições ocupadas, antes das operações acima, pelos

números das linhas no vetor RNLU (uma posição liberada é

indicada colocando zero no vetor RNLU).

Considerando ainda o estágio 1 da Eliminação Gaussiana da matriz (3.2),

onde será criado um preenchimento no elemento a , podem-se observar, passo a

passo, as alterações que o procedimento anterior irá provocar na lista ordenada por

colunas.

24

1º passo: Criação de uma cópia dos números das linhas dos elementos da coluna 4

do vetor RNLU, depois do último elemento armazenado;

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15RNLU 1 0 2 3 3 4 1 4 5 1 3 5 1 4 5 Nº COLUNA

Coluna 1

livre Coluna 2 Coluna 3 Coluna 4 Coluna 5 Cópia da Coluna 4

Neste ponto pode-se observar que não existem espaços livres no final d

estrutura para o armazenamento do número da coluna do preenchimento que ser

(3.14)

a

á

24

criado na segunda coluna, apesar deste espaço existir no meio da estrutura. Será

necessário compactar a estrutura para o armazenamento do preenchimento criado.

2º passo: Compactar a estrutura usando Coleta de Lixo;

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 RNLU 1 2 3 3 4 1 4 5 1 3 5 1 4 5 0 Nº COLUNA

Coluna 1

Coluna 2 Coluna 3 Coluna 4 Coluna 5 Cópia da Coluna 4

livre

3º passo: Armazenar o preenchimento no final do vetor RNLU;


Coluna 1

Coluna 2 Coluna 3 Coluna 4 Coluna 5 Cópia da Coluna 4

livre

4º passo: Atualizar o elemento HA(4,6);

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU

5º passo: Liberar os espaços ocupados pelos antigos elementos da coluna 4

vetor RNLU;

(3.15)

(3.17)

no

(3.16)

25


Coluna 1

Coluna 2 Coluna 3 Espaço Livre Coluna 5 Cópia da Coluna 4

livre

Observando a criação do preenchimento no elemento , pode-se observar

que a lista ordenada por colunas e a matriz HA ficará da seguinte forma:

25a

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16RNLU 1 2 2 3 3 4 0 0 2 1 3 5 1 4 5 2 Nº COLUNA Coluna 1 Coluna 2 Coluna 3 Espaço

Livre Coluna 5 Coluna 4

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU

Conforme pôde ser observado na lista ordenada por linha, a lista ordenada

por colunas também é compacta no início da EG, porém, geralmente, esta estrutura

não permanece compacta após o início dos cálculos, ou seja, apesar de não

existirem posições vagas entre os elementos de uma mesma coluna, podem existir

posições vagas entre os elementos de duas colunas distintas.

Como na lista ordenada por linhas, o número de cópias dos elementos de

uma coluna para o final da lista pode ser reduzido, consideravelmente, quando as

posições vazias no início e no fim de cada coluna são aproveitadas para a inclusão

de um novo preenchimento. Contudo, muitas cópias podem ser ainda necessárias,

o que pode exceder a capacidade do vetor RNLU. Se isto acontecer, então é

necessário compactar novamente a estrutura, eliminando os espaços vagos entre as

(3.

(3.18)

(3.19)

20)

26

colunas (procedimento de Coleta de Lixo). Deve ser enfatizando que o

aproveitamento de posições vazias no início e no fim de cada coluna pode não só

reduzir o número de cópias das colunas, mas também o número de vezes em que o

procedimento de Coleta de Lixo será executado.

Deve se ainda observar que os elementos pivôs )s(ssa serão armazenados em

um vetor de números reais PIVOT de tamanho igual ou superior a N. As posições

ocupadas pelo elemento pivô e por seus números de linha e coluna nos vetores

ALU, RNLU e CNLU, respectivamente, serão liberados no início do estágio s da EG

e poderão ser usados para armazenar preenchimentos.

)s(ssa

3.4 – Procedimento de Coleta de Lixo (“Garbage Collection”)

s ordenadas é conhecido como Coleta de

Lixo (CL) ou “Garbage Collection”.

bilitando que novas cópias sejam feitas

no final deste vetor.

ordenada por linhas (vetores ALU e CNLU). Este processo será executado em dois

Quando um preenchimento )sa é criado durante os cálculos da EG é

necessário que partes dos vetores ALU e CNLU sejam copiados para o final destes

vetores. Porém, se muitas cópias forem feitas pode não haver espaços suficientes

para outras cópias. Por outro lado, podem existir espaços livres entre elementos de

diferentes linhas, isto porque depois dos elementos serem copiados para o final dos

vetores, os espaços ocupados por estes serão liberados. Nestes casos, é

necessária a compressão (compactação) da lista ordenada por linha, ou seja,

eliminar espaços vagos no meio destas estruturas, criando, assim, espaços no final

das listas e possibilitando que novas cópias necessárias sejam feitas. Este processo

de compactação dos elementos das lista

(ij

Uma situação similar ocorre na lista ordenada por colunas. Quando um

preenchimento é criado, partes do vetor RNLU serão copiadas para o final deste.

Quando faltar espaço no final deste vetor, será necessário executar um processo de

CL para compactar esta lista ordenada, possi

Para ilustrar o processo, considere que uma CL será feita em uma lista

27

passos. No primeiro passo serão levantadas algumas informações para o segundo

passo. O segundo passo será a compressão efetiva da estrutura em questão.

Durante o primeiro passo, as posições dos primeiros elementos não nulos de

cada linha são localizados no vetor ALU e marcados da seguinte forma: HA(i,1) =

CNLU(HA(i,1)) e CNLU(HA(i,1)) = -i para i = 1, 2, ... , N. O primeiro passo da CL na

lista ordenada por linhas pode ser executado com complexidade de ordem N (O(N)),

onde O(N) significa que o número de operações é definido por um polinômio onde a

maior potência deste polinômio é N.

No Exemplo (3.13), suponhamos que seja necessário fazer uma CL. Abaixo

podemos observar os vetores ALU e CNLU e a matriz HA antes e depois de ser

executado o primeiro passo da CL.

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ALU 6.0 3.0 2.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 0 1.0 -1.0 CNLU 1 4 0 0 2 3 5 3 4 4 5 1 2 4 Nº LINHA Linha 1 Espaço

Livre Linha 3 Linha 4 Linha 5 Linha 2 Espaço

Livre

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU Estrutura antes do primeiro passo da CL
(3.19)

28

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ALU 6.0 3.0 2.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 0 1.0 -1.0

CNLU 1 4 0 0 2 3 5 3 4 4 5 1 2 4 Nº LINHA Linha 1 Espaço

Livre Linha 3 Linha 4 Linha 5 Linha 2 Espaç

o Livre

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU Estrutura depois de fazer HA(i,1) = CNLU(HA(i,1))

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ALU 6.0 3.0 2.0 1.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 0 1.0 -1.0 CNLU -1 4 0 0 -3 3 5 -4 4 -5 5 -2 2 4 Nº LINHA Linha 1 Espaço

Livre Linha 3 Linha 4 Linha 5 Linha 2 Espaço

Livre

(3.20)

(3.21)

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU Estrutura depois de fazer CNLU(HA(i,1)) = -i

29

Considere, agora, o segundo passo da CL. Seja NCNLU a última posição

ocupada nos vetores ALU e CNLU (NCNLU ≤ NN, onde NN é o comprimento destes

dois vetores). Considere a variável NEWPOS e assuma que NEWPOS = 1 no início

do processo. Verifique os componentes CNLU(K) para K = 1, 2, ..., NCNLU. Se

CNLU(K) = 0, então a localização K está livre e nada é feito. Se CNLU(K) < 0, então

uma nova linha começa na posição K do vetor ALU. Neste caso, os elementos

armazenados na posição K dos vetores ALU e CNLU devem ser movidos para

posição NEWPOS dos respectivos vetores. A matriz HA deve ser atualizada e a

variável NEWPOS deve avançar para próxima posição. As mudanças necessárias

estão descritas abaixo:

ALU(NEWPOS) = ALU(K)

CNLU(NEWPOS) = HA(-CNLU(K),1)

HA(-CNLU(K),1) = NEWPOS

HA(-CNLU(K),2) = NEWPOS + HA(-CNLU(K),2) – K + 1

HA(-CNLU(K),3) = NEWPOS + HA(-CNLU(K),3) – K + 1

NEWPOS = NEWPOS+1

Se CNLU(K) > 0 então, os elementos armazenados na posição K dos v

ALU e CNLU devem ser movidos para posição NEWPOS dos respectivos ve

a variável NEWPOS deve avançar para próxima posição. Neste caso

necessário atualizar a matriz HA. Tais mudanças podem ser observadas a seg

ALU(NEWPOS) = ALU (K)

CNLU(NEWPOS) = CNLU (K)

NEWPOS = NEWPOS +1

A seguir podemos observar os vetores ALU e CNLU e a matriz

Exemplo (3.13) depois de ser executado o segundo passo da CL.

(3.22)

etores

tores e

não é

uir:
(3.23)
HA do

30

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ALU 6.0 3.0 1.0 3.0 3.0 1.0 2.0 2.0 9.0 0 1.0 -1.0 CNLU 1 4 2 3 5 3 4 4 5 1 2 4 0 0 0 Nº LINHA Linha 1 Linha 3 Linha 4 Linha 5 Linha 2 Espaço

Livre

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6



Informações sobre as posições iniciais e finais do

vetores RNLU Estrutura depois de executar o 2º passo da CL

No final deste processo, a estrutura estará totalmente comprimida e a ú

posição ocupada será NEWPOS –1. Neste caso, é esperado que tenh

espaços livres suficientes no final da lista ordenada por linhas para se fazer a

da linha necessária, a qual não foi possível ser feita antes do início da C

verdade este foi o motivo de se realizar este processo de compactação).

mesmo depois do processo, não houver espaços livres suficientes no final da

para a cópia de uma determinada linha, então, o programa deverá mandar

mensagem de erro informando que o comprimento destes vetores é muito pequ

A complexidade do segundo passo é de ordem NN (O(NN)), onde NN

comprimento dos vetores ALU e CNLU.

O processo de CL na lista ordenada por coluna é executado de

semelhante. A única diferença significativa é que, durante o primeiro pass

posições dos primeiros elementos contendo os números das linhas dos elem

não nulos de cada coluna são localizadas no vetor RNLU e marcadas da seg

forma: RNLU(HA(j,4)) = -j e HA(j,4) = RNLU(HA(j,4)) para j = s, s+1, ... , N (sup

que a CL deverá ser executada no estágio s).

(3.24)

s

ltima

amos

cópia

L (na

Se,

lista

uma

eno.

é o

forma

o, as

entos

uinte

ondo

31

No Exemplo (3.18) suponhamos que seja necessário fazer uma CL. Abaixo

podemos observar os vetores ALU e CNLU e a matriz HA antes e depois de ser

executado o primeiro passo da CL.

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 RNLU 1 2 2 3 3 4 0 0 0 3 5 1 4 5 2 Nº COLUNA Coluna 1 Coluna 2 Coluna 3 Espaço Livre Coluna

5 Coluna 4

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6





POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 RNLU 1 2 2 3 3 4 0 0 0 3 5 1 4 5 2 Nº COLUNA Coluna 1 Coluna 2 Coluna 3 Espaço Livre Coluna

5 Coluna 4

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU Estrutura depois de fazer HA(j,4) = RNLU(HA(j,1))

(3.25)

(3.26)

32

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 RNLU -1 2 -2 3 -3 4 0 0 0 -5 5 -4 4 5 2 Nº COLUNA Coluna 1 Coluna 2 Coluna 3 Espaço Livre Coluna

5 Coluna 4

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6




vetores RNLU Estrutura depois de fazer RNLU(j) = -j

A seguir podemos observar o vetor RNLU e a matriz HA do Exemplo (3

depois de ser executado o segundo passo da CL.

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15RNLU 1 2 2 3 3 4 3 5 1 4 5 2 0 0 0Nº COLUNA Coluna 1 Coluna 2 Coluna 3 Coluna

5 Coluna 4 Espaço Livr

MATRIZ HA COLUNA

LINHA 1 2 3 4 5 6





(3.27)

.18)

e
(3.28)

33

No final deste processo a estrutura estará totalmente comprimida e a última

posição ocupada será NEWPOS –1. Neste caso, é esperado que tenhamos

espaços livres suficientes no final da lista ordenada por colunas para se fazer a

cópia da coluna necessária, a qual não foi possível ser feita antes do início da CL

(na verdade este foi o motivo de se realizar este processo de compactação). Se,

mesmo depois do processo, não houver espaços livres suficientes no final da lista

para a cópia de uma determinada coluna, então, o programa deverá mandar uma

mensagem de erro informando que o comprimento destes vetores é muito pequeno.

A complexidade dos dois passos da CL na lista ordenada por colunas é de

ordem N-s+1 (O(N-s+1)) para o primeiro passo e de ordem NN1 (O(NN1)) para o

segundo passo, onde NN1 é o comprimento do vetor RNLU .

3.5 – Espaços Livres

Considere os vetores ALU, RNLU e CNLU, usados no processo de

armazenamento dinâmico descrito anteriormente, de tamanhos NN, NN1 e NN,

respectivamente. Uma vez que preenchimentos serão criados durante o processo

de EG (ou qualquer outra operação algébrica) então serão necessários espaços

adicionais vazios neste vetores para o armazenamento destes, ou seja, os

comprimentos destes vetores deverão ser maiores do que o número de elementos

não nulos do início do processo de armazenamento dinâmico, isto é, NN ≥ NZ e

NN1≥ NZ. Estas posições vazias extras são chamadas de Espaços Livres.

É muito importante determinar quantas posições extras serão necessárias.

Infelizmente, este número depende do número de preenchimentos criados durante

as operações algébricas e, mais ainda, este número não é conhecido no início dos

cálculos computacionais. Segundo Zlatev (1991), experimentos com milhares de

matrizes indicaram que, em geral, uma escolha de NN ∈ [5*NZ, 10*NZ] e NN1 =

0,6*NN, quando a forma clássica de explorar a esparcidade é utilizada, e NN ∈

[2*NZ, 3*NZ] e NN1 = 0,6*NN, quando a forma orientada a computador é utilizada,

são boas escolhas. Contudo, algumas matrizes podem ainda produzir um número

34

superior de preenchimentos. Neste caso, é necessário escolher valores superiores

aos mencionados anteriormente para os parâmetros NN e NN1.

As observações feitas anteriormente são baseadas em resultados numéricos

obtidos de extensivos experimentos computacionais com matrizes esparsas. Alguns

destes experimentos podem ser observados em Zlatev (1991).

3.6 – O uso de Lista Encadeada no modelo de armazenamento dinâmico

O modelo de armazenamento dinâmico discutido na Seção 3.2 utiliza duas

listas ordenadas (a primeira ordenada por linhas e a segunda ordenada por colunas).

Isto não significa que este é o único modelo de armazenamento dinâmico e,

provavelmente, não é o melhor modelo para todas as situações. Um outro modelo é

baseado em listas conhecidas como Listas Encadeadas (”linked lists”).

A idéia básica do modelo utilizando Listas Encadeadas pode ser observada

em Zlatev (1991), sendo descrita a seguir.

meça a coluna j.

Se um elemento não nulo ija é armazenado na posição K (1 < K < NZ) do

vetor ALU então, a posição onde o próximo elemento não nulo da linha i é

armazenado no vetor ALU pode ser encontrado em RNLU(K), enquanto a posição

onde o próximo elemento não nulo da coluna j é armazenado no vetor ALU pode ser

encontrado em CNLU(K). Valores negativos nos vetores RNLU e CNLU indicam o

final de uma linha e de uma coluna, respectivamente. Além dos vetores ALU, RNLU

e CNLU são necessários dois vetores inteiros de comprimento N (HA(*,1) e HA(*,4)).

O elemento HA(i,1) indica a posição no vetor ALU onde começa a linha i. O

elemento HA(j,4) indica a posição no vetor ALU onde co

Para exemplificar o modelo dinâmico descrito anteriormente, consideremos

novamente a matriz (3.2).

35

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

=

0902000002010003003010

000010200300

....

.....

.6.0

A (3.2)

O modelo de armazenamento dinâmico utilizando o conceito de lista

encadeada, descrito no parágrafo anterior, pode ser observado abaixo:

POSIÇÃO 1 2 3

4 5 6 7 8 9 10 11 12 13 14 15 ALU 9.0 2.0 2.0 1.0 3.0 3.0 1.0 1.0 2.0 3.0 6.0 RNLU -5 1 -2 3 -3 5 6 -2 8 -1 10 CNLU -5 -4 2 -3 1 4 -2 7 -1 3 9

MATRIZ HA COLUNA

LINHA 1 4

1 11 11 2 9 8 3 7 6 4 4 10 5 2 5

Vejamos agora como são feitas a inserção de um preenchimen

dos elementos nulos, quando utilizamos a estrutura anterior. Consid

estágio da EG da matriz (3.2). Neste estágio o elemento a

preenchimento = -1 é criado, conforme pode ser observado abaixo

121

124a

⎥⎥⎦⎢

⎢⎣ 0.90.2000

00.20.100

⎥⎥⎥⎥⎤⎡ 00.3006.0

⎢⎢⎢⎢ −

= 0.300.30.100100.10

A

(3.30)

to e a remoçã

ere o primei

é zerado e

.

(3.31)

(3.29)

o

ro

o

36

,1) = 9. O próximo elemento desta linha está armazenado na

posição 8, isto porque RNLU(9) = 8. A segunda linha terminava neste elemento

-2 C a inserção do elemento

U(8)= n n q a term na gora

leme .

O preenchimento será armazenado na posição 12 do vetor ALU. O primeiro

elemento da linha 2, que será zerado, está armazenado na posição 9 do vetor ALU,

isto porque HA(2

(RNLU(8)= ). om 124 no final da linha devemos atualizar a

o RNL 12 e f eaz r N R L (1U 2) = -2 i, d aic do u e segu and l ainh i a

neste e nto

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ALU 9.0 2.0 2.0 1.0 3.0 3.0 1.0 1.0 2.0 3.0 6.0 -1.0 RNLU -5 1 -2 3 6 -3 5 12 8 -1 10 -2 CNLU -5 -4 1 4 -2 -1 9 2 -3 7 3

MATRIZ HA COLUNA

LINHA 1 4

1 11 11 2 9 8 3 7 6 4 4 10 5 2 5

O primeiro elemento da coluna 4 é armazenado na posição 10

isto porque HA(4,4) = 10. O próximo elemento desta coluna será o

. Desta forma devemos fazer CNLU(12) = CNLU(10) e CNLU(10)

124a

(3.33)

do vetor AL

preenchimen

= 12.

(3.32)

U,

to

37

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ALU 9.0 2.0 2.0 1.0 3.0 3.0 1.0 1.0 2.0 3.0 6.0 -1.0 RNLU -5 1 -2 3 -3 5 6 12 8 -1 10 -2 CNLU -5 -4 2 -3 1 4 -2 7 -1 12 9 3

MATRIZ HA COLUNA

LINHA 1 4

1 11 11 2 9 8 3 7 6 4 4 10 5 2 5

Uma vez inserido o preenchimento, podemos zerar e remover o elemento

Isto é feito zerando o valor da posição 9 dos vetores ALU, RNLU e C

atualizando o elemento HA(2,1)=8, indicando que o primeiro elemento não nu

segunda linha, que se encontrava na nona posição dos vetores ALU e RNLU

encontra agora oitava posição, e alterando o elemento CNLU(11)=-1, indicando

o último elemento não nulo da primeira coluna se encontra na décima prim

posição do vetor CNLU.

POSIÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1ALU 9.0 2.0 2.0 1.0 3.0 3.0 1.0 1.0 0 3.0 6.0 -1.0 RNLU -5 1 -2 3 -3 5 6 12 0 -1 10 -2 CNLU -5 -4 2 -3 1 4 -2 7 0 12 -1 3

MATRIZ HA COLUNA

LINHA 1

4 1 11 11 2 8 8 3 7 6 4 4 10 5 2 5

(3.34)

.

NLU,

lo da

, se

que

eira

121a

5
(3.35)

38

O modelo baseado em listas encadeadas tem pelo menos três vantagens,

comparado ao modelo de armazenamento baseado em listas ordenadas, discutido

anteriormente:

• Não é preciso fazer cópias das linhas ou colunas para o final da

estrutura, quando acrescentamos um preenchimento;

• Não é preciso fazer Coleta de Lixo;

• A inserção de um preenchimento é um processo simples.

É claro que o número da linha e da coluna de um elemento implicará o

acréscimo de dois vetores de tamanho NN. Ou seja, se um elemento a é

armazenado na posição K do vetor ALU, os números da linha i e da coluna j serão

armazenados na mesma posição K dos dois novos vetores.

ij

Existem várias desvantagens nos códigos computacionais baseados em listas

encadeadas (ver Duff – 1985 e Osterby et al – 1983). A principal desvantagem da

estrutura baseada em listas encadeadas é que se for preciso o número da linha (ou

da coluna) de um elemento não nulo, então é preciso procurar pela lista das linhas

(ou das colunas) até que o número da linha (ou coluna) desejado seja encontrado.

3.7 – Outros Modelos de Armazenamento

Outros modelos de armazenamento podem ser encontrados na literatura.

Vale ressaltar que muitos destes modelos são elaborados para problemas especiais.

Dentre os modelos podemos citar os seguintes:

• Gilbert-Peierls, ver Zlatev (1991);

• Bit-maps, ver Duff (1985);

• Hash coding, ver Duff (1985);

• Modelo de armazenamento para matrizes banda, ver Dongarra et al

(1979), Jennings (1977) e Rice et al (1985);

• Técnicas Frontais e Multifrontais, ver Duff et al (1983) e Reid (1984);

39

• Técnicas “Multigrid”, ver Wesseling (1982).

3.8 – Conceitos Preliminares

Para apresentarmos o modelo desenvolvido neste trabalho, iremos lembrar

alguns conceitos básicos de programação de computadores. Tais conceitos serão

discutidos a seguir:

3.8.1 – Variáveis

Uma variável é um espaço alocado na memória para o armazenamento de

um tipo de dado específico. Quando utilizamos uma variável, fornecemos a esta um

identificador (nome) para este espaço e toda vez que nos referenciamos a este

identificador estaremos referenciando ao dado armazenado.

Quando declaramos uma estrutura de dados, utilizando variáveis, devemos

dimensionar, direta ou indiretamente, o tamanho desta estrutura, ou seja, estaremos

dimensionando a quantidade de memória necessária para o armazenamento dos

dados. Neste sentido, podemos classificar a estrutura de dados como estática, uma

vez o tamanho desta estrutura não será alterado durante a execução do programa.

Esta característica pode dificultar ou até mesmo inviabilizar a codificação de certas

rotinas de cálculos descritas anteriormente.

Como se pode observar nos modelos de armazenamentos descritos nas

Seções 3.2 e 3.6, as estruturas de dados apresentadas nestas seções utilizam

vetores de tamanhos fixos NN e NN1, onde NN≥ NZ e NN1 NZ. Nestes casos, as

estruturas são dimensionadas com uma folga, onde o excesso de posições é

reservado para o armazenamento dos preenchimentos que irão surgir durante os

cálculos computacionais. Se o espaço reservado para a quantidade de

preenchimentos que irão ser criados não for suficiente, então, o programa deverá

interromper a sua execução e emitir uma mensagem de erro.

≥

40

Além deste problema, o Modelo descrito na Seção 3.2 terá uma estrutura não

totalmente ordenada, pois algumas linhas serão movidas para o final dos vetores,

sendo necessária, em alguns momentos, a compactação da estrutura pelo

procedimento de Coleta de Lixo. Neste caso, seria necessária uma estrutura de

dados que fosse realmente dinâmica, ou seja, uma estrutura que altere o seu

tamanho de acordo com a quantidade de dados armazenados e não uma estrutura

de tamanho fixo e superdimensionada para existirem posições extras para

armazenar os preenchimentos que serão criados posteriormente. Seria interessante

que tal estrutura se mantivesse ordenada e compactada durante as iterações do

programa, evitando assim a perda de tempo com o processo de CL ou qualquer

outro procedimento de ordenação ou compactação.

Na linguagem de programação Pascal existe um tipo de dado que facilita a

montagem da estrutura mencionada anteriormente e é conhecido como “Pointer”

(Ponteiro) que será discutido na próxima seção.

3.8.2 – O Tipo Ponteiro da Linguagem Pascal

O ponteiro (“Pointer”) é um tipo de dado criado para o gerenciamento de uma

área da memória conhecida como “heap”. Esta área de memória é chamada

também de área de armazenamento dinâmico. Diferente das variáveis dos outros

tipos do Pascal que armazenam os dados, o objetivo das variáveis do tipo “Pointer” é

indicar onde encontrar os dados na área de armazenamento dinâmico. Em outras

palavras, o ponteiro aponta para os dados armazenados na “heap”, ou seja, uma

variável do tipo ponteiro conterá um endereço de memória onde podemos encontrar

um dado armazenado.

Uma outra diferença das variáveis do tipo Ponteiro é que estas são criadas

somente durante a execução do programa principal, enquanto as variáveis dos

outros tipos são declaradas e criadas antes da execução do programa. Além disto,

as variáveis do tipo ponteiro podem também ser destruídas em tempo de execução,

liberando espaço na memória do computador para o armazenamento de outros

dados.

41

Maiores informações sobre ponteiro podem ser encontradas em Wood (1987).

Geralmente, os ponteiros são utilizados para montar estruturas de dados que

aproveitem a sua característica dinâmica de poder ser criado ou destruído enquanto

o programa está sendo executado. A seguir, iremos apresentar algumas destas

estruturas.

3.8.3 – Listas Lineares

Segundo Veloso et al (1984), a lista linear é uma estrutura que permite

representar um conjunto de dados de forma a preservar a relação de ordem linear

entre os elementos do conjunto. Os elementos de uma lista linear são chamados de

nós, os quais podem conter, cada um deles, um dado simples ou um dado

composto.

n

n nós

Define-se uma lista linear como sendo o conjunto de )0 nós

n21 n ..., ,n ,n , organizados estruturalmente de forma a refletir as posições relativas dos

mesmos na lista, onde 1n e nn são, respectivamente, o primeiro e o último nó da

ra nk<1 , o nó kn é precedido pelo nó 1−kn e seguido do nó 1+kn . A figura

abaixo representa uma lista linear com

( ≥n

lista. Pa <

1n 2n . . . 1−kn kn 1+kn . . . 1−nn nn

3.8.3.1 – Encadeamento de Listas

As operações de inserção e remoção de nós em uma lista exig

esforço computacional e podem ser um fator determinante do baix

computacional do programa.
(3.36)
em um grande

o desempenho

42

Suponha que a lista (3.36) seja montada em um vetor de dimensão vn. É

necessário fazer uma estimativa a priori do comprimento máximo que a lista pode

tomar para que o vetor que a contiver seja declarado com no mínimo este tamanho

( n≥ ). Caso haja uma tentativa de ultrapassar a estimativa do comprimento do

vetor, o processamento deverá ser interrompido e emitida uma mensagem de erro.

Conforme já mencionado anteriormente, este é um dos maiores problemas de se

utilizar um vetor para representar uma lista, pois o vetor não pode, na maioria das

linguagens de programação, ter o seu tamanho alterado dinamicamente para

permitir a representação de uma lista de comprimento maior do que o inicialmente

previsto.

vn

Uma forma de permitir o crescimento dinâmico do comprimento de uma lista é

representá-la por um encadeamento de nós que indique a ordem de cada nó na lista.

Assim, cada nó deverá conter, além do dado propriamente dito, a indicação do

próximo nó da lista (referência). Uma lista montada pelo encadeamento de nós é

conhecida como Lista Encadeada. A seguir, podemos observar a representação

esquemática de uma lista encadeada.

n4n3 n5n2n1

(3.37)

Como pode ser observada na figura anterior, a ordem dos nós na lista

encadeada é lógica, ou seja, um nó localizado na posição k não é necessariamente

o nó que precede o nó localizado na posição k-1 e nem o nó que antecede o nó

localizado na posição k+1.

Em alguns casos, é necessário, além da informação do próximo nó da lista, a

indicação do nó anterior. Nestes casos a estrutura mais indicada é a lista

duplamente encadeada. Uma lista duplamente encadeada é aquela em que cada nó

43

possui duas referências, onde a primeira é usada para indicar o nó predecessor,

enquanto que a segunda aponta para o nó sucessor. A figura a seguir mostra uma

representação esquemática de uma lista duplamente encadeada.

3.9 – O Modelo de Armazenamento Proposto

O modelo de armazenamento, desenvolvido neste trabalho, é basead

no modelo de armazenamento dinâmico de Zlatev (1991), apre

anteriormente na Seção 3.2, quanto no modelo de listas encadeadas apresen

Seção 3.6.

O modelo irá armazenar os dados na forma de listas encadeadas, ut

ponteiros, onde cada nó da lista irá armazenar um registro contendo, além d

armazenado, informações sobre o seu antecessor e o seu sucessor.

Inicialmente será montado um modelo de armazenamento semelh

modelo estático apresentado na Seção 3.1. A principal diferença do mod

questão é que este irá utilizar uma lista duplamente encadeada de ponteiros

dos vetores AORIG, RNORIG e CNORIG. Esta lista terá NZ nós, onde cada

composto de um pointer do tipo registro chamado de POAORIG. Cada nó

terá as seguintes informações: AORIG, RNORIG, CNORIG, Anterior e Suce

As três primeiras informações (AORIG, RNORIG e CNORIG

respectivamente, o valor de um elemento da matriz A, o número da linha e da

deste elemento. Se um elemento da matriz A é armazenado em

específico, então os campos deste nó terão os seguintes valores:

ija

AORIG = ija

n4n3 n5n2n1

RNORIG = i

CNORIG = j

(3.38)

o tanto

sentado

tado na

ilizando

o dado

ante ao

elo em

no lugar

nó será

da lista

ssor.

) são,

coluna

um nó
(3.39)

44

O campo Anterior terá o endereço do ponteiro anterior ao nó em questão,

enquanto o campo Sucessor terá o endereço do ponteiro seguinte ao nó em

questão. O campo Anterior do primeiro nó terá o valor nulo (“nil”) indicando que na

lista não existe nó anterior a ele. Da mesma forma, o campo Sucessor do último nó

da lista terá o valor nulo (“nil”) indicando que não existe nó após este.

Além destas informações, é necessário indicar em que endereço irá ser

encontrado o primeiro nó da lista (a cabeça da lista). Esta informação será

armazenada em uma variável do tipo Pointer chamada POAORIGINICIAL.

Vamos considerar novamente a matriz (3.2) como exemplo.

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

=

0902000002010003003010

000010200300

....

.....

.6.0

A (3.2)

O primeiro passo do modelo de armazenamento desenvolvido será o

armazenamento dos elementos desta matriz na seguinte lista encadeada.

488F:000C AORIG = 1.0

RNORIG = 3

CNORIG = 2

Anterior = Nil

Sucessor = 488F:0034

488F:0034 AORIG = 3

RNORIG = 3

CNORIG = 5

Anterior = 488F:000C


45

488F:0048 AORIG = 9

RNORIG = 5

CNORIG = 5

Anterior = 488F:0034

Sucessor = 488F:005C

488F:005C AORIG = 3

RNORIG = 1

CNORIG = 4



488F:0070 AORIG = 2.0

RNORIG = 4

CNORIG = 4



488F:0084 AORIG = 2.0

RNORIG = 2

CNORIG = 1



488F:0098 AORIG = 6.0

RNORIG = 1

CNORIG = 1


Sucessor = 488F:00AC

488F:00AC AORIG = 3.0

RNORIG = 3

CNORIG = 3


Sucessor = 488F:00C0

488F:00C0 AORIG = 1.0

RNORIG = 4

CNORIG = 3

46

Anterior = 488F:00AC

Sucessor = 488F:00D4

488F:00D4 AORIG = 1.0

RNORIG = 2

CNORIG = 2

Anterior = 488F:00C0

Sucessor = 488F:00E8

488F:00E8 AORIG = 2.0

RNORIG = 5

CNORIG = 4

Anterior = 488F:00D4

Sucessor = nil

3.40 – Lista Duplamente Encadeada Inicial do Modelo de Armazenamento Proposto

O próximo passo do modelo de armazenamento proposto será a montagem

de duas listas ordenadas, sendo ambas listas duplamente encadeadas, formadas

por ponteiros. Na primeira lista, os elementos serão ordenados pelas linhas, sendo

que a informação do primeiro e do último elemento de cada linha é armazenada nas

duas primeiras colunas da matriz HA.

Cada nó desta lista será composto de um pointer do tipo registro, chamado de

POALUCNLU, contendo as seguintes informações:

• ALU – este campo irá armazenar o valor do elemento da matriz A.

• CNLU – este campo irá armazenar o número da coluna do elemento.

• Anterior – este campo irá armazenar o endereço da memória do elemento

anterior. O valor Nil indica que não existe elemento anterior ao elemento em

questão, ou seja, este elemento é o primeiro da lista.

47

• Sucessor - este campo irá armazenar o endereço da memória do próximo

elemento da lista. O valor Nil indica que não existe elemento seguinte ao

elemento em questão, ou seja, este elemento é o último da lista.

Esta primeira lista é baseada na “Lista Ordenada por Linhas”, descrita no

modelo de armazenamento dinâmico, mostrado na Seção 3.2, e na lista encadeada

descrita na Seção 3.6. As principais diferenças do modelo desenvolvido neste

trabalho para as listas apresentadas nas Seções 3.2 e 3.6 é o fato deste ser

desenvolvido utilizando uma estrutura de armazenamento realmente dinâmica, ou

seja, uma estrutura que será dimensionada para armazenar somente os dados

existentes e não uma estrutura onde será preciso definir, a priori, a máxima

quantidade possível de elementos que serão criados durante os cálculos

computacionais. Uma outra vantagem que poderá ser observada na estrutura

proposta é o fato de que esta permanecerá ordenada e compacta durante todo o

processo de EG, fato este que dispensa o uso de rotinas computacionais de

ordenação ou compactação da estrutura como a Coleta de Lixo, descrita em 3.4.

48

488F:0110 ALU = 6.0

CNLU = 1

Anterior = Nil


488F:0124 ALU = 3.0

CNORIG = 4



488F:0138 ALU = 2.0

CNLU = 1



488F:014C ALU = 1.0

CNLU = 2



488F:0160 ALU = 1.0

CNLU = 2



488F:0174 ALU = 3.0

CNLU = 3



488F:0188 ALU = 3.0

CNLU = 5



488F:019C ALU = 1.0

CNLU = 3


Sucessor = 488F:01B0

49

488F:01B0 ALU = 2.0

CNLU = 4


Sucessor = 488F:01C4

488F:01C4 ALU = 2.0

CNLU = 4

Anterior = 488F:01B0

Sucessor = 488F:01D8

488F:01D8 ALU = 9.0

CNLU = 5

Anterior = 488F:01C4

Sucessor = nil

3.41 – Lista Ordenada por Linhas do Modelo Proposto.

As duas primeiras colunas da matriz HA serão preenchidas com os endereços

dos ponteiros do primeiro e do último elemento de cada linha, como pode ser

observado a seguir:

MATRIZ HA COLUNA

LINHA

1 2 3 4

1 488F:0110 488F:0124 2 488F:0138 488F:014C 3 488F:0160 488F:0188 4 488F:019C 488F:01B0 5 488F:01C4 488F:01D8 Informações sobre as

posições iniciais e finais dos ponteiros da lista ordenada por linhas

3.42 – Duas primeiras colunas da Matriz HA do Modelo Proposto.

Na segunda lista, os elementos serão ordenados pelas colunas, sendo que a

informação do primeiro e do último elemento de cada coluna é armazenada na

50

terceira e quarta coluna da matriz HA. Cada nó desta lista será composto de um

pointer do tipo registro chamado de PORNLU, contendo as seguintes informações:

• RNLU – este campo irá armazenar o número da linha do elemento.

• Anterior – este campo irá armazenar o endereço da memória do elemento

anterior. O valor Nil indica que não existe elemento anterior ao elemento em

questão, ou seja, este elemento é o primeiro da lista.

• Sucessor - este campo irá armazenar o endereço da memória do próximo

elemento da lista. O valor Nil indica que não existe elemento seguinte ao

elemento em questão, ou seja, este elemento é o último da lista.

488F:0200 RNLU = 1

Anterior = Nil


488F:020C RNLU = 2



488F:0218 RNLU = 2



488F:0224 RNLU = 3



488F:0230 RNLU = 3



51

488F:023C RNLU = 4



488F:0248 RNLU = 1



488F:0254 RNLU = 4



488F:0260 RNLU = 5



488F:026C RNLU = 3



488F:0278 RNLU = 5


Sucessor = Nil

3.43 – Lista Ordenada por Colunas do Modelo Proposto.

A terceira e quarta coluna da matriz HA serão preenchidas com os endereços

dos ponteiros do primeiro e do último elemento de cada coluna, como pode ser

observado a seguir:

52

MATRIZ HA COLUNA

LINHA

1 2 3 4

1 488F:0110 488F:0124 488F:0200 488F:020C 2 488F:0138 488F:014C 488F:0218 488F:0224 3 488F:0160 488F:0188 488F:0230 488F:023C 4 488F:019C 488F:01B0 488F:0248 488F:0260 5 488F:01C4 488F:01D8 488F:026C 488F:0278 Informações sobre as


Informações sobre as posições iniciais e finais

dos ponteiros da lista ordenada por colunas

3.44 – Terceira e quarta colunas da matriz HA do Modelo Proposto

3.10 – O cálculo da Eliminação Gaussiana no modelo proposto

Para facilitar o entendimento de como é feita a EG, a inclusão de um

preenchimento e a retirada de um elemento que se tornou nulo durante os cálculos,

vamos considerar a matriz do Exemplo (3.2) com NZ=11 (número de elementos não

nulos).

⎥⎥⎦⎢

⎢⎣ 0902000

0020100..

..

⎥⎥⎥⎥⎤⎡ 00300 .6.0

⎢⎢⎢⎢

= 030030100000102...

..

primeiro passo da decomposição Gaussiana é triangularizar a matriz,

efetua

coluna.

A

As listas iniciais (lista ordenada por linha e lista ordenada por coluna)

referentes a esta matriz estão mostradas em (3.41) e (3.43), sendo que suas

representações podem ser observadas em (3.45a).

O

ndo operações lineares entre suas linhas e colunas. Este processo constitui-

se de zerar os elementos que se encontram abaixo da diagonal principal, coluna a

53

o utilizados dois ponteiros auxiliares IND_LATUAL e IND_LPROX. O

ponteiro IND_LATUAL será posicionado no primeiro elemento não nulo da primeira

linha da lista ordenada por linha eço este que está indicado em

HAPO1(1,1).

Considere a primeira coluna da matriz A , acima. Neste caso, existe um

elemento não nulo na segunda linha que deverá ser zerado. Para executar tais

operações serã

s (3.45b), ender

M RIZ HAPO1 ATCOLUNA

LINHA

1

2

1 488F:0110 488F:0124 2 488F:0138 488F:014C 3 488F:0160 488F:0188 4 48 8F:019C 488F:01B05 48 8 8F:01C4 488F:01D Informações sobre as


Para encontrar a próxima linha com elemento não nulo, será utilizado um

ponteiro auxiliar IND_CATUAL que será inicialmente posicionado no primeiro

elemento da primeira coluna da lista ordenada por colunas (3.45b), endereço este

que está armazenado em HAPO2(1,1).

(3.44a)

54

MATRIZ HAPO2 COLUNA

LINHA

3

4

1 488F:0200 488F:020C2 488F:0218 488F:02243 488F:0230 488F:023C4 488F:0248 488F:02605 488F:026C 488F:0278 Informações sobre as

posições iniciais e finais dos ponteiros da lista ordenada por colunas

(3.44b)

O ponteiro IND_CATUAL irá percorrer os elementos desta coluna até

encontrar um elemento que esteja abaixo da primeira linha (3.45c), ou seja, que

esteja abaixo da diagonal principal, se este existir. Isto é feito verificando se o

campo RNLU do elemento é superior ao valor 1. No exemplo em questão, o valor

encontrado foi 2 (3.45c), indicando que o primeiro elemento não nulo da primeira

coluna está localizado na segunda linha. Sendo assim, o ponteiro IND_LPROX será

posicionado no primeiro elemento não nulo da segunda linha da lista ordenada por

linhas (3.45d).

55

ALU: 6.0CNLU: 1ANTERIOR: NIL

:488F:0124SUCESSOR

488F:0110

ALU: 2.0CNLU: 1ANTERIOR:488F:0124

:488F:014CSUCESSOR

488F:0138


:488F:0160SUCESSOR

488F:014C

ALU: 1.0CNLU: 2ANTERIOR:488F:014C

:488F:0174SUCESSOR

488F:0160


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5

:488F:0174PRÓXIMO:488F:019CSUCESSOR

488F:0188

ALU: 1.0CNLU: 3

:488F:0188PRÓXIMO:488F:01B0SUCESSOR

488F:019C

ALU: 2.0CNLU: 4

:488F:019CPRÓXIMO:488F:01C4SUCESSOR

488F:01B0

ALU: 2.0CNLU: 4

:488F:01B0PRÓXIMO:488F:01D8SUCESSOR

488F:01C4

ALU: 9.0CNLU: 5

:488F:01C4PRÓXIMO: NILSUCESSOR

488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL

RNLU: 1ANTERIOR: NIL

:488F:020CSUCESSOR

488F:0200

RNLU: 2ANTERIOR:488F:020C

:488F:0224SUCESSOR

488F:0218

RNLU: 3ANTERIOR:488F:0218

:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


0248:488F:SUCESSOR

48 23C8F:0


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C

RNLU: 5ANTERIOR:488F:026CSUCESSOR: NIL

488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.45a


:488F:0124SUCESSOR

488F:0110


:488F:014CSUCESSOR

488F:0138


:488F:0160SUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.45b

56


:488F:0124SUCESSOR

488F:0110


:488F:014CSUCESSOR

488F:0138


:488F:0160SUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.45c


:488F:0124SUCESSOR

488F:0110


:488F:014CSUCESSOR

488F:0138


:488F:0160SUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.45d

57

Neste instante, o ponteiro IND_LATUAL está localizado no primeiro elemento

da primeira linha enquanto o IND_LPROX está localizado no primeiro elemento da

segunda linha.

IND_LATUAL

IND_LPROX

(3.46)

⎥⎥⎥⎥⎢= 30310A⎥⎥

⎦

⎤

⎢⎢⎢

⎢⎢

⎣

⎡

09020000020100000

000010200300

....

.....

.6.0

Como o elemento de IND_LPROX está localizado abaixo da diagonal

principal, este elemento deverá ser zerado no processo de triangulariazação.

Para zerar o elemento da primeira coluna que se encontra na segunda linha

(L2), será preciso somar a segunda linha (L2) com o negativo da razão dos campos

ALU dos ponteiros IND_LPROX e IND_LATUAL, multiplicado pela primeira linha

(L1). Tais operações podem ser expressas da seguinte forma:

L2 = L2 – ((IND_LPROX^.ALU / IND_LATUAL^.ALU) * L1) (3.47)

O negativo da razão dos campos ALU dos ponteiros IND_LPROX e

IND_LATUAL será armazenado na variável TEMP. Então, as operações podem ser

expressas da seguinte forma:

L2 = L2 +(TEMP * L1) (3.48)

Uma vez calculado o valor da variável TEMP, o próximo passo será zerar o

primeiro elemento localizado na segunda linha e primeira coluna. Neste caso, serão

eliminadas as referências deste elemento na listas ordenadas por linhas e por

colunas, ou em outras palavras liberar os espaços que este elemento ocupava na

memória para o armazenamento de futuros dados que serão criados durante os

58

cálculos computacionais (preenchimentos). Por questões funcionais, este elemento

será marcado e só será eliminado das listas ordenadas quando todos os elementos

da primeira e segunda linha forem analisados (3.50a).

Agora, o ponteiro IND_LATUAL irá avançar para o próximo elemento da

primeira linha, se este existir. O ponteiro IND_LPROX irá tentar avançar para o

elemento da segunda linha que mais se aproximar, sem ultrapassar, da coluna do

elemento apontado por IND_LATUAL (3.50b).

IND_LATUAL

IND_LPROX

(3.49)

⎥⎥⎥ ⎥⎢= 30310A⎥⎥

⎦

⎤

⎢⎢⎢

⎢⎢

⎣

⎡

09020000020100000

000010200300

....

.....

.6.0

Neste instante, serão comparados os valores dos campos CNLU dos

ponteiros IND_ATUAL e IND_LPROX. Como os valores destes campos são

diferentes (IND_LATUAL^.CNLU=4 e IND_LPROX^.CNLU=2), então será criado um

preenchimento na segunda linha e quarta coluna.

Será criado um novo ponteiro na lista ordenada por linhas em um espaço

vazio de memória, sendo feitos os apontamentos do IND_LPROX para este novo

ponteiro e deste novo ponteiro para o elemento seguinte ao IND_LPROX, se este

existir (3.50c).

Ao campo RNLU deste novo ponteiro será atribuído o valor do campo CNLU

do ponteiro IND_LATUAL, neste caso, o valor 4, indicando que este novo elemento

está na quarta coluna. Ao campo ALU deste novo ponteiro será atribuído o valor -1.

59

O novo ponteiro da lista ordenada por linhas foi criado no endereço

488F:01EC. Fisicamente, este ponteiro está localizado depois do endereço do

último ponteiro desta lista (488F:01D8), porém, logicamente, este ponteiro está

posicionado entre os ponteiros de endereço 488F:014C e 488F:0160, como pode ser

observado nos campos ANTERIOR e SUCESSOR destes ponteiros (3.50c).

A criação e inclusão deste preenchimento na lista ordenada por linhas não

implicam procedimentos de altos custos computacionais, uma vez que os passos

necessários para efetuar tal inclusão são somente a criação de um novo ponteiro e a

mudança dos endereços dos campos “ANTERIOR” e “SUCESSOR” do ponteiro

IND_LPROX e do ponteiro seguinte.

A inclusão do preenchimento, conforme descrita anteriormente, apresenta

ainda a vantagem de manter ordenada a lista organizada por linhas, sem a

necessidade de executar qualquer procedimento extra de arrumação.

60


:488F:0160SUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.50a


:488F:0160SUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.50b

61


:488F:01ECSUCESSOR

488F:014C

ALU: 1.0CNLU: 2ANTERIOR:488F:01EC

:488F:0174SUCESSOR

488F:0160

ALU: - 1.0CNLU: 2ANTERIOR:488F:014C

:488F:0160SUCESSOR

488F:01EC


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.50c

62

Além do ponteiro criado na lista ordenada por linhas, deverá ser criado um

novo ponteiro na lista ordenada por colunas, o qual irá indicar em que linha o

preenchimento, criado na quarta coluna da matriz, se encontra. Para sua criação,

iremos utilizar um ponteiro auxiliar IND_CATUAL_AUX que, inicialmente, irá receber

o endereço de HAPO[4,3], que é o endereço do primeiro elemento da quarta coluna.

Após receber este endereço, o ponteiro auxiliar irá percorrer toda a quarta coluna até

encontrar a posição em que este deve ser inserido para manter a lista devidamente

ordenada (3.51a). O campo RNLU deste elemento receberá o valor 2, indicando que

o preenchimento será criado na segunda linha da quarta coluna.

O novo ponteiro da lista ordenada por colunas foi criado no endereço

488F:0284. Fisicamente, este ponteiro foi criado depois do endereço do último

ponteiro desta lista (488F:0278), porém, logicamente, este ponteiro está posicionado

entre os ponteiros de endereço 488F:0248 e 488F:0254, como pode ser observado

nos campos ANTERIOR e SUCESSOR dos mesmos (3.51b).

A criação e inclusão deste preenchimento na lista ordenada por colunas

implicam a criação de um novo ponteiro, a execução de uma busca na coluna para

encontrar a posição que o novo ponteiro dever ser inserido logicamente na lista e a

mudança dos endereços dos campos “ANTERIOR” e “SUCESSOR” do ponteiro

IND_CATUAL_AUX e do ponteiro seguinte.

A inclusão do preenchimento, conforme descrita anteriormente, além de evitar

a cópia de elementos para o final da estrutura também apresenta a vantagem de

manter organizadas as listas ordenadas por linha e por colunas sem a necessidade

de executar qualquer procedimento extra de arrumação.

63


:488F:01ECSUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0160SUCESSOR

488F:01EC


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0254SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.51ª


:488F:01ECSUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0160SUCESSOR

488F:01EC


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0284SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:0254SUCESSOR

488F:0284


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.51b

64

Após a criação do preenchimento nas listas ordenadas, podemos observar

que o ponteiro IND_LATUAL está posicionado no último elemento da primeira linha

(IND_LATUAL=HAPO1[1,2]), indicando que não será preciso comparar outros

elementos entre estas duas linhas. Neste instante, os elementos selecionados

deverão ser eliminados nas listas ordenadas.

Na lista ordenada por linhas, basta eliminar os elementos selecionados nos

processos anteriores (3.52a).

Na lista ordenada por colunas, será preciso eliminar a referência ao elemento

eliminado. Para isto, será usado um ponteiro auxiliar (IND_CATUAL2), que será

posicionado no primeiro elemento da coluna em que o elemento estava localizado

(IND_CATUAL2:=HAPO2[AUX_CNLU,3]) (3.52b), percorrendo esta coluna até

encontrar um elemento com o valor da linha correspondente ao elemento eliminado

(IND_CATUAL2^.RNLU<>LN_PROX)(3.52c).

Uma vez encontrado o elemento em questão, este será eliminado da lista

ordenada por colunas (3.52d).

65


:488F:01ECSUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0160SUCESSOR

488F:01EC


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0284SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:0254SUCESSOR

488F:0284


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.52a


:488F:01ECSUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0160SUCESSOR

488F:01EC


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0284SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:0254SUCESSOR

488F:0284


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.52b

66


:488F:01ECSUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0160SUCESSOR

488F:01EC


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0284SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:0254SUCESSOR

488F:0284


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278


:488F:0218SUCESSOR

488F:020C NILNIL

3.52c


:488F:01ECSUCESSOR

488F:014C


:488F:0174SUCESSOR

488F:0160


:488F:0160SUCESSOR

488F:01EC


:488F:0188SUCESSOR

488F:0174

ALU: 3.0CNLU: 5


488F:0188

ALU: 1.0CNLU: 3


488F:019C

ALU: 2.0CNLU: 4


488F:01B0

ALU: 2.0CNLU: 4


488F:01C4

ALU: 9.0CNLU: 5


488F:01D8


:488F:0138SUCESSOR

488F:0124 NILNIL


:488F:020CSUCESSOR

488F:0200


:488F:0224SUCESSOR

488F:0218


:488F:0230SUCESSOR

488F:0224


:488F:023CSUCESSOR

488F:0230


:488F:0248SUCESSOR

488F:023C


:488F:0284SUCESSOR

488F:0248


:488F:0260SUCESSOR

488F:0254


:488F:0254SUCESSOR

488F:0284


:488F:026CSUCESSOR

488F:0260


:488F:0278SUCESSOR

488F:026C


488F:0278 NILNIL

3.52d

67

CAPÍTULO IV

ESTRATÉGIAS DE PIVOTAMENTO

Neste capítulo, iremos utilizar o processo de Eliminação Gaussiana (EG) para

solucionar um sistema de equações lineares com matrizes esparsas. Independente

do método utilizado na solução do sistema, o uso de uma estratégia de pivotamento

é uma ferramenta que pode ser eficientemente utilizada para tentar minimizar o

número de preenchimentos tentando preservar, tanto quanto possível, a esparcidade

original da matriz e, ao mesmo tempo, manter os erros de arredondamento nos

menores valores possíveis, sendo que, em alguns casos, somente a utilização de

um pivotamento adequado irá garantir a estabilidade do sistema durante os cálculos

computacionais.

Normalmente, os requisitos de preservar a esparcidade e a precisão não

podem ser satisfeitos simultaneamente. É preciso uma atenção especial para

manter um certo balanço nas exigências quanto à esparcidade e precisão. Alguns

exemplos onde a falta de tal balanço provocou resultados catastróficos podem ser

observados em Zlatev (1991). A seguir podem se observar algumas estratégias de

pivotamento.

4.1 – Pivotamento para Matrizes Densas

Seja nxnRA ∈ uma matriz quadrada genérica. Assuma que uma Eliminação

Gaussiana seja utilizada para representar a matriz A como o produto de uma matriz

triangular inferior nxnRL ∈ e uma matriz triangular superior nxnRU ∈ , ou seja, A = LU.

68

Sej

(4.1)

para assegurar que os cálculos computacionais não irão comprometer os resultados.

Para o estágio considere os três conjuntos a seguir:

é a parte ativa da matriz

iii. é a parte ativa da coluna j no estágio s;

parte ativa da matriz é a parte que ainda não foi triangularizada.

esso de pivotamento são

normalmente executados por uma das seguintes regras:

a )(sija o elemento da linha i e coluna j da matriz A no estágio s da Eliminação

Gaussiana. A fatoração é executada da seguinte forma:

)(1)()()()1( )( s

sjs

sss

iss

ijs

ij aaaa −+ −= a

onde:

• s = 1, 2, ..., n-1;

• i = s+1, s+2, ..., n;

• j = s+1, s+2, ..., n;

• }1-n ..., ,2 ,1{ 0)( ∈∀≠ sa sss

O elemento )(sss é conhecido como “elemento pivô” ou simplesmente “pivô”.

O processo de pivotamento é constituído pelo intercâmbio de linhas e colunas da

matriz A, de acordo com algum critério, para garantir uma escolha adequada do

elemento pivô. Em muitos casos, mudanças de pivô são necessárias até mesmo

a

1}-n ..., 2, ,1{∈s

i. A no estágio s; sA

ii. is é a parte ativa da linha i no estágio s; R

jsC

onde:

-

Os intercâmbios de linhas e colunas do proc

69

a parte ativa i (ou da parte ativa da coluna j) no

estágio s. Mova este elemento para a

(ou das colunas

valor

absoluto da parte ativa da matriz A no estágio s. Mova este elemento para a

posiçã

P e Q, onde a

matriz será uma matriz para permutar linhas enquanto a matriz Q será uma matriz

para permutar colunas. Neste caso o uma

estratégia de pivotamento pode ser representado da seguinte forma:

tilizar qualquer pivotamento para

garantir a estabilidade. Porém, o uso de pivotamento para tentar manter a

esparc . Alguns

exemplos podem ser observados em Zlatev(1991).

Ste

A matriz A é não singular (existe );

os sem erros de

arredondamento;

Pivotamento Parcial – seja )(sisa (ou )(s

sja ) um dos maiores elementos em

valor absoluto d isR da linha jsC

posição (s,s) pelo intercâmbio das linhas i e s

j e s).

Pivotamento Completo – seja )(sa um dos maiores elementos emij

sA

o (s,s) pelo intercâmbio tanto das linhas i e s quanto das colunas j e s.

Os intercâmbios necessários para qualquer uma das duas regras anteriores

podem ser representados por matrizes de permutações denominadas

P

, o processo de decomposição utilizand

nxnnxn Q ,RP , RPAQLU ∈∈= (4.2)

Um critério importante que deve ser observado é como a estratégia de

pivotamento afeta a estabilidade do processo de EG, isto é, algumas matrizes

podem ser decompostas sem que seja necessário u

idade da matriz pode comprometer a estabilidade desta durante a EG

wart (1973) prova que se as seguintes condições são satisfeitas:

• 1−A

• Os cálculos computacionais podem ser executad

então, não irá acontecer nem “Overflow” nem “Underflow”.

70

O algoritmo EG com qualquer uma das duas regras de pivotamento (parcial

ou completo) não irá falhar, isto é, todos os elementos pivôs serão não nulos.

odavia, erros de arredondamento geralmente são inevitáveis quando

cálculos computacion osição

resultante da EG pode ser representada da seguinte forma:

T

ais são realizados em computadores. Então, a decomp

EQLU PA += (4.3)

o

nde nxnRE ∈ é chamada de matriz de perturbação, e seus elementos

..., 2, (i eij 1, n) ..., 2, 1, j n, == satisfazem a seguinte relação

επ nij b ne ≤ (4.4)

onde ε é a precisão do computador, π é uma constante de ordem O(1) que

independe da matriz A, e ( ) a maxb )s(ijnj sn,i s,kslK ≤≤≤≤≤≤

= .

4.2 – Conceitos básicos para construção

ri s.

urante o processo de Eliminação Gaussiana (EG) de uma matriz esparsa A

se

de estratégias de pivotamento para

mat zes esparsa

D

0=) , mas se 0≠)s(isa e 0≠)s(

sja então será criado um novo elemento não nulo

(preenchimento) na linha i e coluna j no próximo estágio da EG, ou seja, 01 ≠+ )s(ija .

Para manter baixos o tempo computacional e a exigência de armazenamento

deve-se tentar manter o número de preenchimentos pequeno. O requisito de manter

o número de preenchimentos pequeno é equivalente ao requisito de preservar a

esparcidade da matriz A durante a os cálculos dos fatores L e U. Uma estratégia de

s(ija

71

e pivotamento para matrizes esparsas tem a finalidade de calcular

decomposições e mais precisas e esparsas. Os requisitos de esparcidade e

precis

ento para matrizes esparsas normalmente tentam conciliar este dois

requisitos.

s estratégias de pivotamento podem ser divididas em três grupos (Zlatev-

1991):

• Grupo 1 – Estratégias de pivotamento com mudanças a priori;

• mento baseadas no uso da função de

custo de Markowitz;

Um es esparsas pertencentes a

qualquer um dos três grupos anteriores pode ser obtida de alguma estratégia de

pivotamen

• Relaxamento da exigência de precisão;

eja r(i,s) e c(j,s) o número de elementos não nulos na parte ativa da linha

i no estágio s e na parte ativa da coluna j no estágio s. Seja

pivotamento é uma ferramenta muito útil na tentativa de se evitar a criação excessiva

de preenchimentos. Uma vez que o pivotamento evita a criação de preenchimentos,

este também reduz o cálculo computacional necessário para EG e,

conseqüentemente, a propagação de erros computacionais. Neste sentido, uma

estratégia d

L U

ão trabalham em direções opostas, e apesar disto, as estratégias de

pivotam

A

Grupo 2 – Estratégias de pivota

• Grupo 3 – Estratégias de pivotamento baseadas na minimização local

do número de preenchimentos.

a estratégia de pivotamento para matriz

to para matrizes densas utilizando os seguintes princípios:

• Introdução de algum critério adicional para preservar a esparcidade

durante os cálculos computacionais.

isR

jsC

S

72

( )(s)ij

Rais a max

is)s(

ij ∈=α (4.5)

e

( )(s)ij

Cajs a max

js)s(

ij ∈=β (4.6)

laxada pela introdução de um fator

de estabilidade e pela escolha dos elementos pivôs em cada estágio s (s = 1, 2,

..., n-1) entre os elementos não nulos de um conjunto de estabilidade , que

depende da estratégia de pivotamento utilizada e do fator de estabilidade u. Os

elementos deste conjunto satisfazem, pelo menos, uma destas duas relações:

A exigência de precisão é normalmente re

1≥u

ss AB ⊆

is)s(

ijau α≥ , is)s(

ijau β≥ . (4.7)

As estratégias de esparcidade dos três grupos tentam preservar a

esparcidade de diferentes formas. Contudo, o seguinte princípio comum pode ser

formulado para estratégias dos diferentes grupos. Um subconjunto de candidatos a

pivô

conseqüentemente a escolha do

fator de estabilidade u, irão influir diretamente no tamanho do conjunto de

estabilidade e do subconjunto de candidatos . Quanto maior é o fator de

ss (s = 1, 2, ..., n-1) será definido como: * BC ⊆

e}esparcidad de critério algum satisfaz :{ )()()(* sijs

sij

sijs aBaaC ∧∈= (4.8)

O elemento pivô do estágio s será escolhido do subconjunto de candidatos *sC .

O relaxamento da exigência de precisão, e

sB *sC

73

estabi

ões (4.7). Logo, maior será o tamanho conjunto de

estabilidade e o critério de estabilidade adotado para formar o conjunto de

candidatos será aplicado em um conjunto maior.

alguns detalhes das estratégias dos três grupos

mencionados anteriormente.

4.3 – Grupo 1: Estratégias de pivotamento com mudanças a priori

As est

ou colunas de posição. Uma estratégia

(1991) e descrita pelos seguintes passos:

•

n as

lidade u, normalmente, maior será o número de elementos que satisfaçam,

pelo menos, umas das relaç

sB

*sC

A seguir, serão mostrados

ratégias de pivotamento deste grupo podem ser feitas trocando linhas

deste grupo pode ser observada em Zlatev

Passo 1: Troque, a priori, as posições das linhas (colunas) da matriz A

de tal forma que estas fiquem orde ad por um número crescente de

elementos não nulos, isto é, r(1,1) ≤ r(2,1) ≤ ... ≤ r(n,1)

• Passo 2: No estágio s (s = 1, 2, ..., n-1) da EG escolha como pivô um

elemento ) na linha s (coluna s) que tenha o menor número de

te elemento para a posição (s,s)

trocando sua coluna (linha) de posição com a coluna (linha) s.

Uma vez que foram feitas as trocas de linhas no Passo 1, então os conjuntos

e serão definidos da seguinte forma:

)s(sja ( )s(

isa

elementos não nulos na coluna C ( R ) e que satisfaça a primeira

(segunda) condição (4.7). Traga es

js is

*ssB C

} : { )()()( sss auRaaB α≥∧∈= (4.9)

:{ )()(* aaC ss=

sssjsssjsjs

(s)sm

*(s)sm

*)( sjcsmcBCCaB ssss

sjssjsjs ≥⇒∈∉∈∧∈ (4.10) )},(),(a ,a ,(

74

a ormar este

conjunto, serão escolhidos os maiores elementos em módulo (

A definição (4.9) do conjunto de estabilidade sB diz que, par f

ss)s(

sjau α≥ ) da parte

ativa d sj

definição (4.10) do conjunto de candidato à pivô diz que os elementos deste

conjunto serão escolhidos os elementos sj

possuírem o menor número de elementos não nulos em suas colunas

s)s(

sj ≥⇒∈∉∈ .

Se forem feitas as trocas das colunas no Passo 1, então, os conjuntos e

a linha s ( )s( Ra ∈ ).

ss

A

do conjunto de estabilidade ( )s( Ba ∈ ) que s

))s,j(c)s,m(cBa ,Ca ,Ca( s(s)sm

*s

(s)sm

*

s

sC serão definidos da seguinte forma:

B

*

} : { )()()(sss

sisss

sisiss auCaa β≥∧∈= (4.11)

to de estabilidade diz que, para formar este

conjunto, serão escolhidos os maiores elementos em módulo (

B

),(),(a ,a ,(:{ (s)ms

*(s)ms

*)()()(* sjrsmrBCCaBaaC ssss

isss

iss

iss ≥⇒∈∉∈∧∈=

}

A definição (4.11) do conjun sB

ss)s(

isau β≥ ) da parte

ativa da coluna s ( ).

este

conjunto serão escolhidos os elementos do conjunto de estabilidade ( ) que

possuírem o menor número de elementos não nulos em suas linhas

Ca( s(s)ms

*s

)s(is ≥⇒∈∉∈ .

Considere a seguinte matriz :

(4.12

ss)s(

sj Ca ∈

)

A definição (4.12) do conjunto de candidato à pivô diz que os elementos d

s)s(

is Ba ∈

))s,j(r)s,m(rBa ,Ca , *s

(s)ms

A

75

⎤

⎢⎢⎡

0201001006000....1.0

Os números de elementos não nulos em suas linhas no estágio s=1 são:

• 2

• 3

• 3 (4.14)

•

Executando o passo 1 da estratégia de pivotamento, as linhas da matriz

serão trocas de tal forma que estas fiquem ordenadas pelo número crescente de

elementos não nulos. Desta forma, a matriz terá a seguinte estrutura:

⎤

⎢⎢⎢⎢⎢⎡

=

00301001002010010

006000

...

...

.1.0

(4.15)

O

⎥⎥⎥⎥

⎦⎢⎢⎢⎢

⎣

=

010200209002010003010010

......

...A (4.13) ⎥⎥

=),(r 11

=),(r 12

=),(r 13

2

• =),(r 15 4

=),(r 14

A

⎥⎦⎢⎣ 10200209 ....

⎥⎥⎥⎥⎥002010 ..

A

elemento 11α será 6.0, ou seja, o maior elemento, em módulo, da linha 1. O

conjunto de estabilidade com um fator de estabilidade sB 4=u será:

}a{Bs 15= (4.16)

76

O

nto pivô será o . Neste caso, será preciso trocar de posição as

colunas nº 1 e nº 5, sendo que a matriz

⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

=

09020020100100103

0102002010001000

.......

....

.6.0

A

Pode-se o

de elementos não nulos do que a primeira coluna. Se o elemento pivô escolhido

fosse o elemento , teríamos que zerar somente o elemento , ou seja, teríamos

apena ç

-s

mostra

que a escolha de um fator de estabilidade inadequado pode provocar a criação de

um n

conjunto de candidatos *sC será:

}a{C*s 15= (4.17)

O eleme 15a

A ficará da seguinte forma:

⎥⎥⎥⎥⎥

0010 . (4.18)

bservar, em (4.18), que a quinta coluna contém um número menor

15a 55a

s que efetuar uma opera ão elementar entre as linhas 1 e 5. Com o elemento

pivô 11a deve zerar os elementos 1514 a e a ,a13 . Para isto devem e efetuar

operações elementares entre as linha 1 e 3, 1 e 4, e 1 e 5. Este exemplo

úmero maior de preenchimento, mais cálculos computacionais e

conseqüentemente uma maior propagação de erros, podendo, inclusive,

comprometer a estabilidade do processo EG.

Se usarmos um fator de estabilidade 10=u , o conjunto de estabilidade

referente à matriz apresentada em (4.15) será:

(4.19)

sB

}a,a{Bs 1511=

O conjunto de candidatos *sC será:

77

C*s }a{ 11= (4.20)

elemento pivô será e, neste caso, não será preciso efetuar troca de

colunas e

teríamos apenas que efetuar uma operação

Considere a matriz do exemplo (4.13). Uma vez ordenadas suas linhas em

um número crescente de elem

(4.15). Neste exemplo, pode-se observa

linha e sim na segunda linha onde o elemento é

o único el

Outras estratégias do Grupo 1, baseadas em trocas a priori, podem ser

observadas em Duff et al (1974) e Reid (1977).

é mais direta e confiável do que códigos

baseados nas estratégias do grupo 2 ou do grupo 3.

11aO

para efetuar EG terá que ser zerado somente o elemento 51a , ou seja,

elementar entre as linhas 1 e 5.

entos não nulos, esta matriz assume a estrutura

r que a melhor escolha para o elemento

pivô não se encontra na primeira 23a

emento não nulo da terceira coluna.

A estratégia de pivotamento pertencente a este grupo apresenta várias

vantagens sobre as estratégias de pivotamento dos dois outros grupos (Zlatev –

1991). Entre elas podemos destacar:

• Somente trocas de linhas (ou colunas) são necessárias durante a EG.

Tais trocas podem ser facilmente e eficientemente implementadas

(Gustavson – 1972 e 1978).

• O desenvolvimento de códigos computacionais baseados nesta

estratégia de pivotamento

• A quantidade de informação adicional que deve ser mantida e

atualizada durante a fatoração é menor do que a necessária para

estratégias dos grupos 2 e 3.

78

• O código computacional, normalmente, será menor do que os códigos

baseados nas estratégias dos grupos 2 e 3.

tipo de estratégia podem produzir muitos preenchimentos durante

as decomposição de algumas matrizes. Infelizmente, esta desvantagem é bastante

séria,

d

com o padrão de esparcidade bem

similar. Nestes casos, é interessante testar o desempenho de um código baseado

na estratégia do grupo 1 antes d

utilizada para um problema específico.

a o caso em que todos os elementos

não nu

pode alterar drasticamente a estrutura da matriz e o padrão de

esparcidade. Alguns exemplos disto podem ser observados em Zlatev (1991).

4.4 – Grupo 2: Estratégias de pivotame

de Markowitz.

As estratégias do grupo 2 são baseadas na função de custo de Markowitz dos

elementos não nulos. A função de custo de Markowitz do elemento é definida

como sendo o produto do número dos elementos da parte ativa da linha i, com

coluna j, com exceção do próprio elemento .

Existe somente uma desvantagem das estratégias do grupo 1. Os códigos

baseados neste

porque o excesso de preenchimentos irá provocar o aumento do tempo

computacional e do espaço necessário na memória dos computa ores para

armazenamento dos dados do problema. Desta forma, as estratégias de

pivotamento deste grupo são indicadas para problemas que, durante a resolução,

irão decompor uma seqüência de matrizes

e decidir qual estratégia de pivotamento deve ser

As conclusões anteriores são válidas par

los são considerados durante todo o processo de EG, isto é, quando a forma

clássica de explorar a esparcidade é aplicada. Se a forma orientada a computador é

utilizada (os elementos 01 ≠+ )s(ija são removidos do processo de armazenamento

dinâmico quando estes forem muito “pequenos”) então, esta situação pode mudar,

pois, isto

nto baseadas no uso da função de custo

)s(ija

exceção do próprio elemento )s(ija , pelo número dos elementos da parte ativa da

)s(ija

79

]

[ ] [ 11 −−= )s,i(rM ijs )s,j(c* (4.21)

Tal produto pode ser interpretado como sendo o número máximo de

preenchimentos que pode ser cria

estágio s. É claro que isto só aconteceria se todos os elementos das intersecções

das colunas dos elementos não nulos da linha i com as linhas dos elementos não

nulos da coluna j fossem elementos nulos no estágio s. Observe o exemplo a

seguir.

do se o elemento )s(ija for escolhido como pivô do

00000000000000000000

000000

262422

151311

aaaa

aaa

62

55

42

35

aa

a (4.22)

A função de custo de Markowitz do elemento , no exemplo acima, será

igual a = [3-1]*[3-1] = 4, ou seja, se o elemento for escolhido como pivô.

Neste caso, serão criados 4 preenchimentos nos locais marcado com X como pode

ser co

)(a 222

222M )(a 222

nstatado a seguir.

XXaa

XXa0000

0042

aa

00000

000000

62

55

35

2624

(4.23)

aaaaa

00000

22

151311

80

o, ero de preenchimentos será menor do

que 4. Observe o exemplo a seguir onde o elemento ≠) .

Isto ocorre porque os elementos )(a 244 , )(a 2

46 , )(a 264 e )(a 2

66 são nulos. Se algum

destes elementos não for nulo entã o núm

0244(a

00000 62

55

a

Durante o processo de EG, o valor do elemento )(a 2 será alterado e somente

serão criados 3 preenchimentos nos locais marcado com X, como pode ser

00000000000000

0000

4442

35

262422

1311

aaa

aaa

aaa

(4.24)

constatado a seguir. Porém a função de custo de Markowitz do elemento

continuará valendo 4.

0015

a

44

)(a 222

XXaa

Xaaa

aaaaaa

00000000

00000000

000000

62

55

4442

35

262422

151311

(4.25)

Para saber o número real de preenchimentos que serão criados pela escolha

de um determinado pivô , durante um estágio s, seria preciso verificar se todas

as intersecções das colunas dos elementos não nulos da linha i com as linhas dos

elementos não nulos da coluna j são elementos nulos. Isto pode comprometer o

tempo computacional do processo.

O custo ótimo de Markowitz no estágio s ( ) é definido da seguinte forma:

)s(ija

sM

81

( 26)

D kowitz, no estágio s, pode ser (e

freqüentemente é) maior do que o mínimo custo de Markowitz no estágio s

), isto porque o mínimo custo ij não

nulos da parte ativa da matriz, enquanto o custo ótimo só considera os elementos

não nulos pertencentes ao conjunto de estabilidade .

)M(minM ijsBa

ss

)s(ij ∈

= 4.

eve ser ressaltado que o custo ótimo de Mar

( )Mmin(M ijs*s = considera todos os elementos (a )s

)s(ija s

Seja um conjunto de dimensão

B

sI )s(p ( 11 +−≤≤ sn)s(p ) dos índices das

linhas da parte ativa da matriz A que possuam a menor quantidade de elementos

não nulos no estágio s, definido da seguinte forma:

82

s i{I p(s)) ..., 2, 1,m },n ..., 1, s,s{(i }i..., ,i , mp(s)2 =+∈=

nde:

i(r

1 (4.27)

o

)s,i(r...)s,i(rs, )s(p≤≤≤ 21 (4.28)

)s,i(r)s,r(i )nis

)

Ii( p(s)s ≤⇒≤≤∧ (4.29) ∉

CO conjunto de estabilidade ( s ) e o conjunto de candidatos a pivô ( s ) nesta

estratégia são definidos da seguinte forma:

B *

)}Ii()au( )Aa( /a{B sis)s(

ijs)s(

ij)s(

ijs ∈∧≥∧∈= α (4.30)

)}MM()Ba( / a{C sijss)s(

ij)s(

ij*s =∧∈= (4.31)

As estratégias de M

arkowitz podem ser também aplicadas para efetuarem

trocas de colunas ao invés de linhas. Neste caso, as fórmulas anteriores (4.28, 4.29

e 4.30) serão modificadas para

)s,i(c...)s,i(c)s,i(c )s(p≤≤≤ 21 (4.32)

)s,j(c)s,c(j )njsIj( p(s)s ≤⇒≤≤∧∉ (4.33)

)}Ij()au( )Aa( /a{B sjs)s(

ijs)s(

ij)s(

ijs ∈∧≥∧∈= β (4.34)

As estratégias de pivotamento baseadas na função de custo de Markowitz

podem ser divididas em duas classes:

• A classe de Estratégias de Markowitz Generalizadas (EMG) - esta

classe engloba todas as estratégias onde o elemento pivô do estágio s

83

) é escolhido arbitrariamente do conjunto de candidatos

• A classe de Estratégias de Markowitz Generalizadas Aprimoradas

s (s

alor absoluto do conjunto de candidatos .

que classe de estratégia

deve ser escolhida entre a EMG e a EMGA para um problema específico. Tal

escolha pode não parecer muito importante para a precisão dos resultados, uma

vez que os elementos do conjunto de candidatos C são também elementos do

es de

matrizes para as quais o uso de estratégias de pivotamento da classe EMGA é

nitidam

(s = 1, 2, ..., n-1*sC .

(EMGA) - esta classe contém todas as estratégias baseadas na função

de custo de Markowitz onde o elemento pivô do estágio = 1, 2, ...,

n-1) é escolhido como sendo aquele elemento que possuir o maior

v *sC

Uma questão importante que deve ser levantada é

*s

conjunto de estabilidade sB nas duas estratégias de pivotamento. Contudo, pode-se

verificar tanto experimentalmente, quanto teoricamente, que existem class

ente superior às estratégias da classe EMG. Tal afirmação é comprovada

pelos seguintes teoremas:

Teorema 4.1: Seja nxnRA∈ uma matriz diagonalmente dominante (o valor absoluto

de qualquer elemento da diagonal é maior do que a soma dos valores absolutos dos

outros elementos em suas linhas) e de estrutura simétrica

( n) ..., 2, (1,j e n) ..., 2, (1,i aa jiij ∈∀∈∀≠⇒≠ 00 ). Então, o processo EG é estável,

quando qualquer estratégia de pivotamento da classe EMGA é usada.

84

Teorema 4.2: Assuma que:

i) O sistema bAx = tem solução;

) é a solução encontrada; yii

iii) δ<− yx seja exigido.

Seja )(G δ o conjunto de todas as possíveis seqüências de pivotamento da

classe EMG que não são aceitáveis (isto é, qualquer estratégia do conjunto )(G δ

pode ser escolhida durante a fatoração da matriz que não irá satisf

seja,

A azer (iii), ou

δ≥− yx ).

Seja )(G* δ o conjunto de estratégias de pivotamento da classe EMGA com

parâmetros iguais aos da Classe u e )s(p 1)-n ..., 2, ,s( 1= )(G δ .

Então G* δ .

teriores ns exempl numéricos em q e as

estratégias de pivotamento da classe EMG falham, enquanto estratégias de

pivotamento da classe EMGA não, podem ontradas e Zlatev (1991).

s estratégias de pivotamento apresentadas anteriormente dependem de dois

parâm e lidad

irão

afetar diretamente o tamanho do conjunto de índices e também o tamanho dos

)(G)(δ ⊆

As provas dos teoremas an e algu os u

ser enc m

A

etros: o fator d estabi e u e do número p(s) de linhas (ou colunas) de

onde será escolhido o elemento pivô do estágio s. Mudanças no fator de

estabilidade u irão alterar o conjunto de estabilidade sB e conseqüentemente o

conjunto de candidatos *sC . Alterações no número p(s) de linhas (ou colunas)

s

conjuntos de estabilidade sB e de candidatos *sC .

A estratégia original de Markowitz (1957) utilizava um fator de estabilidade

∞=u e um conjunto sI de dimensão 1

I

+−= sn)s(p . Isto significa que nenhuma

restrição de estabilidade será aplicada e, conseqüentemente, o conjunto de

estabilidade sB será formado por toda a parte ativa da matriz A, ou seja, ABs = . O

valor de p(s) utilizado implica afirmar que o conjunto de índices sI será formado

pelos índices de todas as linhas da parte ativa da matriz A . Tais valores de u e

)s(p podem deixar o código computacional excessivamente lento, podendo

85

inclusive comprometer a estabilidade do processo EG. Por tais razões os valores

anteriores de e não são mais utilizados nos códigos atuais.

1), podem-se observar outros exemplos em que a escolha de

valores inapropriados de e para alguns problemas podem demorar muito

durant

u )s(p

Em Zlatev (199

u )s(p

e a procura do elemento pivô, comprometendo o tempo computacional do

processo de EG.

A seguir, podemos observar alguns valores de u e )s(p utilizados em três

códigos computacionais conhecidos:

Código Tipo de u )s(p

Estratégia

MA18 (Curtis e Reid (1971)) EMG 4=u 1+− sn

MA28 (Duff (1977)) EMG 10=u 1+− sn

Y12M (Zlatev et al(1981)) EMGA [ ]16 ,u 4∈ )q,snmin( 1+−

Os valores de e de da tabela anterior são os valores recomendados

nos respectivos códigos, porém podem-se especificar valores diferentes destes

utilizados. Os valores de dos dois primeiros códigos são fixos. No código

Y12M, de Zlatev et al., o valor recomendado de

u )s(p

)s(p

3=q para matrizes esparsas em

geral.

m tação de estratégias do primeiro grupo (Estratégias de

Pivotamento com Mudança a Priori). A maior dificuldade de implementação surge

da ne a h

ra junto de

índices

A implementação de uma estratégia deste grupo para matrizes esparsas é

mais difícil do que a imple en

cessidade de ordenar s lin as (ou colunas) em um número crescente de

elementos não nulos na partes ativa da matriz pa a elaboração do con

I no início de cada estágio . Este processo requer um tempo

computa ssário na memória. Porém, o

número de preenchimentos gerados durante a EG é normalmente reduzido em

comparação às estratégias do primeiro grupo. Conseqüentemente, tal redução irá

s

cional extra e um aumento do espaço nece

86

provocar um redução considerável no tempo computacional total e no espaço

necessário de memória para resolver o sistema bAx = .

4.5 – Grupo 3: Estratégias de pivotamento baseadas em uma minimização local

de preenchimentos

s estratégias do grupo 3 são baseadas no número de preenchimentos

criado l

rá chamado d Função de Custo de Preenchimentos ( ). O menor

valor da função de custo é chamado de valor Mínimo da Função de Custo de

Preenchimen efinido da seguinte forma:

F *ijs =

O menor valor da função de custo dos elementos do conjunto de

estabilidade é chamado de valor Ótimo da Função de Custo de Preenchimentos

) e é definido da seguinte forma:

s(s)ijijss ∈≤≤∈= (4.36)

É claro que F

Preenchimentos é calculado somente nos elementos do conjunto de estabilidade,

enquant reenchimentos é calculado em

toda parte ativa da matriz

A

s por cada e emento )s(ija se este for escolhido como pivô do estágio s da EG.

Tal valor se e ijsF

ijsF

tos ( ijsF ) e é d*

)ni s1},-n ..., 2, 1,{(s )Fn( ijs ≤≤∈ (4.35) mi

ijsF

B

( sF

s

F )Ba n,i s1},-n ..., 2, 1,{(s )Fmin(

*

ijsF≥ uma vez que o valor Ótimo da Função de Custo de s

o o valor Mínimo da Função de Custo de P

A .

atos será definido como:

Sejam os conjuntos I e B como já definidos anteriormente em (4.27) e

(4.30), respectivamente. O conjunto de candid

s s

*sC

87

s(ij

)s(ij

*s = }FF B sijss

) =∧∈ (4.37) a/a{C

Observe o exemplo abaixo

aaaa

444342

34

2422

000

(4.38)

aa

aa

13

1311

0

000

No t

não nulos sã

(4.39)

a

es ágio 1=s a Função de Custo de Preenchimentos ( ijsF ) dos elementos

o:

1111 =F

1131 =F

0221 =F

0241 =F

1131 =F

2341 =F

421 =F

2431 =F

1441 =F

1

Para um 5=)s(p e um fator de estabilidade ∞=u , os conjuntos sI e sB

serão:

}5 4, 3, ,2 ,{I s 1= (4.40)

}a,a,a,a,a,a,a,a,a{Bs 444342343124221311= (4.41)

88

O valor Ótimo da Função de Custo de Preenchimentos ( sF ) é igual a zero, e o

conjunto de candidatos *sC será definido como:

(4.42)

• A classe de Estratégias de Mínimo “Fill-in” Generalizadas

}a,a{C*s 2422=

As estratégias de pivotamento baseadas na Função de Custo de

Preenchimentos podem ser divididas em duas classes:

• A classe de Estratégias de Mínimo “Fill-in” Generalizadas (EMFG)

- esta classe engloba todas as estratégias onde o elemento pivô do

estágio s (s = 1, 2, ..., n-1) é escolhido, arbitrariamente, do conjunto de

candidatos *sC .

Aprimoradas (EMFGA) - esta classe contém todas as estratégias

baseadas na função de custo de preenchimento onde o elemento pivô

do estágio s (s = 1, 2, ..., n-1) é escolhido como sendo aquele

elemento que possuir o maior valor absoluto do conjunto de candidatos *sC .

No Exemplo (4.38), se estiver sendo utilizada uma estratégia da classe

EMFG, o elemento pivô poderá ser qualquer um dos dois elementos do conjunto de

candidatos ( 22a ou 24a ). Se estiver sendo utilizada uma estratégia da classe EMFGA

o elemento pivô será aquele que possuir o maior valor absoluto entre os dois

elementos, ou seja, o elemento pivô será o elemento 22a se 2422 aa > ou será 24a

se 2224 aa > .

A implementação das estratégias de pivotamento deste grupo é muito mais

difícil do que a implementação das estratégias dos outros dois grupos anteriores.

89

Duff e

odem ser úteis para

algumas matrizes especiais. Desta forma, estratégias deste grupo são incluídas em

pacote

4.6 – Escolha da estratégia de Pivotamento

nalisando as estratégias de pivotamento apresentadas neste capítulo, pode-

se con

e

uma seqüência de matrizes com o padrão de

esparcidade bem similar. Nestes casos, é interessante testar o desempenho de um

código baseado na estratégia do grupo 1 antes de decidir qual estratégia de

pivotamento deve ser utilizada para um problema específico.

As estratégias de pivotamento do grupo2 (estratégias de pivotamento

baseadas no uso da função de custo de Markowitz) não apresentam a desvantagem

das estratégias do grupo 1 de produzir muitos preenchimentos para alguns tipos de

matrizes, porém as estratégias do grupo 2 necessitam de mais espaço para o

armazenamento de dados, efetua mais cálculos computacionais e apresenta maior

dificuldade na implementação quando comparadas às estratégias do grupo1.

Mesmo apresentando tais desvantagens, as estratégias deste grupo normalmente

Reid (1974) fizeram alguns experimentos computacionais com estratégias

deste grupo e concluíram que “apesar deste algoritmo ser muito mais caro

computacionalmente, sob esta consideração seu custo não é totalmente proibitivo”.

As estratégias de pivotamento do terceiro grupo p

s computacionais para matrizes esparsas, não devendo, contudo, ser a única

estratégia de pivotamento disponível.

A

cluir que não existe uma estratégia mais indicada para todas as situações.

As estratégias de pivotamento do grupo 1: (estratégias de pivotamento com

mudanças a priori) apresentam várias vantagens sobre as outras duas estratégias,

porém a principal desvantagem das estratégias deste grupo é elas poderem produzir

muitos preenchimentos durante a decomposição de algumas matrizes com um

padrão de esparcidade específico.

As estratégias de pivotamento deste grupo são indicadas para problemas qu

durante a resolução irão decompor

90

são mais vantajosas, pois, por gerarem menos preenchimentos, acabam gastando

menos tempo nos cálculos computacionais.

As estratégias de pivotamento do grupo 3 (estratégias de pivotamento

baseadas em uma minimização eenchimentos) apresentam uma

implementação muito difícil e alto custo computacional. Apesar destes algoritmos

serem muito mais caros computacionalmente, em comparação às estratégias do

grupo 1 e do grupo 2, seu custo não é totalmente proibitivo.

As estratégias de pivotamento do terceiro grupo podem ser úteis para

algumas matrizes especiais, como, por ex mplo, a matriz com o seguinte padrão de

esparc

local de pr

e

idade:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

xxxxxxxxxxxxxx

xxxx

000000000000000000000000000000000000

00000000000000000000000000000000000000000000000

00000000000000000000000000

xxxx 0000000000

xxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxx

000

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

0
(4.43)

91

tratégia de pivotamento baseado na função de

usto de Markowitz em 4.43 irá provocar um preenchimento três vezes maior do que

a apl

r Duff–1985, Duff–1986, Reid–1986,

Zlatev et al–1981 e Osterby et al–1983), não devendo, contudo, ser a única

estratégia de pivotamento disponível.

Neste trabalho será implementado um código computacional com as

estratégias do grupo 1 e do grupo 2.

A aplicação de qualquer es

c

icação de uma estratégia baseada em uma minimização local de

preenchimentos. Desta forma, estratégias deste grupo são incluídas em pacotes

computacionais para matrizes esparsas (ve

92

MÉTODO SEQÜENCIAL QUADRÁTICO

s Métodos Seqüenciais Quadráticos (MSQ) são considerados como uma

das técn s d

otimizaçã om

Est m o mação

seqüencia ou e ewton (ou

Quasi-Newton) para resolver as condições de K.K.T. do problema original. Como

resultado, tem-se um subproblema que consiste em uma aproximação quadrática da

função o linear das restrições.

Conseqüentemente, este tipo de processo é conhecido também como aproximação

Lagrangeano Projetada, ou aproximação Lagrange-Newton, ver Bazaraa (1993) e

Melo (1998).

este capítulo, iremos abordar alguns aspectos importantes do método

seqüencia uadrátic id rt ão de mestrado

de Melo (1998) e aplicar o modelo de armazenamento de dados e as estratégias de

pivotamento, vistas nos capítulos anteriores, para desenvolver um algoritmo

seqüe ti ar os. Alguns algoritmos serão

aproveitados do trabalho citado anteriormente, não sendo detalhados novamente.

CAPÍTULO V

O

ica mais eficientes para resolução de problemas não lineares e

o c restrições (ver Powell,1983).

es étodos, também conhecidos como métodos de pr gra

l ( recursiva) quadrática (PSQ), empregam o método d N

Lagrangeana otimizada sobre uma aproximaçã

N

l q o, analisar o algoritmo desenvolv o na disse aç

ncial quadrá co p a problemas espars

93

5.1 – D

ara apresentar o conceito deste método, considere um problema não linear

conten

escrição do Método MSQ

P

do unicamente restrições de igualdade onde todas as funções são contínuas

e duas vezes diferenciáveis, como se segue:

ni

Rx onde ∈

l ..., 2, 1,i 0(x)h f(x) min :

== , (5.1)

As condições de otimalidade para o problema (5.1) requerem uma solução

primal e um vetor de multiplicadores de Lagrange qu

xxhvxf t

(5.2)

e:

• - Jacobiano das restrições h(x).

Pode-se escrever o sistema de equações acima de forma mais compacta

como:

. (5.3)

Usando o método Newton-Raphson para resolver (5.3) obtém-se:

k

kkkkk 0=⎥

⎦

⎤⎢⎣

⎡−−

∇+ , (5.4)

Ps.a.

nRx ∈ lRv ∈ e satisfaçam:

,0)(,0)()(

==∇−∇

h

ond

• )x(f∇ - gradiente da função objetivo f(x).

)x(h∇

W 0=)v,x(

vvxx

)v ,x(W)v ,x(W

94

e W.

a

de equações (5.4) da próxima iteração . Escrevendo o

Jacobiano como:

⎡ ∇∇0

2 )x(h)x(L

k

Tk

• –

–

• – representa a Hessiana da função objetivo f(x) no ponto .

Usando (5.2) e (5.5), pode-se escrever (5.4) como:

(5.6)

onde:

• - gradiente da função objetivo no ponto .

Substituindo por

onde:

• W∇ - representa o Jacobiano d

Então, dada solução )v ,x( kk de uma iteração anterior, resolvendo o sistem

obtêm-se os valores )v ,x(

W∇

⎥⎦

⎢⎣ ∇

=∇)x(h

)v ,x(W kkk , (5.5)

⎤

onde:

)x(hv)x(f)x(L kk222 ∇∑+∇=∇ representa a Hessiana do

Lagrangeano da função f(x) no ponto kx .

• )x(h k∇ representa o Jacobiano das restrições h(x) no ponto .

kk

kx

)(2kxf∇ kx

• )(2kxh∇ – representa a Hessiana das restrições h(x) no ponto kx .

),())((,)()()()())((2

kkk

kt

kkkt

kkk

xhxxxhvxhxfvvxhxxxL

−=−∇∇−−∇=−∇+−∇

)x(f k∇ )x(f kx

)xx( k− x∆ em (5.6), obtém-se:

95

kk −=∆

sistema de equações (5.7) para

)x(hx)x(h)x(fv)x(hx)x(L k

tkk −∇=∇+∆∇ 2

(5.7) ∇

Resolvendo o v) ,x( ∆ , onde xxx k ∆+= , até

que , encontra-se uma solução de K.K.T. para (5.1), se esta existir.

Ao invés de resolver o sistema d

de KKT para o problema (5.1), pode-se empregar um subproblema de minimização

quadrática cujas condições de otimalidade são idênticas às condições do problema

original.

de ser observado abaixo, onde o termo constante

foi inserido na função objetivo por conveniência:

0=∆x

e equações (5.7) para encontrar uma solução

Tal subproblema po )x(f k

l ..., 2, 1,i x)x(h)x(h .a. s

x)x(Lxx)x(f)f(x minimizar ),x(PQ

Tkiki

kkkkk

==∆∇+

∆∇∆+∆∇+

02

λ (5.8)

vetor de multiplicadores de Lagrange λ do subproblema quadrático (5.8)

satisfaz:

2 (5.9)

A solução de (5.8)

TT 1 2

O

λ)x(hx)x(L)x(f T∇=∆∇+∇

resulta em um vetor n-dimensional kx∆ , sendo que o novo

ponto 1+kx é definido como:

kkkk xx ∆+=+x α1 (5.10)

onde:

96

• um vetor de busc ional

•

k é a n-dimensx∆

kα é um tamanho de passo não negativo (0 < αk ≤ 1).

do.

5.2 – Algoritmo Seqüencial Quadrático Básico (PSQ)

Início: o contador

Um ponto ótimo do subproblema quadrático (5.8), se existir, é um ponto de

K.K.T. e satisfaz as equações (5.7), onde v é um conjunto de multiplicadores de

Lagrange associados às restrições de (5.8).

A seguir pode-se observar um algoritmo rudimentar para resolução do

subproblema quadrático (5.8), assumindo que o subproblema é bem comporta

Fazer 1=k e selecionar uma solução inicial conveniente

Primal-Dual ( kk .

Passo Principal: Resolver o subproblema quadrático (5.8) para obter uma

solução e o r u

restrições de iguald

)v,x

kx∆ bte m conjunto de multiplicadores de Lagrange 1+kv associados às

ade. Se 0=∆ kx , então )v,x( kk 1+ satisfaz as condições de K.K.T.

(5.2) para o problema P, então PARE. Caso contrário, faça kkk xxx ∆+=+1 ,

incrementar de 1, e repetir o passo principal.

anterior ver Bazaraa (1993).

k

Para uma análise da convergência do algoritmo

97

5.3 - Extensão do algoritmo básico PSQ incluindo Restrições de Desigualdade

onsidere a inclusão de restrições de desigualdade no

proble

i == 0 (5.11)

• Formulação IQP (Innequality Constrained Quadratic Programming)

• Formulação EQP (Equality Constrained Quadratic Programming)

Na formulação IQP todas a restrições do problema original são linearizadas e

incluídas no subproblema quadrático como pode ser observado abaixo.

m ..., 1,j ,)x(g j =≤ 0C

ma P, onde as funções )x(g j são contínuas e duas vezes diferenciáveis,

conforme se segue:

f(x) minimizar :Pl ..., 1,i )x(h s.a. m ..., 1,j )x(g j =≤ 0

Neste caso, existem basicamente duas formulações alternativas para o

subproblema quadrático:

m ..., 1,j x)x(g)x(g

l ..., 1,i x)x(h)x(h s.a.

x)x(Lxx)x(f)f(x r Minimiza:)v ,u ,x(PQ

Tkjkj

Tkiki

kTT

kkkkk

=≤∆∇+

==∆∇+

∆∇∆+∆∇+

0

021 2

(5.12)

Na formulação EQP se tem uma previsão do conjunto ativo , ou seja das

restrições de desigualdade

kI

( )0≤)x(g kj que serão satisfeitas exatamente em seus

limites ( )0=)x(g kj no ponto , e será atualizada a cada iteração. O subproblema

quadrático é definido apenas em função das restrições ativas na iteração :

kx

k

98

kj Ij 0)(ˆ)(g ∈=∆∇+ xxgx kjk

onde:

• )x(g)x(g kjkj = tal qu

i

2k

l ..., 1,i 0)()(h s.a.

)(21)()f(xMinimizar :) v,u ,(

==∆∇+

∆∇∆+∆∇+

xxhx

xxLxxxfx

T

Tkik

kTT

k

(5.13)

e

PQ kkk

KIj ∈

• tal que )x(g)x(g kjk ∇=∇ KIj ∈

Neste trabalho, iremos utilizar a Formulação EQP com uma aproximação

definida positiva B da Matriz Hessiana do Lagrangeano, quando a referida hessiana

não fo

ma seja

definida positiva. O algoritmo utilizado foi o desenvolvido na dissertação de

mestrado de Melo (1998). Desta forma o subprob

r definida positiva. A estratégia para obter tal aproximação é perturbar,

quando necessário, a diagonal principal da matriz Hessiana até que a mes

lema quadrático (5.13) fica:

kT

kjkj

Tkiki x)x(h)x(h s.a. =∆∇+ 0

T

Ij x)x(g)x(g

l ..., 1,i

x Bxx(QP

∈=∆∇+

=

∆′

0

1

(5.14)

• tal que

Tkkkkk x)x(f)f(x r Minimiza:)v ,u , ∆+∆∇+

2

onde:

)x(g)x(g kjkj = KIj ∈

tal que )x(g)x(g kjk ∇=∇ KIj ∈ •

• B é uma aproximação definida positiva da hessiana do

Lagrangeano

)(2kxL∇

99

Neste caso, a resolução do subproblema quadrático consiste apenas da

solução do seguinte sistema de equ

ações lineares.

k

k

k

k

k

Tk

b)x(f

vx

* J

JB−

∇−=

∆

+

+

1

1

0 (5.15)

onde:

kkj

kik

kkj

IjEi

, )x(g)x(h

b

Ij

∈∈

=

(5.16)

kik

Ei ,

)x(g)x(h

∈∈

∇∇

=

ativo atualização do conjunto ativo utilizado

neste trabalho é o mesmo desenvolvido na dissertação de mestrado de Melo (1998).

rática é

que a sua convergência só é garantida quando o algoritmo é iniciado próximo de

uma solução desejada, Gill et al. (1986), enquanto, na prática, esta condição

dificilmente poderá ser realizada.

ma maneira de assegurar a convergência global do algoritmo é garantir que

seja uma solução melhor do que . Isto pode ser feito utilizando o vetor

J

Um aspecto crítico desta formulação é a atualização da previsão do conjunto

kI a cada iteração. O algoritmo de

A principal desvantagem do método de programação seqüencial quad

U

1+kx kx x∆

(soluç

eu valor (função de descida). Para

garantir tal decréscimo na função, introduz-se a idéia da Função de Mérito.

ão do subproblema quadrático) como uma direção de descida para uma

função que garanta um decréscimo razoável no s

100

5.4 – Função

ma Função de Mérito é definida como sendo uma função que, juntamente

com a função objetivo, é minimizada na solução do problema, servindo como função

de de orcionando

ve ser uma função fácil de ser avaliada, e não deve

erá utilizada neste trabalho é a Função Lagrangeana

Aumentada (FALAG), também conhecida como função de penalidade de

multiplicadores.

onsidere primeiro o caso em que todas restrições não lineares são

igualdades. A função Lagrangeana Aumentada associada é definida como:

de Mérito

U

scida e prop uma idéia da não otimalidade do ponto atual.

Preferivelmente esta de

prejudicar a convergência do algoritmo.

A função de mérito que s

C

)x(h)x(h )x(hv f(x) :) v, ,x( TTALAG µµ

21

++ (5.17)

• - multiplicador de Lagrange estimado.

•

F

onde:

v

µ - parâmetro de penalidade não negativa.

ockfaller (1973) introduziu a função de mérito Lagrangeano Aumentado para

o problema contendo restrições de igualdade e desigualdade:

R

))x(g)x(g)x(h)x(h( )x(gu)x(hv)x(f),u,v,x(L TTTT ++++= µµ2

1 (5.18)

nde:

o

101

⎢⎢⎢⎢

⎣

⎡

−

−≥=

contrário caso u

u)x(g se)x(g

)x(gi

iii

i

µ

µ (5.19)

eira derivada descontínua, o que pode

rsveld (1992) para tornar a função de mérito suave, consiste no

créscimo de variáveis de folga as restrições de desigualdade exclusivamente na

definição da função de mérito (de forma que são usadas unicamente na definição do

modo, definimos a seguinte função Lagrangeana

Aumentada:

A função de mérito anterior tem prim

causar dificuldades nas buscas lineares baseadas na primeira derivada.

Uma extensão dessa idéia, desenvolvida por Gill et al. (1986) e usada

também por Elde

a

tamanho do passo). Deste

)s)x(g)x(h( )s)x(g(u)x(hv)x(f),s,u,v,x(FALAG22

21

++++++= µµ (5.20)

As variáveis de folga serão definidas no começo da iteração k como:

TT

⎢⎢

⎣

⎡

−− x(g,ax( 0

=−= contrário caso ),

u )m

0 se)),x(g,max(s i

ki

ki

i

µ

µ0 (5.21)

Podemos reescrever de maneira mais simplificada a relação (5.20),

odificando levemente a definição (5.21), como:

m

)s)x(c( )s)x(c(u)x(f),s,u,v,x( TG 2

1++++= µµ (5.22)

e:

FALA2

ond

⎥⎦

⎤⎡⎤⎡ vx(h⎢⎣

=⎥⎦

⎢⎣

=u

u ,)x(g)

)x(c

102

⎢⎢⎢⎢⎢

⎣

⎡

=∈∈

=

contrário caso ),u

-)(xmax(0,-g

0 e Ei se)),(xmax(0,-gI,i se,

si

ki

kii

µ

µ0

I = conjunto de índices correspondentes às restrições h(x),

E = conjunto de índices correspondentes às restrições ativas g(x).

Definindo-se kuu −=∆ kk λ como direção de busca para os multiplicadores de

estimados ku , Lagrange ( )kkkkk s)x(cx)x(cs ++∆∇−=∆ , como direção de busca

para as variáveis de folga k ks e x∆ como direção de busca para , obtida da

solução do seguinte problema quadrático

kx

0)()(c s.a.

)(21)(f(x

i

2k

=∆∇+

∆∇∆+∆∇+

xxcx

xxLxxxfMinimizar

Tkik

kTT

k (5.23)

onde

)

kλ são os multiplicadores associados a solução kx∆ de (5.23).

Ass , uma busca linear é feita na função de

érito, ao longo das direções de busca

im, para obter a próxima iteração

m kk s e u , ∆∆∆ kx :

+ ,xxx kkkk ∆+= α1

kkkk ∆+=+

u ,uu α1 (5.24)

,sss kkkk ∆+=+ α1

103

onde requerer-se que, na nova iteração, a função de mérito seja

suficientemente reduzida, i.e., que a função

kkkkkkkkkALAG

)( ),ss,uu,xx(Fαφ µααα ∆+∆+∆+ (5.25)

satisfaça, por exemplo,

=

)()((0) )()(

00φηαφ

φασφαφ′≤

′≤− (5.26)

onde 2

0 ≤≤< ησ (ver l. (1986) para uma prova que estas condições

são satisfeitas).

A escolha do parâmetro de penalidade

1 Gill et a

µ e o algoritmo da Função de Mérito

utilizados neste trabalho são aqueles desenvolvidos por Gill et al (1986) e utilizados

em Melo (1998).

5.5 – Algoritmo de solução

O algoritmo de programação seqüencial quadrático implementado neste

trabalho pode ser estabelecido como:

• Passo Inicial: Fazer φ== kI e k 1

Escolher um ponto inicial viável e valores iniciais para: 0x

000 e x , ,u µλ ∆0 .

• Passo 1: Calcular os valores de

Onde:

kkk2

k b e J ),x(f ,)x(f ∇∇ ,

kkj

kik Ij )x(g

l} ..., E{1,i )x(hJ

∈∇∈∇

= ,

104

kkj

kik Ij )x(g

l}

..., E{1,i )x(h

B∈

∈= ,

• Passo 2: Verificar se ositiva. Se é definida

positiva fazer 2 , caso contrário, perturbar a diagonal principal

até conseguir ção

) é definida px(f k2∇ )x(f k

2∇

)x(fB k∇=

uma aproxima B definida positiva, utilizando o algoritmo

para obter uma aproximação B de Melo(1998).

• Passo 3: Resolver o subproblema quadrático PQ’ utilizando a formulação EQP:

kT

kjkj

Tkiki

TTkkkkk

Ei x)x(h)x(h s.a.

xBxx)x(f)f(x r Minimiza:)v ,u ,x('PQ

∈=∆∇+

∆∆+∆∇+

021

Ij x)x(g)x(g ∈=∆∇+ 0

• Passo 4: Testar os valores encontrados de 1+∆ kx e 1+kλ para verificar se 1+∆ kx é

solução ótima do problema quadrático (5.12). Caso seja, ir ao passo 5.

r restrições ao

conjunto ativo do problema PQ’ (5.14) utilizando o algoritmo do

conjunto ativo de Melo(1998) e voltar ao passo 3.

• Passo 5

Caso contrário, verificar se precisa acrescentar ou retira

kI

: Se 01 =∆ +kx , então é um ponto de K.K.T., faça kx 11 ++ = kku λ e PARE.

Caso contrário, calcule o tamanho do passo α utilizando a função de

mérito Lagrangeano Aumentado (5.22), faça kkk uu −=∆ + λ1 e atualize e

:

kx

ku

11 ++ ∆+= kkk x xx α

11 ++ ∆+= kkk u uu α

105

• Passo 6: Verificar se é viável para o problema original. Caso seja, ir ao

o algoritmo de

viabilidade de Melo (1998) com:

1+kx

passo 7. Caso contrário, corrigir o ponto 1+kx utilizando

11 ++ ∆+= kkk x lamxx .

• Passo 7: Se 01 =−+ kk xx então PARE. Caso contrário, faça e ir ao

passo1.

A resolução do problema

1+= kk

QP ′ no Passo 3 consiste em resolver o sistema de

equações lineares (5.15), como pode ser observado abaixo:

k

k

k

k

k

Tk

b)x(f

vx

* J

JB−

∇−=

∆

+

+

1

1

0, (5.15)

onde:

kkj

kik

kkj

kik

IjEi

, )x(g)x(h

b

IjEi

, )x(g)x(h

J

∈∈

=

∈∈

∇∇

=

Se o problema original for esparso, então o Jacobiano e da aproximação

definida positiva da matriz hessiana do Lagrangeano

kJ

B conseqüentemente também

serão esparsos. Neste caso, o sistema de equações (5.15) será esparso, ou seja,

muitos elementos da matriz 0k

Tk

JJB

serão nulos. Como é preciso resolver o

sistema (5.15) várias vezes em uma iteração do algoritmo, o cálculo efetuado com

os elementos nulos pode comprometer o tempo computacional e a precisão dos

resultados. Neste caso, o sistema poderá ser resolvido utilizando o modelo de

armazenamento e as estratégias de pivotamento desenvolvidas nos capítulos

106

anteriores. O modelo de armazenamento evita cálculos desnecessários com os

elementos nulos, o que irá reduzir consideravelmente o tempo computacional do

algoritmo, enquanto as estratégias de pivotamento irão reduzir o número de

preenchimentos que serão gerados durante a resolução do sistema, o que irá

melhorar a precisão dos resultados.

107

CAPÍTULO VI

os sistemas de equações lineares serão utilizadas matrizes testes das

classe

s matrizes da classe E(n,c) são definidas da seguinte forma:

TESTES E RESULTADOS NUMÉRICOS

Neste capítulo, serão apresentados os resultados numéricos obtidos a partir

da resolução de sistemas de equações lineares com matrizes testes e de problemas

de otimização não lineares simulando problemas de fluxo de potência ótimo.

N

s E(n,c) e D(n,c), apresentada em Zlatev(1991) e descritas a seguir:

A

n ..., 2, 1,i ,4 , ==iia

1-n ..., 2, 1,i 1,11 , =−== ++ iiii aa (6.1)

c-n ..., 2, 1,i ,1 , , =−==+cii aa + ici

seguir, podemos observar o padrão de esparcidade de uma matriz teste da

classe

onde:

• 3≥n

• nc ≤≤1

A

E, com parâmetros n=20 e c=5, ou seja, uma matriz E(20,5). Os elementos

não nulos serão representados por x .

108

⎥⎥⎥⎥

⎥⎥⎥⎥

⎦⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎢⎢

⎢⎢

⎣ 000000000000000000000000000000000

000000000000000000000000000000000000000000000000

000000000000000

000000000000000000000000000

0000000000000000000

xxxxxxx

xxxxxxxx

xxxxxxxxx

xxxxxxxxx

xxxx

As matrizes da classe D(n,c) são definidas da seguinte forma:

⎤

⎢⎢⎡

000000000000000000000000000000

xxxxxxx

⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢

00000000000000000000000000000000000000000000000000000000000000000

xxxxxx

xxxxxxxxx

xxxx

(6.2)

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢

000000000000000000000000000000000000000000000000000000000000000000000000000

xxxxxxxxxx

xxxxxxxxxx

xxxxx

n ..., 2, 1,i ,1 , ==iia

c-n ..., 2, 1,i 1 , =+=+ ia cii

n ..., 2,c-n ,1i 1 , ++−=+=+− cnia cnii

1-c-n ..., 2, 1,i ,1 , =−=++ ia cii (6.3)

n ..., 1,c-n ,i ,1 , +−=−=++− cnia cnii

1,i ,162 , ==++ciia 1-c-n ..., 2,

n ..., c,-n ,1i ,162 , −−==++− cna cnii

i-11 ..., 2, 1,j 10, ..., 2, ,1i ,10011 , ==×=++− ja jini

109

onde:

• 14≥n

• 131 −≤≤ nc

A seguir, podemos observar o padrão de esparcidade de uma matriz teste da

classe

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

000000000000000000000000000000000000000000000000

00000000000000000000000000000000

0000000000000000000000000000000000

0000000000000000000000000000000

000000000000000000000000000

00000000000000000000000

0000000000000000000

xxxxxxxx

xxxxxxxxxxxx

xxxxxx

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

As principais características das matrizes testes das duas classes pode

bservadas na tabela a seguir:

D, com parâmetros n=20 e c=5, ou seja, uma matriz D(20,5):

⎥⎥⎤

⎢⎢⎢⎢⎡

000000000000000

000000

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

⎥⎥

⎦⎢⎢

⎣ 00000000000000000000000000000000xxxx

xxxx

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

)

o

(6.4

m ser

110

Classe Dimensão NZ Menor

Elemento

Maior

Elemento

E(n,c) nxn 225 −− cn 1 4

D(n,c) nxn 554 +n 1 )1 ,1000max( +n

6.5 – Características das Matrizes Testes

Inicialmente, os sistemas serão resolvidos considerando toda a matriz,

inclusive os elementos nulos. Depois, os problemas serão resolvidos simulando o

modelo de armazenamento dinâmico apresentado em Zlatev (1991) e descrito na

eção 3.2, porém não será executado nenhum procedimento de compactação e

reordenação dos dados como, por exemplo, o procedimento de Coleta de Lixo.

Posteriormente, os problemas serão resolvidos utilizando o Modelo de

Armazenamento Proposto neste trabalho.

Em todos os casos anteriores, serão utilizadas matrizes de dimensões de

50x50 até 3000x3000, variando de 50 em 50.

Todas as instâncias criadas serão resolvidas de três formas. Primeiramente

os sistemas serão resolvidos sem a utilização de nenhuma técnica de pivotamento.

Após isto, os sistemas serão resolvidos utilizando técnicas de pivotamento dos

grupos I (Pivotamento a Priori) e II (Pivotamento Markowitz), apresentadas no

capítulo 4.

PO), que serão resolvidos utilizando o

método seqüencial quadrático. Tais problemas serão solucionados utilizando o

modelo de armazenamento padrão (com matrizes) e o modelo de armazenamento

proposto neste trabalho.

S

Serão criados, ainda, problemas de otimização não lineares simulando

problemas de fluxo de potência ótimo (F

Na resolução dos sistemas de equações lineares, serão comparados os

tempos computacionais, as porcentagens de preenchimentos gerados e os erros

111

relativos percentuais obtidos. Na resolução dos problemas de otimização não

lineare

Na resolução dos sistemas lineares com matrizes das Classes D (6.6) e E

ores tempos computacionais.

s, serão comparados somente os tempos computacionais.

O programa foi codificado em Delphi, sendo que os testes foram realizados

em um computador portátil com processador Athlon de 1.4 Ghz, com 256 Mbytes de

memória RAM. As tabelas com os resultados computacionais podem ser

observadas no Anexo.

(6.7), utilizando o modelo padrão, podemos observar que a opção que não usou

estratégias de pivotamento apresentou os menores tempos. Por outro lado, a

estratégia de Markowitz apresentou os mai

Duração da Resolução Matrizes Classe D no Modelo Padrão

00:00:0000:02:5300:05:4600:08:3800:11:3100:14:2400:17:1700:20:10

50 400

750

1100

1450

1800

2150

2500

2850

Dimensão da Matriz (n)

Tem

po

Matrizes Classe D ***SEM PIVOTAMENTO***Matrizes Classe D ***PIVOTAMENTO APRIORI ***Matrizes Classe D ***PIVOTAMENTOMARKOWITZ ***

6.6 – Comparação entre os tempos computacionais das técnicas de pivotamento na

resolução de sistemas lineares com matrizes da Classe D, utilizando o Modelo

Padrão (Tabelas 1, 2 e 3 do Anexo).

112

Duração da Resolução Matrizes Classe E no Modelo Padrão

00:00:0000:02:5300:05:4600:08:3800:11:3100:14:2400:17:1700:20:10

50 400

750

1100

1450

1800

2150

2500

2850


Tem

po

Matrizes Classe E*** SEMPIVOTAMENTO ***Matrizes Classe E*** PIVOTAMENTO APRIORI ***Matrizes Classe E*** PIVOTAMENTOMARKOWITZ ***


resolução de sistemas lineares com matrizes da Classe E, utilizando o Modelo

Padrão (Tabelas 4, 5 e 6 do Anexo).

Na resolução dos sistemas lineares com matrizes das Classes D (6.8) e E

Markowitz apresentou os maiores tempos computacionais.

(6.9), utilizando o Modelo apresentado em Zlatev (sem procedimentos de Coleta de

Lixo), novamente podemos observar que a opção que não usou estratégias de

pivotamento apresentou os menores tempos. Por outro lado, a estratégia de

113

Duração da Resolução Matrizes Classe D no Modelo apresentado em Zlatev sem Garbage Collection

00:00:0000:01:2600:02:5300:04:1900:05:4600:07:1200:08:3800:10:0500:11:31

50 400

750

1100

1450

1800

2150

2500

2850


Tem

po

Matrizes Classe D ***SEM PIVOTAMENTO***Matrizes Classe D ***PIVOTAMENTO APRIORI ***Matrizes Classe D ***PIVOTAMENTOMARKOWITZ ***


resolução de sistemas lineares com matrizes da Classe D, utilizando o Modelo

apresentado em Zlatev, sem usar procedimentos de Coleta de Lixo (Tabelas 7, 8 e 9

do Anexo).

Duração da Resolução Matrizes Classe E no Modelo apresentado em Zlatev sem Garbage Collection

00:07:1200:08:38

00:00:0000:01:26

50 400

750

1100

1450

1800

2150

2500

2850

00:02:5300:04:1900:05:46


Tem

po

Matrizes*** SEM

Classe E

PIVOTAMENTO ***Matrizes Classe E*** PIVOTAMENTO APRIORI ***Matrizes Classe E*** PIVOTAMENTOMARKOWITZ ***


resolução de sistemas de equações lineares com matrizes da Classe E, utilizando o

Modelo apresentado em Zlatev, sem usar procedimentos de Coleta de Lixo (Tabelas

10, 11 e 12 do Anexo).

114

Na resolução dos sistemas lineares com matrizes da Classe D, utilizando o

Modelo Proposto, a opção em que não usou estratégias de pivotamento continuou

apresentando os menores tempos computacionais (6.10), porém a estratégia do

Grupo II (Markowitz) apresentou tempos menores do que a estratégia do Grupo I (a

Priori). Este fato pode ser explicado, pois a estratégia de Markowitz, apesar da

possuir mais cálculos, produziu menos preenchimentos do que a estratégia de

Pivotamento a Priori (6.11).

Duração da Resolução Matrizes Classe D no Modelo Proposto

00:00:0000:43

50 400

750

1100

1450

1800

2150

2500

2850


00:00:01:2600:02:1000:02:53

Tem

00:03:3600:04:1900:05:0200:05:46

po

Matrizes Classe D ***SEM PIVOTAMENTO***Matrizes Classe D ***PIVOTAMENTO APRIORI***Matrizes Classe D ***PIVOTAMENTOMARKOWITZ ***


solução de sistemas lineares com matrizes da Classe D, utilizando o Modelo

Proposto (Tabelas 13, 14 e 15 do Anexo).

re

115

Porcentagem de Fill-in na Resolução de Matrizes Classe D no Modelo Proposto

0.00%2.00%4.00%6.00%8.00%

10.00%12.00%14.00%16.00%

50 350

650

950

1250

1550

1850

2150

2450

2750


Tem

po

Matrizes Classe D ***SEM PIVOTAMENTO***Matrizes Classe D ***PIVOTAMENTO APRIORI***Matrizes Classe D ***PIVOTAMENTOMARKOWITZ ***

6.11 – Comparação entre as Porcentagens de Preenchimentos Gerados pelas

técnicas de pivotamento na resolução de sistemas com matrizes da Classe D,

utilizando o Modelo Proposto (Tabelas 13, 14 e 15 do Anexo).

A resolução dos sistemas lineares com matrizes da Classe D, utilizando o

Model

te no aumento do tempo computacional.

o Proposto, sem utilizar estratégias de Pivotamento apresentou os menores

tempos computacionais (6.10), mas apresentou também, em alguns casos, erros

extremamente altos, alcançando valores de até 510+ (6.12). Neste caso a utilização

de uma técnica de pivotamento é necessária para garantir a precisão dos resultados,

mesmo que isto acarre

116

Erro Relativo Pencentual na Resolução de Matrizes Classe D no Modelo Proposto

0.00E+002.00E+044.00E+046.00E+048.00E+041.00E+051.20E+051.40E+05

50 400

750

1100

1450

1800

2150

2500

2850


Tem

poMatrizes Classe D*** SEMPIVOTAMENTO ***Matrizes Classe D*** PIVOTAMENTO APRIORI***Matrizes Classe D*** PIVOTAMENTOMARKOWITZ ***

6.12 – Comparação entre os Erros Relativos obtidos pelas técnicas de pivotamento

na resolução de sistemas lineares com matrizes da Classe D, utilizando o Modelo

Proposto (Tabelas 13, 14 e 15 do Anexo).

Na resolução dos sistemas lineares com matrizes da Classe E, utilizando o

Model

estes casos aconteceram com matrizes de pequenas

imensões. Na medida que a dimensão da matriz foi aumentando, a porcentagem

e preenchimento diminuiu, porém permaneceu superior às estratégias dos Grupos I

e II (6.14). A precisão dos resultados obtidos nos três casos é satisfatória (6.15).

o Proposto, a opção que não usou estratégias de pivotamento continuou

apresentando os menores tempos computacionais (6.13). As estratégias dos

Grupos I (Pivotamento a Priori) e II (Markowitz) apresentaram tempos praticamente

semelhantes (6.13). A porcentagem de preenchimentos gerados na opção que não

usou estratégias de pivotamento foi relativamente alta em alguns casos, alcançando

valores de até 35% (6.14). Mas isto não chegou a comprometer o tempo

computacional, pois

d

d

117

Duração da Resolução Matrizes Classe E no Modelo Proposto

00:00:0000:00:1700:00:3500:00:5200:01:0900:01:2600:01:4400:02:01

50 400

750

1100

1450

1800

2150

2500

2850


Tem

po

Matrizes Classe E ***SEM PIVOTAMENTO***Matrizes Classe E ***PIVOTAMENTO APRIORI***Matrizes Classe E ***PIVOTAMENTOMARKOWITZ ***


resolução de sistemas de equações lineares com matrizes da Classe E, utilizando o

Modelo Proposto (Tabelas 16, 17 e 18 do Anexo).

Porcentagem de Fill-in na Resolução de Matrizes Classe E no Modelo Proposto

0.00%5.00%

10.00%15.00%20.00%25.00%30.00%35.00%40.00%

50 400

750

1100

1450

1800

2150

2500

2850


Tem

po

Matrizes Classe E*** SEMPIVOTAMENTO ***Matrizes Classe E*** PIVOTAMENTO APRIORI***Matrizes Classe E*** PIVOTAMENTOMARKOWITZ ***

6.14 – Comparação entre as Porcentagens de Preenchimentos Gerados pelas

técnicas de pivotamento na resolução de sistemas de equações lineares com

matrizes da Classe E, utilizando o Modelo Proposto (Tabelas 16, 17 e 18 do Anexo).

118

Erro Relativo (%) na Resolução de Matrizes Classe E no Modelo Proposto

0.00E+00

2.00E-11

4.00E-11

6.00E-11

8.00E-11

1.00E-10

50 400

750

1100

1450

1800

2150

2500

2850


Tem

poMatrizes Classe E*** SEMPIVOTAMENTO ***Matrizes Classe E*** PIVOTAMENTO APRIORI***Matrizes Classe E*** PIVOTAMENTOMARKOWITZ ***

6.15 – Comparação entre os Erros Relativos obtidos pelas técnicas de pivotamento

na resolução de sistemas de equações lineares com matrizes da Classe E, utilizando

o Modelo Proposto (Tabelas 16, 17 e 18 do Anexo).

Comparando os tempos computacionais obtidos na resolução dos sistemas

lineare

mente inferiores ao Modelo Proposto (6.17).

s com matrizes da classe D, sem usar estratégias de Pivotamento, podemos

observar que o Modelo Padrão apresentou os maiores tempos computacionais,

enquanto o Modelo de Zlatev e o Modelo Proposto apresentaram tempos

semelhantes (6.16), sendo que o Modelo de Zlatev apresentou tempos

computacionais ligeira

119

Comparação dos Tempos de Duração Matrizes Classe D *** SEM PIVOTAMENTO ***

00:00:0000:01:2600:02:5300:04:1900:05:4600:07:1200:08:38

50 400

750

1100

1450

1800

2150

2500

2850

dimensão da Matriz (n)

Tem

po

Matriz Classe DModelo Proposto

Matriz Classe DModelo Padrão

Matriz Classe DZlatev sem GarbageCollection

6.16 – Comparação entre os tempos computacionais entre os modelos de

armazenamento na resolução de sistemas de equações lineares com matrizes da

Classe D, sem utilizar técnicas de pivotamento (Tabelas 1, 7 e 13 do Anexo).

Comparação dos Tempos de Duração Matrizes Classe D *** SEM PIVOTAMENTO ***

00:

00:00:17

00:00:22

po

00:00:00

50 400

750

1100

1450

1800

2150

2500

2850

dim

00:00:04

00:00:09

00:13

ensão da Matriz (n)

Tem





Classe D, sem utilizar técnicas de pivotamento, não considerando o Modelo Padrão

(Tabelas 7 e 13 do Anexo).

120


lineares com matrizes da classe D, utilizando estratégia de Pivotamento do Grupo I

(Pivotamento a Priori), podemos observar que o Modelo Padrão novamente

apresentou os maiores tempos computacionais (6.18), enquanto o Modelo de Zlatev

e o Modelo Proposto apresentaram tempos semelhantes (6.19).

Comparação dos Tempos de Duração Matrizes Classe D *** Com Pivotamento a Priori ***

00:00:00

00:02:53

00:05:46

00:08:38

Tem

po

00:11:31

00:14:24

50 400

750

1100

1450

1800

2150

2500

2850







Classe D, utilizando técnicas de pivotamento do Grupo I (Tabelas 2, 8 e 14 do

Anexo).

121

Comparação dos Tempos de Duração Matrizes Classe D *** Com Pivotamento a Priori ***

00:00:0000:00:4300:01:2600:02:1000:02:5300:03:3600:04:1900:05:0200:05:46

50 40 75 110

145

180

250

285

dimensão da Ma (n)

Tem

po

0 0 0 0 0 0 0 0

215

triz





Classe D, utilizando técnicas de pivotamento do Grupo I (Pivotamento a Priori), não

consid

omparando os tempos computacionais obtidos na resolução dos sistemas

lineare

erando o Modelo Padrão (Tabelas 8 e 14 do Anexo).

C

s com matrizes da classe D, utilizando estratégia de Pivotamento do Grupo II

(Pivotamento Markowitz), podemos observar que o Modelo Proposto apresentou os

menores tempos computacionais, seguidos pelo Modelo de Zlatev e pelo Modelo

Padrão (6.20 e 6.21).

122

Comparação dos Tempos de Duração Matrizes Classe D *** Com Pivotamento Markowitz ***

00:00:0000:02:5300:05:4600:08:3800:11:3100:14:2400:17:1700:20:10

50 400

750

1100

1450

1800

2150

2500

2850


Tem

po






Classe D, utilizando técnicas de pivotamento do Grupo II (Tabelas 3, 9 e 15 do

Anexo).

Comparação dos Tempos de Duração Matrizes Classe D *** Com Pivotamento Markowitz ***

00:08:3800:10:0500:11:31


00:00:0000:01:2600:02:5300:04:19

50 400

750

1100

1450

1800

2150

2500

2850


Te

00:05:4600:07:12

mpo


6.21

as de pivotamento do Grupo II (Pivotamento Markowitz),

não considerando o Modelo Padrão (Tabelas 9 e 15 do Anexo).

– Comparação entre os tempos computacionais entre os modelos de


Classe D, utilizando técnic

123


lineares com matrizes da classe E, sem usar estratégias de pivotamento e utilizando

estratégia do Grupo I (a Priori), podemos observar que o Modelo Padrão apresentou

os maiores tempos computacionais, enquanto o Modelo de Zlatev e o Modelo

Proposto apresentaram tempos semelhantes (6.22 e 6.24), sendo que o Modelo de

Proposto apresentou tempos computacionais ligeiramente inferiores ao Modelo de

Zlatev (6.23 e 6.25).

Comparação dos Tempos de Duração Matrizes Classe E *** SEM PIVOTAMENTO ***

00:00:0000:01:2600:02:5300:04:1900:05:4600:07:1200:08:3800:10:05

50 400

750

1100

1450

1800

2150

2500

2850


Tem

po

Matriz Classe EModelo Proposto

Matriz Classe EModelo Padrão

Matriz Classe EZlatev sem GarbageCollection



Classe E, sem utilizar técnicas de pivotamento (Tabelas 4, 10 e 16 do Anexo).

124

Comparação dos Tempos de Duração Matrizes Classe E *** SEM PIVOTAMENTO ***

00:00:00

00:00:09

00:00:17

00:00:26

00:00:35

00:00:43

50 40 75 110

145

180

215

250

285


0 0 0 0 0 0 0 0

Tem

poMatriz Classe EModelo Proposto


arma matrizes da

lasse E, sem utilizar técnicas de pivotamento, não considerando o Modelo Padrão


zenamento na resolução de sistemas de equações lineares com

C

(Tabelas 10 e 16 do Anexo).

Comparação dos Tempos de Duração Matrizes Classe E *** Com Pivotamento a Priori ***

00:00:00

00:02:53

00:05:46

50

Te

00:08:38

400

750

1100

1450

1800

2150

2500

2850

mp

00:11:31

00:14:24

o





.24 – Comparação entre os tempos computacionais entre os modelos de

Classe E, utilizando técnicas de pivotamento do Grupo I (Tabelas 5, 11 e 17 do

nexo).

6


A

125

Comparação dos Tempos de Duração Matrizes Classe E *** Com Pivotamento a Priori ***

00:00:5240

0

750

1100

1450

1800

2150

2500

2850


Te

00:00:0000:00:1700:00:35

5000:01:0900:01:2600:01:4400:02:0100:02:18

mpo




zenamento na resolução de sistemas de equações lineares com

6.25

arma matrizes da

lasse E, utilizando técnicas de pivotamento do Grupo I (Pivotamento a Priori), não


(Pivo resentou os

enores tempos computacionais, seguidos pelo Modelo de Zlatev e pelo Modelo

C

considerando o Modelo Padrão (Tabelas 11 e 17 do Anexo).

lineares com matrizes da classe E, utilizando estratégia de Pivotamento do Grupo II

tamento Markowitz), podemos observar que o Modelo Proposto ap

m

Padrão (6.26 e 6.27).

126

Comparação dos Tempos de DuraE *** Com Pivotamento Ma

ção Matrizes Classe rkowitz ***

00:08:38

2500

2850


Te

00:00:0000:02:5300:05:46

50 400

750

1100

1450

1800

2150

00:11:3100:14:2400:17:1700:20:10

mpo





zenamento na resolução de sistemas de equações lineares com ma

6.26

arma trizes da

lasse E, utilizando técnicas de pivotamento do Grupo II (Tabelas 6, 12 e 18 do

C

Anexo).

Comparação dos Tempos de Duração Matrizes Classe E *** Com Pivotamento Markowitz ***

00:02:5304:19

50 400

750

1100

1450

1800

2150

2500

2850

Te

00:00:05:4600:07:1200:08:38

mpo


Matriz Classe EZlatev sem Garbage

00:00:0000:01:26 Collection


.27 – Comparação entre os tempos computacionais entre os modelos de

Classe E, utilizando técnicas de pivotamento do Grupo II (Pivotamento Markowitz),

ão considerando o Modelo Padrão (Tabelas 12 e 18 do Anexo).

6


n

127

Na resolução dos problemas de otimização não lineares simulando problemas

de FPO, tanto com Função Objetivo Linear (6.28) quanto com Função Objetivo Não

inear (6.29), o Método Seqüencial Quadrático (MSQ) utilizando o Modelo Proposto

Mode

L

apresentou tempos computacionais significantemente inferiores ao MSQ utilizando o

lo Padrão.

Função Objetivo Linear

00:05:46l

00:00:0000:00:4300:01:2600:02:1000:02:53

00:05:02

50 100 150 200 250 300 350

Nº de Barras

Tem

po C

omp

ona

Modelo de

Proposto00:03:3600:04:19

utac

i

Armazenamento

Modelo deArmazenamentoPadrão

6.28 – Comparação dos Tempos Computacionais da Resolução de Problemas de

Otimização simulando problemas de Fluxo de Potência Ótima com Função Objetivo

Linear (Tabelas 19 do Anexo).

Função Objetivo Não Linear

00:00:0000:01:2600:02:5300:04:1900:05:4600:07:1200:08:3800:10:0500:11:31

50 100 150 200 250 300 350

Nº de Barras

Tem

po C

ompu

taci

onal

Modelo deArmazenamentoPropostoModelo deArmazenamentoPadrão

128

.29 – Comparação dos Tempos Computacionais da Resolução de Problemas de

timização simulando problemas de Fluxo de Potência Ótima com Função Objetivo

ão Linear (Tabelas 20 do Anexo).

6

O

N

129

CA V

NC ES O ÕE

Neste t lh sen mos

matrizes esparsas, sendo do r de lineares de

equações atra d todo aus na sian

Foram a os p ime ra d lineares em

um método S e Qua o p es pr e otimização

não lineares s

Os modelos de armazenamento dinâmic tiliz apresentam

como princip ge efin p qua ecessária de

posições ext a arma me el ue dos, durante

os cálculos m ion pre nt exata de

preenchimen u o c nã he da dos cálculos,

sendo feita uma estimativa de posições necessárias. Tal estimativa pode ser super

ou sub dimensionada. Quando estimamos ma es necessárias,

estaremos s a ndo mó putacional. Quando estimamos menos

posições do s ssá s cá om ais rompidos por

falta de espa a óri omp

criados. Ne a od dize a de ento não é

realmente di a ve est lter ma trabalha com

um tamanho pré-dimensionado. Esta característica pode dificultar ou até mesmo

inviabilizar a codificação de certas rotinas computacionais.

PÍTULO II

CO LUSÕ E REC MENDAÇ S

raba o, de volve um modelo de armazenamento dinâmico para

utiliza para a esolução sistemas

vés o mé de G s (Elimi ção Gaus a).

utiliz dos roced ntos pa resolução e sistemas

eqü ncial drátic ara a r olução de oblemas d

espar os.

os que u am vetores

al desvanta m a d ição, a riori, da ntidade n

ras p ra o zena nto dos ementos q serão cria

co putac ais ( enchime os). A quantidade

tos q e serã riados o é con cida antes execução

is posiçõ do que as

obrec rrega a me ria com

que a nece rias, o lculos c putacion serão inter

ço n mem a do c utador para o armazenamento dos elementos

ste c so, p emos r que estrutura armazenam

nâmic , uma z que a não a a o seu ta nho e sim

130

modelo desenvolvido neste trabalho apresenta a vantagem de utilizar uma

estrutura de ma a a in m esta será

inicialmente n da arm

matriz, alterando o seu tamanho durante os cálculos computacionais. A partir do

momento em que um preenchimento for criado, a dimensão da estrutura será

aumentada, enquanto, quando um el nã m rnar nulo, na

forma clássic e ar rcid pr ze a orientada à

computação, d

de sobrecarga desnecessária de memória computacional e principalmente de

interrupção d l co cion um tiva Ao contrário

dos modelos m s, a pç álc tacionais no

modelo prop ó co o c do m ciente para o

armazenamento dos dados necessários. Neste caso, tal computador realmente não

possui recursos físicos para a realização dos cálculos, sendo necessária a

ampliação fís a óri nív

A inclusão de um preenchimento no modelo de armazenamento proposto,

além de evitar a cópia de elementos para o final da estrutura, também apresenta a

vantagem de manter as listas ordenadas, por linha e por colunas, organizadas e

compactas, sem a necessidade de executar qualquer procedimento extra de

ordenação e compactação, como por exemplo, a Coleta de Lixo (Zlatev, 1991).

Desta forma, o armazenamento dos preenchimentos gerados é executado utilizando

procedimentos computacionais bastante simples.

Uma outra característica que pode ser observada é que o preenchimento será

criado em um espaço livre da memória, alterando dinamicamente a dimensão da

estrutura de armazenamento de acordo com a quantidade de dados que precisam

ser armazenados, diferente de estruturas que utilizam vetores que são previamente

dimensionadas com folgas para o armazenamento dos dados que serão criados.

Todas estas características resultam em um ganho significativo no tempo

computacional, uma vez que, evitam-se perdas com procedimentos de compactação

e ordenação da estrutura.

O

ar zen mento re lmente d âmica, u a vez que

dime siona para azenar somente os elementos não nulos da

emento o nulo da atriz ser to

a de xplor a espa ade, ou óximo de ro, na form

a dimensão a estrutura será reduzida. Desta forma, evita-se o risco

os cá culos mputa ais por a estima mal feita.

que utiliza vetore interru ão dos c ulos compu

osto s irá o rrer se omputa r não tiver emória sufi

ica d mem a dispo el.

131

dos bastante satisfatórios, tanto na

resolução de em d s ti zenamento

proposto qua utiliza d d di putacionais,

desenvolvido st balh ra çã lem ização Não

Lineares Esparsos, apesar de não ter sido desenvolvido um algoritmo específico

para tais pro a oti ão. ita o d ento destes

algoritmos, e tur aba pod ra pen esentado.

Os testes numéricos, aplicados às matrizes que exploram o condicionamento

dos elementos (Matrizes da Classe D) e o preenchimento da matriz durante a EG

(Matrizes da Classe E), apresentaram resulta

sist as e equaçõe lineares u lizando o modelo de arma

mnto na ção este e os proce entos com

s ne e tra o, pa a resolu o de Prob as de Otim

blem s de mizaç Acred mos que esenvolvim

m fu os tr lhos, e melho r o desem ho aqui apr

132

REFERÊNCIAS BIBLIOGRÁFICAS

Bazaraa, M.S., Sherali, H.D., Shetty, C.M. (1993) Nonlinear Programming: Theory

and algorithms. 2. ed. New York: John Wiley & Sons, 638p.

Carpentier J. (1962), Contribuition á `L`étude du Dispaching Économique, Bulletin de

la Societe Françoice dos Electriciens, SER-8, Vol. 3, p. 432-447.

Curtis, A. R., Reid J. K. (1971) The solution of large sparse unsymetric systems of

linear equation. J. Inst. Math. Applics., 8:344-353.

Dongarra, J. J., Bunch, J. R., Moler, C. B., Stewart, G. W. (1979) LINPACK: user’s

guide. Philadelphia: Society for Industrial and Applied Mathematics, 320p.

Duff, I. S, Reid, J. K. (1974) A comparation of sparsity ordering for obtaining a pivotal

sequence in Gaussian elimination. J. Inst. Math. Applics., 14: 281-291.

Duff, I. S. (1985) Data structures, algoritms and softwares for sparse matrices. In

Evans, D. J. (ed.) Sparsity and its applications. London: Cambridge University

Press, p. 1-29.

Duff, I. S., Reid, J. K. (1983) The multifrontal solution of indefinite sparse symmentric

linear systems. Trans. on Mathematical Software. 9 : 302-325p.

Duff, I. S., Erisman, A. M., Reid, J. K. (1986) Direct methods for sparse matrices.

London: Oxford University Press, p.

133

Duff, I.S. (1977) MA28: a set of FORTRAN subroutines for sparse unsymetric linear

equations. Tech. Report of Computer Science and Systems Divison. HMSO,

London, Tech Report AERE R8730.

Duff, I.S. (1985) Data Structures, algorithms and software for sparse matrices. In:

Evans, D. J. (eds.) Sparsity and its applications. London: Cambridge University

Press, p. 1-29.

Eldersveld, S.K. (1992) Large Scale Sequential Quadratic Programming Algorithms.

Technical Report of System Optmization Laboratory SOL, Stanford, Califórnia,

SOL 92 (4):82p.

Gill, P.E., Murray, W, Saunders, M.A., Wright, M.H. (1986) Some Theoretical

Properties of an Augmented Lagrangian Merit Funcion, California. System

Optimation Laboratory SOL, Stanford, Califórnia, SOL86 (6): 21p.

Gustavson, F. G., (1972) Some basic techniques for solving sparse systems of linear

equations. In: Rose, J., Willoughby, R. A. (eds.) Sparse Matrices and their

applications. New York: Plenum Press, p. 41-52.

Gustavson, F. G., (1978) Two fast algorithms for sparse matrices: multiplication and

permuted transposition. ACM Trans. Math. Software, 4: 250 – 269.

Jennings, M. (1977) Matrix computations for engineers and scientists. New York:

John Wiley, 346p.

Markowitz, H. M. (1957) The elimination form of the inverse and its applications to

linear programming. Management Sci. , 3: 255-267.

Melo, N.A.F. (1998) Implementação de um algoritmo para o problema de fluxo de

potência ótimo utilizando o método seqüencial quadrático. Tese (Mestrado em

Ciências de Engenharia) – Campos dos Goytacazes – RJ, Universidade

Estadual de Norte Fluminense – UENF, 66 p.

134

Osterby, O., Zlatev, Z. (1983) Direct methods for sparse matrices. Lecture Notes in

Computer Science Nº 157. Berlin: Springer.

Powell, M. J. D. (1983) Variable metric methods for constrained optimization. In:

Bachem, A., Grotschel, M., Korte, B. (eds.) Mathematical Programming: The

State of the Art. New York: Springer-Verlag, p. 288-311.

Reid, J. K. (1977) Solution of linear systems of equations: direct methods general.

In Barker, V. A. (ed) Sparse Matrix Techniques. Lecture Notes In Mathematics

Nº 572. Berlim: Springer, p. 102 – 109.

Reid, J. K. (1984) TRESOLVE, a package for solving large sets of linear finite

element equations. In Engquist, B., Smedsaas, T. (eds.) PDE Softhware:

modules interfaces and systems. Amsterdam: North-Holland, p.1-17.

Reid, J. K. (1986) Sparse matrices. Report Nº CSS 201. Computer Science and

Systems Division, Harwell Laboratory. England.

Rice, J. R., Boisvert, R. F. (1985) Solving elliptic problems using ELLPACK. New

York: Springer-Verlag, 497p.

Rockafellar, R. T. (1973) The multiplier method of Hestenes and Powell applied to

convex programming. J. Optimization Theory and Applications JOTA. 12:555-

562.

Stewart, G. W. (1973) Introduction to matrix computations. New York: Academic

Press, 441p.

Veloso, P. A. S., Santos, C. S., Furtado, A. L., Azeredo, P. A. (1984) Estrutura de

Dados. 2. ed. Rio de Janeiro: Campus, 228p.

Wesseling, P. (1982) Theorical and practical aspects of a multigrid method. SIAM J.

Sci. Statist. Comput. 3: 387-407.

135

Zlatev, Z., Wasniewski, J., Schaumburg, K. (1981) Y12M – solution of large and

sparse systems of linear algebraic systems. Lecture Notes in Computer

Science Nº 121. Berlim: Springer.

Zlatev, Z. (1991) Computational methods for general sparse matrices. Dordrecht-

Boston-London: KLUWER Academic Publishers, 328p.

Zlatev, Z., Wasniewski, J., Schaumburg, K. (1981) Y12M – solution of large and

sparse systems of linear algebric systems. Berlin-Heidelberg-New York:

Springer-Verlag, 128p.

Wood, Steve (1987) Turbo Pascal: guia do usuário. São Paulo: McGraw-Hill, 249p.

136

ANEXOS

137

Tabela 1 - Resultados obtidos na resolução de sistemas de equações lineares com

matrizes da classe D, utilizando o Modelo Padrão (com matrizes), sem técnicas de

Pivotamento.

N C Fill-in Fill-In (%) DURAÇÃO Erro

Relativo(%) 50 12 305 12.20% 00:00:00 2.36E-10 100 25 712 7.12% 00:00:00 7.23E-06 150 37 1202 5.34% 00:00:01 1.20E-07 200 50 1412 3.53% 00:00:00 3.02E-04 250 62 2102 3.36% 00:00:00 1.12E-05 300 75 2112 2.35% 00:00:01 2.40E-03 350 87 3002 2.45% 00:00:00 5.38E-05 400 100 2812 1.76% 00:00:01 1.59E-02 450 112 3902 1.93% 00:00:01 1.43E-05 500 125 3512 1.40% 00:00:02 3.08E-02 550 137 4802 1.59% 00:00:03 2.03E-05 600 150 4212 1.17% 00:00:04 1.72E-01 650 162 5702 1.35% 00:00:05 8.95E-04 700 175 4912 1.00% 00:00:05 1.10E-01 750 187 6602 1.17% 00:00:08 1.15E-05 800 200 5612 0.88% 00:00:08 7.93E-02 850 212 7502 1.04% 00:00:10 6.71E-06 900 225 6312 0.78% 00:00:12 3.28E-01 950 237 8402 0.93% 00:00:15 2.95E-04 1000 250 7012 0.70% 00:00:16 5.86E-01 1050 262 9302 0.84% 00:00:19 6.94E-05 1100 275 7712 0.64% 00:00:22 9.88E-01 1150 287 10202 0.77% 00:00:25 6.95E-05 1200 300 8412 0.58% 00:00:28 4.75E+00 1250 312 11102 0.71% 00:00:32 8.51E-06 1300 325 9112 0.54% 00:00:36 8.02E-01 1350 337 12002 0.66% 00:00:40 5.87E-05 1400 350 9812 0.50% 00:00:45 6.16E+00 1450 362 12902 0.61% 00:00:49 1.21E-05 1500 375 10512 0.47% 00:00:59 2.11E+01 1550 387 13802 0.57% 00:01:04 4.33E-05 1600 400 11212 0.44% 00:01:14 1.29E+01 1650 412 14702 0.54% 00:01:21 1.43E-04 1700 425 11912 0.41% 00:01:27 9.57E+00 1750 437 15602 0.51% 00:01:37 2.14E-05 1800 450 12612 0.39% 00:01:41 2.39E+01 1850 462 16502 0.48% 00:01:55 3.15E-04 1900 475 13312 0.37% 00:02:05 1.30E+02 1950 487 17402 0.46% 00:02:13 1.78E-03 2000 500 14012 0.35% 00:02:22 1.50E+02

138


Relativo(%) 2050 512 18302 0.44% 00:02:38 1.01E-04 2100 525 14712 0.33% 00:02:45 4.83E+01 2150 537 19202 0.42% 00:03:03 7.38E-04 2200 550 15412 0.32% 00:03:10 9.11E+01 2250 562 20102 0.40% 00:03:29 1.75E-04 2300 575 16112 0.30% 00:03:39 4.70E+02 2350 587 21002 0.38% 00:04:05 2.77E-04 2400 600 16812 0.29% 00:04:12 7.48E+01 2450 612 21902 0.36% 00:04:22 4.86E-04 2500 625 17512 0.28% 00:04:44 1.59E+02 2550 637 22802 0.35% 00:05:01 1.75E-04 2600 650 18212 0.27% 00:05:18 1.30E+03 2650 662 23702 0.34% 00:05:36 2.94E-03 2700 675 18912 0.26% 00:05:54 3.68E+02 2750 687 24602 0.33% 00:06:17 1.67E-04 2800 700 19612 0.25% 00:06:35 4.38E+02 2850 712 25502 0.31% 00:06:57 3.26E-04 2900 725 20312 0.24% 00:07:18 1.73E+03 2950 737 26402 0.30% 00:07:42 3.82E-04 3000 750 21012 0.23% 00:08:03 2.48E+02

139


matrizes da classe D, utilizando o Modelo Padrão (com matrizes), com técnicas de

Pivotamento do Grupo I (Pivotamento a Priori).


Relativo(%) 50 12 402 16.08% 00:00:00 1.29E-14 100 25 966 9.66% 00:00:00 3.55E-12 150 37 1509 6.71% 00:00:00 1.26E-13 200 50 2196 5.49% 00:00:00 8.41E-13 250 62 2895 4.63% 00:00:00 6.14E-13 300 75 3289 3.65% 00:00:01 8.50E-12 350 87 4215 3.44% 00:00:01 3.05E-13 400 100 4411 2.76% 00:00:02 7.58E-13 450 112 4857 2.40% 00:00:03 5.52E-13 500 125 5907 2.36% 00:00:03 2.22E-12 550 137 5381 1.78% 00:00:06 1.17E-13 600 150 7188 2.00% 00:00:06 1.10E-12 650 162 6557 1.55% 00:00:08 5.52E-14 700 175 7780 1.59% 00:00:11 3.00E-12 750 187 7070 1.26% 00:00:13 7.46E-13 800 200 8218 1.28% 00:00:15 1.94E-12 850 212 7542 1.04% 00:00:18 1.12E-13 900 225 8907 1.10% 00:00:22 5.35E-12 950 237 8196 0.91% 00:00:29 2.30E-13 1000 250 9933 0.99% 00:00:33 8.52E-13 1050 262 8906 0.81% 00:00:37 1.30E-12 1100 275 11266 0.93% 00:00:38 2.92E-12 1150 287 9448 0.71% 00:00:45 4.35E-13 1200 300 11524 0.80% 00:00:50 9.83E-13 1250 312 10703 0.68% 00:01:01 6.83E-13 1300 325 12167 0.72% 00:01:04 3.40E-12 1350 337 11403 0.63% 00:01:11 1.68E-14 1400 350 13089 0.67% 00:01:19 1.19E-14 1450 362 11886 0.57% 00:01:29 1.40E-14 1500 375 14222 0.63% 00:01:37 2.18E-13 1550 387 12438 0.52% 00:01:48 1.74E-12 1600 400 14898 0.58% 00:01:58 2.80E-14 1650 412 13388 0.49% 00:02:14 5.34E-13 1700 425 15398 0.53% 00:02:22 5.44E-12 1750 437 14094 0.46% 00:02:35 2.67E-14 1800 450 16346 0.50% 00:02:48 8.51E-14 1850 462 14802 0.43% 00:03:03 3.49E-13 1900 475 16986 0.47% 00:03:17 2.40E-13 1950 487 15579 0.41% 00:03:34 1.51E-12 2000 500 17817 0.45% 00:03:50 1.51E-13

140


Relativo(%) 2050 512 16516 0.39% 00:04:08 8.75E-13 2100 525 18208 0.41% 00:04:26 4.16E-13 2150 537 17191 0.37% 00:04:51 3.22E-15 2200 550 19525 0.40% 00:05:13 1.77E-12 2250 562 17738 0.35% 00:05:27 3.24E-13 2300 575 19966 0.38% 00:05:54 2.51E-12 2350 587 18599 0.34% 00:06:47 5.12E-15 2400 600 20946 0.36% 00:06:58 1.62E-13 2450 612 19321 0.32% 00:06:49 1.86E-13 2500 625 21946 0.35% 00:07:54 3.16E-12 2550 637 19788 0.30% 00:08:41 1.21E-13 2600 650 22602 0.33% 00:08:54 1.02E-12 2650 662 20759 0.30% 00:08:26 3.87E-13 2700 675 23321 0.32% 00:08:54 3.61E-12 2750 687 21461 0.28% 00:10:07 2.73E-13 2800 700 24281 0.31% 00:10:37 7.60E-15 2850 712 21981 0.27% 00:11:17 1.41E-12 2900 725 24692 0.29% 00:11:41 5.97E-12 2950 737 22635 0.26% 00:12:20 1.35E-12 3000 750 25283 0.28% 00:13:38 1.17E-14

141


matrizes da classe D, utilizando o Modelo Padrão (com matrizes), com técnicas de

Pivotamento do Grupo II (Pivotamento Markowitz).


Relativo(%) 50 12 370 14.80% 00:00:00 7.93E-10 100 25 1029 10.29% 00:00:00 1.78E-06 150 37 1837 8.16% 00:00:00 7.57E+04 200 50 2491 6.23% 00:00:00 3.30E-02 250 62 3057 4.89% 00:00:01 3.69E-08 300 75 3607 4.01% 00:00:01 1.29E-07 350 87 4317 3.52% 00:00:02 6.57E-07 400 100 4287 2.68% 00:00:03 1.24E-07 450 112 4653 2.30% 00:00:04 9.76E-12 500 125 5045 2.02% 00:00:06 5.84E-06 550 137 5732 1.89% 00:00:07 1.57E+02 600 150 6187 1.72% 00:00:10 1.82E-04 650 162 6876 1.63% 00:00:13 2.25E-05 700 175 8753 1.79% 00:00:15 5.28E+00 750 187 10398 1.85% 00:00:18 2.28E-13 800 200 13921 2.18% 00:00:22 2.61E-05 850 212 16694 2.31% 00:00:26 3.70E-12 900 225 22110 2.73% 00:00:31 1.48E-06 950 237 25444 2.82% 00:00:36 4.68E-04 1000 250 33839 3.38% 00:00:42 1.65E-04 1050 262 36716 3.33% 00:00:48 1.22E-12 1100 275 50757 4.19% 00:00:55 2.26E+12 1150 287 50482 3.82% 00:01:03 1.16E-10 1200 300 66295 4.60% 00:01:11 2.36E+00 1250 312 67195 4.30% 00:01:19 3.57E-12 1300 325 87760 5.19% 00:01:30 7.47E+03 1350 337 86293 4.73% 00:01:40 1.14E-12 1400 350 111405 5.68% 00:01:55 2.08E+01 1450 362 106792 5.08% 00:02:03 1.70E-10 1500 375 138691 6.16% 00:02:20 5.93E+00 1550 387 129566 5.39% 00:02:33 2.18E-13 1600 400 170141 6.65% 00:02:44 2.01E+00 1650 412 155681 5.72% 00:03:03 6.89E-13 1700 425 201508 6.97% 00:03:22 3.61E+11 1750 437 184216 6.02% 00:03:55 2.99E-11 1800 450 241837 7.46% 00:03:57 1.04E-04 1850 462 215271 6.29% 00:04:14 2.84E-02 1900 475 276869 7.67% 00:04:42 1.63E-09 1950 487 249103 6.55% 00:05:00 6.74E-07 2000 500 318244 7.96% 00:05:23 1.66E-13

142


Relativo(%) 2050 512 282918 6.73% 00:05:42 1.07E-04 2100 525 378174 8.58% 00:06:11 1.52E+04 2150 537 336297 7.28% 00:06:34 1.35E+08 2200 550 409877 8.47% 00:07:07 1.40E-06 2250 562 362985 7.17% 00:07:47 1.33E-07 2300 575 459488 8.69% 00:08:19 1.09E-07 2350 587 403142 7.30% 00:08:34 7.12E-05 2400 600 508169 8.82% 00:09:01 6.71E-06 2450 612 452497 7.54% 00:09:44 1.88E-09 2500 625 579957 9.28% 00:10:10 2.17E+02 2550 637 597124 9.18% 00:10:46 2.61E+04 2600 650 624159 9.23% 00:11:25 3.34E-06 2650 662 556515 7.92% 00:11:55 2.92E-13 2700 675 687677 9.43% 00:12:37 3.29E-04 2750 687 613654 8.11% 00:13:12 4.08E-09 2800 700 772944 9.86% 00:14:03 2.41E+00 2850 712 674216 8.30% 00:14:44 1.92E-08 2900 725 812422 9.66% 00:15:29 1.63E-04 2950 737 720716 8.28% 00:16:05 1.31E-11 3000 750 1075046 11.94% 00:17:07 1.11E+03

143


matrizes da classe E, utilizando o Modelo Padrão (com matrizes), sem técnicas de

Pivotamento.



144



145


matrizes da classe E, utilizando o Modelo Padrão (com matrizes), com técnicas de

Pivotamento do Grupo I (Pivotamento a Priori).



146



147


matrizes da classe E, utilizando o Modelo Padrão (com matrizes), com técnicas de

Pivotamento do Grupo II (Pivotamento Markowitz).


Relativo(%) 50 12 376 15.04% 00:00:00 4.67E-12 100 25 1012 10.12% 00:00:00 1.40E-07 150 37 1663 7.39% 00:00:00 1.24E-11 200 50 1673 4.18% 00:00:00 8.64E-03 250 62 2824 4.52% 00:00:01 5.50E-09 300 75 3465 3.85% 00:00:01 1.28E-08 350 87 4419 3.61% 00:00:02 5.97E-14 400 100 4697 2.94% 00:00:03 1.11E-11 450 112 5351 2.64% 00:00:04 9.44E-04 500 125 6125 2.45% 00:00:06 2.75E-06 550 137 6872 2.27% 00:00:08 7.98E-10 600 150 5224 1.45% 00:00:10 1.57E-13 650 162 8136 1.93% 00:00:12 4.56E+00 700 175 10118 2.06% 00:00:16 2.57E-08 750 187 10040 1.78% 00:00:20 8.48E-12 800 200 10745 1.68% 00:00:26 1.86E+01 850 212 10957 1.52% 00:00:31 8.85E+08 900 225 11455 1.41% 00:00:38 2.44E+01 950 237 13392 1.48% 00:00:42 6.28E+05 1000 250 8742 0.87% 00:00:45 9.29E-14 1050 262 12129 1.10% 00:00:53 3.71E-12 1100 275 13645 1.13% 00:01:06 6.38E-11 1150 287 14468 1.09% 00:01:19 1.79E-11 1200 300 14701 1.02% 00:01:27 2.59E-12 1250 312 14177 0.91% 00:01:27 1.33E-12 1300 325 16225 0.96% 00:01:38 2.79E-13 1350 337 15412 0.85% 00:01:49 9.93E-12 1400 350 11561 0.59% 00:02:01 5.71E-13 1450 362 16750 0.80% 00:02:14 2.05E-07 1500 375 18625 0.83% 00:02:28 5.87E+05 1550 387 19536 0.81% 00:02:43 2.90E-11 1600 400 19779 0.77% 00:03:00 2.28E-12 1650 412 18516 0.68% 00:03:32 1.37E-11 1700 425 20622 0.71% 00:03:42 9.52E+04 1750 437 21782 0.71% 00:04:05 2.38E-02 1800 450 15705 0.48% 00:04:22 4.35E-15 1850 462 23167 0.68% 00:04:45 3.26E+00 1900 475 24132 0.67% 00:05:11 1.96E+05 1950 487 24947 0.66% 00:05:43 1.17E+00 2000 500 25928 0.65% 00:06:02 4.68E-12

148


Relativo(%) 2050 512 25261 0.60% 00:06:34 1.28E+03 2100 525 23835 0.54% 00:07:10 2.85E-12 2150 537 25541 0.55% 00:07:38 2.56E-10 2200 550 19146 0.40% 00:08:09 1.59E-13 2250 562 27918 0.55% 00:09:22 1.50E+05 2300 575 29137 0.55% 00:09:27 1.31E-11 2350 587 29676 0.54% 00:10:03 2.68E+01 2400 600 31168 0.54% 00:10:38 2.24E-04 2450 612 30127 0.50% 00:11:52 4.92E-03 2500 625 28223 0.45% 00:12:17 8.98E-13 2550 637 33072 0.51% 00:13:04 4.42E-03 2600 650 21357 0.32% 00:14:14 7.55E-13 2650 662 31122 0.44% 00:13:45 2.43E-03 2700 675 33849 0.46% 00:13:43 1.23E-12 2750 687 34796 0.46% 00:14:37 4.46E-10 2800 700 34972 0.45% 00:15:28 3.50E-12 2850 712 31950 0.39% 00:14:14 4.84E-11 2900 725 37398 0.44% 00:16:12 4.49E-12 2950 737 32925 0.38% 00:17:28 1.01E-12 3000 750 26117 0.29% 00:18:40 1.54E-14

149


matrizes da classe D, utilizando o Modelo apresentado em Zlatev (sem procedimento

de Coleta de Lixo), sem técnicas de Pivotamento.

N C Fill-in

Fill-In (%) DURAÇÃO Erro

Relativo(%) 50 12 305 12.20% 00:00:00 2.36E-10 100 25 712 7.12% 00:00:00 7.23E-06 150 37 1202 5.34% 00:00:00 1.20E-07 200 50 1412 3.53% 00:00:00 3.02E-04 250 62 2102 3.36% 00:00:00 1.12E-05 300 75 2112 2.35% 00:00:00 2.40E-03 350 87 3002 2.45% 00:00:00 5.38E-05 400 100 2812 1.76% 00:00:00 1.59E-02 450 112 3902 1.93% 00:00:01 1.43E-05 500 125 3512 1.40% 00:00:00 3.08E-02 550 137 4802 1.59% 00:00:00 2.03E-05 600 150 4212 1.17% 00:00:00 1.72E-01 650 162 5702 1.35% 00:00:00 8.95E-04 700 175 4912 1.00% 00:00:00 1.10E-01 750 187 6602 1.17% 00:00:01 1.15E-05 800 200 5612 0.88% 00:00:00 7.93E-02 850 212 7502 1.04% 00:00:00 6.71E-06 900 225 6312 0.78% 00:00:01 3.28E-01 950 237 8402 0.93% 00:00:00 2.95E-04 1000 250 7012 0.70% 00:00:00 5.86E-01 1050 262 9302 0.84% 00:00:01 6.94E-05 1100 275 7712 0.64% 00:00:00 9.88E-01 1150 287 10202 0.77% 00:00:01 6.95E-05 1200 300 8412 0.58% 00:00:01 4.75E+00 1250 312 11102 0.71% 00:00:00 8.51E-06 1300 325 9112 0.54% 00:00:00 8.02E-01 1350 337 12002 0.66% 00:00:00 5.87E-05 1400 350 9812 0.50% 00:00:01 6.16E+00 1450 362 12902 0.61% 00:00:01 1.21E-05 1500 375 10512 0.47% 00:00:01 2.11E+01 1550 387 13802 0.57% 00:00:01 4.33E-05 1600 400 11212 0.44% 00:00:01 1.29E+01 1650 412 14702 0.54% 00:00:01 1.43E-04 1700 425 11912 0.41% 00:00:01 9.57E+00 1750 437 15602 0.51% 00:00:01 2.14E-05 1800 450 12612 0.39% 00:00:01 2.39E+01 1850 462 16502 0.48% 00:00:02 3.15E-04 1900 475 13312 0.37% 00:00:01 1.30E+02 1950 487 17402 0.46% 00:00:01 1.78E-03 2000 500 14012 0.35% 00:00:02 1.50E+02

150

N C Fill-in



151



de Coleta de Lixo), com técnicas de Pivotamento do Grupo I (Pivotamento a Priori).

N C Fill-in



152

N C Fill-in



153



de Coleta de Lixo), com técnicas de Pivotamento do Grupo II (Pivotamento

Markowitz).


Relativo(%) 50 12 370 14.80% 00:00:00 7.93E-10 100 25 1029 10.29% 00:00:00 1.78E-06 150 37 1837 8.16% 00:00:00 7.57E+04 200 50 2491 6.23% 00:00:00 3.30E-02 250 62 3057 4.89% 00:00:00 3.69E-08 300 75 3607 4.01% 00:00:00 1.29E-07 350 87 4317 3.52% 00:00:01 6.57E-07 400 100 4287 2.68% 00:00:01 1.24E-07 450 112 4653 2.30% 00:00:02 9.76E-12 500 125 5045 2.02% 00:00:03 5.84E-06 550 137 5732 1.89% 00:00:03 1.57E+02 600 150 6187 1.72% 00:00:04 1.82E-04 650 162 6876 1.63% 00:00:06 2.25E-05 700 175 8753 1.79% 00:00:07 5.28E+00 750 187 10398 1.85% 00:00:08 2.28E-13 800 200 13921 2.18% 00:00:10 2.61E-05 850 212 16694 2.31% 00:00:16 3.70E-12 900 225 22110 2.73% 00:00:14 1.48E-06 950 237 25444 2.82% 00:00:16 4.68E-04 1000 250 33839 3.38% 00:00:20 1.65E-04 1050 262 36716 3.33% 00:00:26 1.22E-12 1100 275 50757 4.19% 00:00:26 2.26E+12 1150 287 50482 3.82% 00:00:34 1.16E-10 1200 300 66295 4.60% 00:00:34 2.36E+00 1250 312 67195 4.30% 00:00:45 3.57E-12 1300 325 87760 5.19% 00:00:44 7.47E+03 1350 337 86293 4.73% 00:01:04 1.14E-12 1400 350 111405 5.68% 00:01:16 2.08E+01 1450 362 106792 5.08% 00:01:19 1.70E-10 1500 375 138691 6.16% 00:01:39 5.93E+00 1550 387 129566 5.39% 00:01:54 2.18E-13 1600 400 170141 6.65% 00:01:53 2.01E+00 1650 412 155681 5.72% 00:02:07 6.89E-13 1700 425 201508 6.97% 00:02:11 3.61E+11 1750 437 184216 6.02% 00:02:06 2.99E-11 1800 450 241837 7.46% 00:02:03 1.04E-04 1850 462 215271 6.29% 00:02:15 2.84E-02 1900 475 276869 7.67% 00:02:25 1.63E-09 1950 487 249103 6.55% 00:02:35 6.74E-07 2000 500 318244 7.96% 00:02:50 1.66E-13

154


Relativo(%) 2050 512 282918 6.73% 00:03:00 1.07E-04 2100 525 378174 8.58% 00:03:18 1.52E+04 2150 537 336297 7.28% 00:03:28 1.35E+08 2200 550 409877 8.47% 00:03:47 1.40E-06 2250 562 362985 7.17% 00:03:58 1.33E-07 2300 575 459488 8.69% 00:04:19 1.09E-07 2350 587 403142 7.30% 00:04:30 7.12E-05 2400 600 508169 8.82% 00:04:59 6.71E-06 2450 612 452497 7.54% 00:05:08 1.88E-09 2500 625 579957 9.28% 00:05:40 2.17E+02 2550 637 597124 9.18% 00:06:01 2.61E+04 2600 650 624159 9.23% 00:06:21 3.34E-06 2650 662 556515 7.92% 00:06:35 2.92E-13 2700 675 687677 9.43% 00:07:06 3.29E-04 2750 687 613654 8.11% 00:07:22 4.08E-09 2800 700 772944 9.86% 00:07:59 2.41E+00 2850 712 674216 8.30% 00:08:13 1.92E-08 2900 725 812422 9.66% 00:08:53 1.63E-04 2950 737 720716 8.28% 00:09:05 1.31E-11 3000 750 1075046 11.94% 00:10:11 1.11E+03

155


matrizes da classe E, utilizando o Modelo apresentado em Zlatev (sem procedimento

de Coleta de Lixo), sem técnicas de Pivotamento.

N C Fill-in



156

N C Fill-in



157



de Coleta de Lixo), com técnicas de Pivotamento do Grupo I (Pivotamento a Priori).

N C Fill-in



158

N C Fill-in



159



de Coleta de Lixo), com técnicas de Pivotamento do Grupo II (Pivotamento

Markowitz).

N C Fill-in


Relativo(%) 50 12 376 15.04% 00:00:00 4.67E-12 100 25 1012 10.12% 00:00:00 1.40E-07 150 37 1663 7.39% 00:00:00 1.24E-11 200 50 1673 4.18% 00:00:00 8.64E-03 250 62 2824 4.52% 00:00:00 5.50E-09 300 75 3465 3.85% 00:00:01 1.28E-08 350 87 4419 3.61% 00:00:01 5.97E-14 400 100 4697 2.94% 00:00:01 1.11E-11 450 112 5351 2.64% 00:00:02 9.44E-04 500 125 6125 2.45% 00:00:03 2.75E-06 550 137 6872 2.27% 00:00:03 7.98E-10 600 150 5224 1.45% 00:00:05 1.57E-13 650 162 8136 1.93% 00:00:05 4.56E+00 700 175 10118 2.06% 00:00:07 2.57E-08 750 187 10040 1.78% 00:00:09 8.48E-12 800 200 10745 1.68% 00:00:10 1.86E+01 850 212 10957 1.52% 00:00:12 8.85E+08 900 225 11455 1.41% 00:00:15 2.44E+01 950 237 13392 1.48% 00:00:17 6.28E+05 1000 250 8742 0.87% 00:00:19 9.29E-14 1050 262 12129 1.10% 00:00:23 3.71E-12 1100 275 13645 1.13% 00:00:26 6.38E-11 1150 287 14468 1.09% 00:00:29 1.79E-11 1200 300 14701 1.02% 00:00:33 2.59E-12 1250 312 14177 0.91% 00:00:37 1.33E-12 1300 325 16225 0.96% 00:00:42 2.79E-13 1350 337 15412 0.85% 00:00:47 9.93E-12 1400 350 11561 0.59% 00:00:51 5.71E-13 1450 362 16750 0.80% 00:00:58 2.05E-07 1500 375 18625 0.83% 00:01:04 5.87E+05 1550 387 19536 0.81% 00:01:10 2.90E-11 1600 400 19779 0.77% 00:01:17 2.28E-12 1650 412 18516 0.68% 00:01:25 1.37E-11 1700 425 20622 0.71% 00:01:33 9.52E+04 1750 437 21782 0.71% 00:01:41 2.38E-02 1800 450 15705 0.48% 00:01:49 4.35E-15 1850 462 23167 0.68% 00:01:59 3.26E+00 1900 475 24132 0.67% 00:02:08 1.96E+05 1950 487 24947 0.66% 00:02:19 1.17E+00 2000 500 25928 0.65% 00:02:29 4.68E-12

160

N C Fill-in


Relativo(%) 2050 512 25261 0.60% 00:02:41 1.28E+03 2100 525 23835 0.54% 00:02:53 2.85E-12 2150 537 25541 0.55% 00:03:04 2.56E-10 2200 550 19146 0.40% 00:03:16 1.59E-13 2250 562 27918 0.55% 00:03:31 1.50E+05 2300 575 29137 0.55% 00:03:44 1.31E-11 2350 587 29676 0.54% 00:03:59 2.68E+01 2400 600 31168 0.54% 00:04:15 2.24E-04 2450 612 30127 0.50% 00:04:31 4.92E-03 2500 625 28223 0.45% 00:04:49 8.98E-13 2550 637 33072 0.51% 00:05:05 4.42E-03 2600 650 21357 0.32% 00:05:22 7.55E-13 2650 662 31122 0.44% 00:05:44 2.43E-03 2700 675 33849 0.46% 00:06:04 1.23E-12 2750 687 34796 0.46% 00:06:25 4.46E-10 2800 700 34972 0.45% 00:06:44 3.50E-12 2850 712 31950 0.39% 00:07:07 4.84E-11 2900 725 37398 0.44% 00:07:28 4.49E-12 2950 737 32925 0.38% 00:07:54 1.01E-12 3000 750 26117 0.29% 00:08:12 1.54E-14

161


matrizes da classe D, utilizando o Modelo Proposto, sem técnicas de Pivotamento.

N C Fill-in Fill-in (%) DURAÇÃO Erro

Relativo(%) 50 12 305 12.20% 00:00:00 6.12E-08 100 25 712 7.12% 00:00:00 3.20E-03 150 37 1202 5.34% 00:00:00 2.92E-05 200 50 1412 3.53% 00:00:00 3.86E-02 250 62 2102 3.36% 00:00:00 4.10E-04 300 75 2112 2.35% 00:00:00 1.34E-01 350 87 3002 2.45% 00:00:00 1.01E-02 400 100 2812 1.76% 00:00:00 1.50E+00 450 112 3902 1.93% 00:00:00 1.52E-03 500 125 3512 1.40% 00:00:01 2.13E+00 550 137 4802 1.59% 00:00:00 1.47E-03 600 150 4212 1.17% 00:00:00 3.19E+01 650 162 5702 1.35% 00:00:00 2.48E-02 700 175 4912 1.00% 00:00:01 4.83E+01 750 187 6602 1.17% 00:00:00 3.20E-04 800 200 5612 0.88% 00:00:01 2.74E+01 850 212 7502 1.04% 00:00:00 5.68E-04 900 225 6312 0.78% 00:00:01 6.38E+01 950 237 8402 0.93% 00:00:01 1.16E-03 1000 250 7012 0.70% 00:00:00 4.03E+03 1050 262 9302 0.84% 00:00:01 1.34E-03 1100 275 7712 0.64% 00:00:01 6.38E+01 1150 287 10202 0.77% 00:00:02 2.16E-03 1200 300 8412 0.58% 00:00:01 7.32E+01 1250 312 11102 0.71% 00:00:01 4.99E-03 1300 325 9112 0.54% 00:00:01 8.16E+01 1350 337 12002 0.66% 00:00:02 2.78E-02 1400 350 9812 0.50% 00:00:01 5.13E+02 1450 362 12902 0.61% 00:00:02 9.17E-02 1500 375 10512 0.47% 00:00:02 9.18E+01 1550 387 13802 0.57% 00:00:03 2.85E-02 1600 400 11212 0.44% 00:00:03 2.02E+03 1650 412 14702 0.54% 00:00:03 5.56E-03 1700 425 11912 0.41% 00:00:03 1.22E+02 1750 437 15602 0.51% 00:00:03 3.83E-03 1800 450 12612 0.39% 00:00:03 5.21E+02 1850 462 16502 0.48% 00:00:05 6.84E-02 1900 475 13312 0.37% 00:00:04 1.66E+03 1950 487 17402 0.46% 00:00:06 2.73E-01 2000 500 14012 0.35% 00:00:06 7.30E+03

162



163


matrizes da classe D, utilizando o Modelo Proposto, com técnicas de Pivotamento do

Grupo I (Pivotamento a Priori).



164



165


matrizes da classe D, utilizando o Modelo Proposto, com técnicas de Pivotamento do

Grupo II (Pivotamento Markowitz).



166



167


matrizes da classe E, utilizando o Modelo Proposto, sem técnicas de Pivotamento.

N C Fill-in

Fill-in (%) DURAÇÃO Erro


168

N C Fill-in



169


matrizes da classe E, utilizando o Modelo Proposto, com técnicas de Pivotamento do

Grupo I (Pivotamento a Priori).

N C Fill-in


Relativo(%) 50 12 322 12.88% 00:00:00 3.64E-14 100 25 705 7.05% 00:00:00 5.46E-14 150 37 1162 5.16% 00:00:00 1.52E-12 200 50 1493 3.73% 00:00:00 4.55E-15 250 62 1961 3.14% 00:00:00 3.97E-13 300 75 2383 2.65% 00:00:00 3.03E-15 350 87 2837 2.32% 00:00:00 3.27E-12 400 100 3109 1.94% 00:00:01 6.37E-14 450 112 3288 1.62% 00:00:00 4.04E-14 500 125 3981 1.59% 00:00:01 1.82E-15 550 137 4432 1.47% 00:00:00 1.65E-15 600 150 4625 1.28% 00:00:01 3.03E-15 650 162 4688 1.11% 00:00:02 1.54E-14 700 175 5210 1.06% 00:00:01 1.10E-13 750 187 6354 1.13% 00:00:02 0.00E+00 800 200 5684 0.89% 00:00:02 2.16E-14 850 212 6916 0.96% 00:00:02 2.44E-12 900 225 6267 0.77% 00:00:03 1.01E-15 950 237 7022 0.78% 00:00:03 7.18E-14 1000 250 7405 0.74% 00:00:04 2.00E-14 1050 262 7775 0.71% 00:00:04 9.75E-12 1100 275 8421 0.70% 00:00:04 8.27E-16 1150 287 8942 0.68% 00:00:05 0.00E+00 1200 300 8554 0.59% 00:00:06 7.41E-12 1250 312 9569 0.61% 00:00:07 4.07E-11 1300 325 9632 0.57% 00:00:08 2.24E-12 1350 337 9117 0.50% 00:00:08 1.35E-15 1400 350 10165 0.52% 00:00:10 1.30E-15 1450 362 11278 0.54% 00:00:10 8.17E-13 1500 375 10957 0.49% 00:00:12 1.18E-13 1550 387 10718 0.45% 00:00:13 5.87E-16 1600 400 10933 0.43% 00:00:14 3.41E-15 1650 412 11794 0.43% 00:00:16 2.86E-13 1700 425 13269 0.46% 00:00:18 2.42E-12 1750 437 14077 0.46% 00:00:22 1.20E-14 1800 450 13255 0.41% 00:00:20 3.74E-14 1850 462 12499 0.37% 00:00:22 6.44E-14 1900 475 13158 0.36% 00:00:27 1.72E-13 1950 487 13559 0.36% 00:00:25 1.96E-11 2000 500 15705 0.39% 00:00:31 1.50E-11

170

N C Fill-in


Relativo(%) 2050 512 13991 0.33% 00:00:29 2.22E-15 2100 525 13902 0.32% 00:00:35 4.33E-16 2150 537 15042 0.33% 00:00:37 0.00E+00 2200 550 15298 0.32% 00:00:37 2.54E-12 2250 562 15007 0.30% 00:00:42 2.02E-15 2300 575 15948 0.30% 00:00:42 7.12E-15 2350 587 17229 0.31% 00:00:54 4.06E-14 2400 600 15989 0.28% 00:00:48 2.39E-14 2450 612 16331 0.27% 00:00:59 1.86E-15 2500 625 19919 0.32% 00:00:58 5.24E-14 2550 637 17408 0.27% 00:01:05 0.00E+00 2600 650 18951 0.28% 00:00:55 7.00E-16 2650 662 18634 0.27% 00:00:57 2.92E-14 2700 675 17860 0.24% 00:01:04 3.37E-16 2750 687 18833 0.25% 00:01:07 1.46E-14 2800 700 21781 0.28% 00:01:09 3.79E-13 2850 712 19635 0.24% 00:01:17 6.38E-16 2900 725 19815 0.24% 00:01:24 3.14E-16 2950 737 19548 0.22% 00:01:27 0.00E+00 3000 750 21029 0.23% 00:01:35 3.33E-15

171


matrizes da classe E, utilizando o Modelo Proposto, com técnicas de Pivotamento do

Grupo II (Pivotamento Markowitz).

N C Fill-in


Relativo(%) 50 12 315 12.60% 00:00:00 8.89E-12 100 25 699 6.99% 00:00:00 2.19E-12 150 37 1098 4.88% 00:00:00 9.70E-14 200 50 1514 3.79% 00:00:00 9.59E-12 250 62 2019 3.23% 00:00:00 2.34E-11 300 75 2336 2.60% 00:00:01 0.00E+00 350 87 2832 2.31% 00:00:00 1.41E-11 400 100 3224 2.02% 00:00:00 5.37E-13 450 112 3603 1.78% 00:00:01 1.78E-13 500 125 3796 1.52% 00:00:00 2.18E-14 550 137 4549 1.50% 00:00:01 2.65E-12 600 150 4726 1.31% 00:00:01 6.06E-15 650 162 5099 1.21% 00:00:01 6.83E-11 700 175 5863 1.20% 00:00:01 4.77E-12 750 187 6147 1.09% 00:00:02 2.57E-12 800 200 6263 0.98% 00:00:02 1.46E-11 850 212 6824 0.94% 00:00:03 1.48E-11 900 225 7449 0.92% 00:00:03 1.01E-15 950 237 7796 0.86% 00:00:03 4.12E-14 1000 250 7631 0.76% 00:00:04 1.73E-14 1050 262 7860 0.71% 00:00:05 1.30E-11 1100 275 8678 0.72% 00:00:05 3.39E-14 1150 287 9036 0.68% 00:00:07 0.00E+00 1200 300 8850 0.61% 00:00:07 1.21E-11 1250 312 9353 0.60% 00:00:08 2.79E-11 1300 325 10781 0.64% 00:00:09 1.40E-15 1350 337 9561 0.52% 00:00:10 1.35E-15 1400 350 11382 0.58% 00:00:12 8.38E-14 1450 362 10432 0.50% 00:00:12 8.18E-13 1500 375 11239 0.50% 00:00:14 3.12E-11 1550 387 12729 0.53% 00:00:16 4.87E-14 1600 400 11541 0.45% 00:00:16 6.99E-14 1650 412 12029 0.44% 00:00:19 1.43E-11 1700 425 13628 0.47% 00:00:20 1.43E-13 1750 437 12589 0.41% 00:00:20 8.42E-14 1800 450 13210 0.41% 00:00:22 1.21E-14 1850 462 14104 0.41% 00:00:24 1.47E-14 1900 475 15266 0.42% 00:00:26 7.64E-11 1950 487 15288 0.40% 00:00:27 4.03E-12 2000 500 16322 0.41% 00:00:30 6.82E-12

172

N C Fill-in


Relativo(%) 2050 512 14609 0.35% 00:00:32 4.40E-13 2100 525 14757 0.33% 00:00:34 6.06E-15 2150 537 17139 0.37% 00:00:40 2.67E-14 2200 550 15283 0.32% 00:00:39 3.07E-12 2250 562 16479 0.33% 00:00:46 4.42E-13 2300 575 18600 0.35% 00:00:48 2.74E-13 2350 587 18663 0.34% 00:00:51 5.46E-12 2400 600 16839 0.29% 00:00:53 7.58E-16 2450 612 18051 0.30% 00:00:58 8.46E-14 2500 625 17347 0.28% 00:00:59 7.28E-16 2550 637 20626 0.32% 00:01:04 3.57E-16 2600 650 18680 0.28% 00:01:10 3.50E-16 2650 662 21265 0.30% 00:01:24 1.78E-14 2700 675 18552 0.25% 00:01:19 4.38E-15 2750 687 21773 0.29% 00:01:24 3.31E-15 2800 700 20059 0.26% 00:01:29 7.53E-12 2850 712 23390 0.29% 00:01:29 1.02E-14 2900 725 20537 0.24% 00:01:34 1.74E-11 2950 737 20015 0.23% 00:01:36 0.00E+00 3000 750 24664 0.27% 00:01:42 1.82E-14

173

Tabela 19 – Tempos Computacionais da Resolução de Problemas de Otimização

Não Lineares simulando problemas de Fluxo de Potência Ótima utilizando o Método

Seqüencial Quadrático com o Modelo de Armazenamento Proposto

Método Seqüêncial Quadrático utilizando Modelo Proposto de Armazenamento

Nº de

Barras

Nº de

Variáveis

Nº de

Restrições

Função

Objetivo Linear

Função

Objetivo Não

Linear

50 100 200 00:00:01 00:00:00 100 200 400 00:00:01 00:00:02 150 300 600 00:00:03 00:00:04 200 400 800 00:00:07 00:00:09 250 500 1000 00:00:13 00:00:17 300 600 1200 00:00:21 00:00:27 350 700 1400 00:00:32 00:00:42

Tabela 20 – Tempos Computacionais da Resolução de Problemas de Otimização

Não Lineares simulando problemas de Fluxo de Potência Ótima utilizando o Método

Seqüencial Quadrático com o Modelo de Armazenamento Padrão

Método Seqüêncial Quadrático utilizando Modelo de Armazenamento Padrão

Nº de

Barras

Nº de

Variáveis

Nº de

Restrições

Função

Objetivo Linear

Função

Objetivo Não

Linear

50 100 200 00:00:02 00:00:01 100 200 400 00:00:08 00:00:11 150 300 600 00:00:25 00:00:38 200 400 800 00:00:59 00:01:29 250 500 1000 00:01:52 00:02:54 300 600 1200 00:03:12 00:05:37 350 700 1400 00:05:11 00:09:49

Documents

DESENVOLVIMENTO DE UM MODELO DE …uenf.br/Uenf/Downloads/POS-ENGPRODUCAO_2397_1190378971.pdf · DINÂMICO DE DADOS PARA RESOLUÇÃO DE SISTEMAS LINEARES ESPARSOS E SEU USO EM PROBLEMAS