Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions

A new partitioning algorithm that permutes sparse matrices to a specific block lower-triangular form (BlTF) complying with special features required for instrumentation problems is presented. The proposal consists in the decomposition of the occurrence matrix in two stages, using methodologies based...

Descripción completa

Detalles Bibliográficos
Autores principales: Ponzoni, Ignacio, Sánchez, Mabel C., Brignole, Nélida B.
Formato: Articulo
Lenguaje:Inglés
Publicado: 1998
Materias:
Ciencias Informáticas
Graph theory
directed graphs
bipartite graphs
sparse matrices
block lower-triangular forms
assignment algorithms
partitioning algorithms
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/135519
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/136
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-135519
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Graph theory
directed graphs
bipartite graphs
sparse matrices
block lower-triangular forms
assignment algorithms
partitioning algorithms
spellingShingle Ciencias Informáticas
Graph theory
directed graphs
bipartite graphs
sparse matrices
block lower-triangular forms
assignment algorithms
partitioning algorithms
Ponzoni, Ignacio
Sánchez, Mabel C.
Brignole, Nélida B.
Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
topic_facet Ciencias Informáticas
Graph theory
directed graphs
bipartite graphs
sparse matrices
block lower-triangular forms
assignment algorithms
partitioning algorithms
description A new partitioning algorithm that permutes sparse matrices to a specific block lower-triangular form (BlTF) complying with special features required for instrumentation problems is presented. The proposal consists in the decomposition of the occurrence matrix in two stages, using methodologies based on graph theory. First of all, Hopcroft-Karp´s algorithm is employed to match the vertices, this classification being carried out by means of a modification of Dulmage-Mendelsohn´s technique, which was devised by the authors. The second step is the application of Tarjan´s algorithm to the square blocks obtained as a result of the first stage.
format Articulo
Articulo
author Ponzoni, Ignacio
Sánchez, Mabel C.
Brignole, Nélida B.
author_facet Ponzoni, Ignacio
Sánchez, Mabel C.
Brignole, Nélida B.
author_sort Ponzoni, Ignacio
title Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
title_short Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
title_full Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
title_fullStr Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
title_full_unstemmed Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
title_sort permutation of sparse matrices to a specific lower btf using graph decompositions
publishDate 1998
url http://sedici.unlp.edu.ar/handle/10915/135519
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/136
work_keys_str_mv AT ponzoniignacio permutationofsparsematricestoaspecificlowerbtfusinggraphdecompositions
AT sanchezmabelc permutationofsparsematricestoaspecificlowerbtfusinggraphdecompositions
AT brignolenelidab permutationofsparsematricestoaspecificlowerbtfusinggraphdecompositions
bdutipo_str Repositorios
_version_ 1764820455436320770

Ejemplares similares