Chordality Preserving Incremental Triangular Decomposition and Its Implementation

In this paper, we first prove that the incremental algorithm for computing triangular decompositions proposed by Chen and Moreno Maza in ISSAC’ 2011 in its original form preserves chordality, which is an important property on sparsity of variables. On the other hand, we find that the current impleme...

Descripción completa

Detalles Bibliográficos
Autor principal: Chen, Changbo
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7340895/
http://dx.doi.org/10.1007/978-3-030-52200-1_3
_version_ 1783555116343754752
author Chen, Changbo
author_facet Chen, Changbo
author_sort Chen, Changbo
collection PubMed
description In this paper, we first prove that the incremental algorithm for computing triangular decompositions proposed by Chen and Moreno Maza in ISSAC’ 2011 in its original form preserves chordality, which is an important property on sparsity of variables. On the other hand, we find that the current implementation in Triangularize command of the RegularChains library in Maple may not always respect chordality due to the use of some simplification operations. Experimentation show that modifying these operations, together with some other optimizations, brings significant speedups for some super sparse polynomial systems.
format Online
Article
Text
id pubmed-7340895
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73408952020-07-08 Chordality Preserving Incremental Triangular Decomposition and Its Implementation Chen, Changbo Mathematical Software – ICMS 2020 Article In this paper, we first prove that the incremental algorithm for computing triangular decompositions proposed by Chen and Moreno Maza in ISSAC’ 2011 in its original form preserves chordality, which is an important property on sparsity of variables. On the other hand, we find that the current implementation in Triangularize command of the RegularChains library in Maple may not always respect chordality due to the use of some simplification operations. Experimentation show that modifying these operations, together with some other optimizations, brings significant speedups for some super sparse polynomial systems. 2020-06-06 /pmc/articles/PMC7340895/ http://dx.doi.org/10.1007/978-3-030-52200-1_3 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Chen, Changbo
Chordality Preserving Incremental Triangular Decomposition and Its Implementation
title Chordality Preserving Incremental Triangular Decomposition and Its Implementation
title_full Chordality Preserving Incremental Triangular Decomposition and Its Implementation
title_fullStr Chordality Preserving Incremental Triangular Decomposition and Its Implementation
title_full_unstemmed Chordality Preserving Incremental Triangular Decomposition and Its Implementation
title_short Chordality Preserving Incremental Triangular Decomposition and Its Implementation
title_sort chordality preserving incremental triangular decomposition and its implementation
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7340895/
http://dx.doi.org/10.1007/978-3-030-52200-1_3
work_keys_str_mv AT chenchangbo chordalitypreservingincrementaltriangulardecompositionanditsimplementation

Ejemplares similares