Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória
The inversion of extremely high order matrices has been a challenging task because of the limited processing and memory capacity of conventional computers. In a scenario in which the data does not fit in memory, it is worth to consider exchanging more processing time for less memory usage in orde...
Na minha lista:
Autor principal: | |
---|---|
Outros Autores: | |
Formato: | doctoralThesis |
Idioma: | por |
Publicado em: |
Brasil
|
Assuntos: | |
Endereço do item: | https://repositorio.ufrn.br/jspui/handle/123456789/25895 |
Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
id |
ri-123456789-25895 |
---|---|
record_format |
dspace |
institution |
Repositório Institucional |
collection |
RI - UFRN |
language |
por |
topic |
Matrizes em bloco Baixo consumo de memória Complemento de Schur Inversão de matrizes de grande porte CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA |
spellingShingle |
Matrizes em bloco Baixo consumo de memória Complemento de Schur Inversão de matrizes de grande porte CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA Cosme, Iria Caline Saraiva Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória |
description |
The inversion of extremely high order matrices has been a challenging task because of
the limited processing and memory capacity of conventional computers. In a scenario in
which the data does not fit in memory, it is worth to consider exchanging more processing
time for less memory usage in order to enable the computation of the inverse, which
otherwise would be prohibitive.
Therefore, this work introduces a novel algorithm to compute the inverse of block
partitioned matrices with a reduced memory footprint. The algorithm works recursively
to invert one block of a k×k block matrix M, with k ≥ 2, based on the successive splitting
of M into lower order matrices. This algorithm, called Block Recursive Inverse (BRI),
computes one block of the inverse at a time to limit memory usage during the entire
processing.
Considering that the low memory consumption, provided by the BRI, is counterbalanced
by longer processing time, this work also discusses a parallel implementation of the
algorithm in OpenMP to reduce the running time and to extend its applicability. Additionally,
an improvement in the sequential algorithm is proposed.
As a practical application, the proposed algorithm was applied in the cross-validation
process for Least Squares Support Vector Machines (LS-SVM). This computational procedure
uses the inverse matrix calculation to find the expected labels of the test samples
in the cross-validation.
Experimental results with BRI show that, despite increasing computational complexity,
matrices that otherwise would exceed the memory-usage limit can be inverted using
this technique |
author2 |
Souza, Samuel Xavier de |
author_facet |
Souza, Samuel Xavier de Cosme, Iria Caline Saraiva |
format |
doctoralThesis |
author |
Cosme, Iria Caline Saraiva |
author_sort |
Cosme, Iria Caline Saraiva |
title |
Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória |
title_short |
Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória |
title_full |
Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória |
title_fullStr |
Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória |
title_full_unstemmed |
Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória |
title_sort |
um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória |
publisher |
Brasil |
publishDate |
2018 |
url |
https://repositorio.ufrn.br/jspui/handle/123456789/25895 |
work_keys_str_mv |
AT cosmeiriacalinesaraiva ummetodoparaocalculodainversadematrizesemblocoscomusolimitadodememoria |
_version_ |
1773958936467079168 |
spelling |
ri-123456789-258952019-01-30T06:04:59Z Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória Cosme, Iria Caline Saraiva Souza, Samuel Xavier de Doria Neto, Adrião Duarte Aloise, Daniel Oliveira, Luiz Affonso Henderson Guedes de Oliveira, Aurelio Ribeiro Leite de Lima Júnior, Francisco Chagas de Matrizes em bloco Baixo consumo de memória Complemento de Schur Inversão de matrizes de grande porte CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA The inversion of extremely high order matrices has been a challenging task because of the limited processing and memory capacity of conventional computers. In a scenario in which the data does not fit in memory, it is worth to consider exchanging more processing time for less memory usage in order to enable the computation of the inverse, which otherwise would be prohibitive. Therefore, this work introduces a novel algorithm to compute the inverse of block partitioned matrices with a reduced memory footprint. The algorithm works recursively to invert one block of a k×k block matrix M, with k ≥ 2, based on the successive splitting of M into lower order matrices. This algorithm, called Block Recursive Inverse (BRI), computes one block of the inverse at a time to limit memory usage during the entire processing. Considering that the low memory consumption, provided by the BRI, is counterbalanced by longer processing time, this work also discusses a parallel implementation of the algorithm in OpenMP to reduce the running time and to extend its applicability. Additionally, an improvement in the sequential algorithm is proposed. As a practical application, the proposed algorithm was applied in the cross-validation process for Least Squares Support Vector Machines (LS-SVM). This computational procedure uses the inverse matrix calculation to find the expected labels of the test samples in the cross-validation. Experimental results with BRI show that, despite increasing computational complexity, matrices that otherwise would exceed the memory-usage limit can be inverted using this technique A inversão de matrizes de ordem extremamente alta tem sido uma tarefa desafiadora devido ao processamento e à capacidade de memória limitados dos computadores convencionais. Em um cenário em que os dados não cabem na memória, é oportuno considerar a troca de mais tempo de processamento por menos uso de memória para permitir a computação da inversa matricial, o que seria proibitivo de outra forma. Sendo assim, este trabalho apresenta um novo algoritmo para o cálculo da inversa de matrizes particionadas em blocos com uso reduzido de memória. O algoritmo funciona de forma recursiva para inverter um bloco de uma matriz Mk×k , com k ≥ 2, com base na divisão de M, sucessivamente, em matrizes de menor ordem. Este algoritmo, denominado BRI (do inglês, Block Recursive Inversion), calcula um bloco da matriz inversa por vez para limitar o uso da memória durante todo o processamento. Considerando que o baixo consumo de memória, proporcionado pelo BRI, é contrabalanceado por um maior tempo de processamento, este trabalho também discorre sobre uma implementação paralela, em OpenMP, do algoritmo a fim de reduzir o tempo de processamento e ampliar sua aplicabilidade. Além disso, uma melhoria no algoritmo sequencial é proposta. Como aplicação prática, o algoritmo proposto foi utilizado no processo de validação cruzada para Máquinas de Vetor de Suporte por Mínimos Quadrados (LS-SVM, do inglês, Least Squares Support Vector Machines). Este procedimento computacional utiliza o cálculo da matriz inversa para encontrar os rótulos esperados das amostras de testes na validação cruzada. Os resultados experimentais com o BRI demonstraram que, apesar do aumento da complexidade computacional, matrizes, que de outra forma excederiam o limite de uso da memória, podem ser invertidas usando esta técnica. 2018-09-20T19:01:39Z 2018-09-20T19:01:39Z 2018-05-04 doctoralThesis COSME, Iria Caline Saraiva. Um método para o cálculo da inversa de matrizes em blocos com uso limitado de memória. 2018. 109f. Tese (Doutorado em Engenharia Elétrica e de Computação) - Centro de Tecnologia, Universidade Federal do Rio Grande do Norte, Natal, 2018. https://repositorio.ufrn.br/jspui/handle/123456789/25895 por Acesso Aberto application/pdf Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO |