Triangular decomposition algorithms that preserve chordal structure have proven effective for solving sparse polynomial systems. Additionally, choosing perfect elimination orderings plays an important role in the performance of sparse triangular decomposition, as different orderings can lead to significantly different computational costs. In this paper, we theoretically demonstrate that all the other variables that may occur in the intermediate polynomials generated during the elimination process started from polynomials with leading variable \(x_i\) are confined to the path from the node \(x_i\) to the root node in the elimination tree. This property not only relaxes certain assumptions previously required in complexity analyses of triangular decomposition algorithm over \(\mathbb {F}_2\) based on chordal graphs, but also provides a new heuristic aimed at selecting perfect elimination orderings for a class of triangular decomposition algorithms. The key idea of the proposed heuristic is to reduce the number of variable elimination by minimizing the average height of the corresponding elimination tree, which is defined as the ratio of the sum of the distances from all nodes to the root to the total number of nodes. Experimental results show that the elimination orderings generated by our proposed algorithm lead to improved efficiency in computing sparse triangular decompositions.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Choosing Variable Orderings Based on Elimination Tree for Sparse Triangular Decomposition

  • Zhaoxing Qi,
  • Linpeng Wang

摘要

Triangular decomposition algorithms that preserve chordal structure have proven effective for solving sparse polynomial systems. Additionally, choosing perfect elimination orderings plays an important role in the performance of sparse triangular decomposition, as different orderings can lead to significantly different computational costs. In this paper, we theoretically demonstrate that all the other variables that may occur in the intermediate polynomials generated during the elimination process started from polynomials with leading variable \(x_i\) are confined to the path from the node \(x_i\) to the root node in the elimination tree. This property not only relaxes certain assumptions previously required in complexity analyses of triangular decomposition algorithm over \(\mathbb {F}_2\) based on chordal graphs, but also provides a new heuristic aimed at selecting perfect elimination orderings for a class of triangular decomposition algorithms. The key idea of the proposed heuristic is to reduce the number of variable elimination by minimizing the average height of the corresponding elimination tree, which is defined as the ratio of the sum of the distances from all nodes to the root to the total number of nodes. Experimental results show that the elimination orderings generated by our proposed algorithm lead to improved efficiency in computing sparse triangular decompositions.