Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics Scheme
Solving polynomial equations inevitably faces many severe challenges, such as easily occupying storage space and demanding prohibitively expensive computation resources. There has been considerable interest in exploiting the sparsity to improve computation efficiency, since asymmetry phenomena are p...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-06-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/14/6/1174 |
| _version_ | 1797482008215027712 |
|---|---|
| author | Guoqiang Deng Niuniu Qi Min Tang Xuefeng Duan |
| author_facet | Guoqiang Deng Niuniu Qi Min Tang Xuefeng Duan |
| author_sort | Guoqiang Deng |
| collection | DOAJ |
| description | Solving polynomial equations inevitably faces many severe challenges, such as easily occupying storage space and demanding prohibitively expensive computation resources. There has been considerable interest in exploiting the sparsity to improve computation efficiency, since asymmetry phenomena are prevalent in scientific and engineering fields, especially as most of the systems in real applications have sparse representations. In this paper, we propose an efficient parallel hybrid algorithm for constructing a Dixon matrix. This approach takes advantage of the asymmetry (i.e., sparsity) in variables of the system and introduces a heuristics strategy. Our method supports parallel computation and has been implemented on a multi-core system. Through time-complexity analysis and extensive benchmarks, we show our new algorithm has significantly reduced computation and memory overhead. In addition, performance evaluation via the Fermat–Torricelli point problem demonstrates its effectiveness in combinatorial geometry optimizations. |
| first_indexed | 2024-03-09T22:22:08Z |
| format | Article |
| id | doaj.art-65e90301d6ba4f7e95a1deacce966208 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-09T22:22:08Z |
| publishDate | 2022-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-65e90301d6ba4f7e95a1deacce9662082023-11-23T19:12:00ZengMDPI AGSymmetry2073-89942022-06-01146117410.3390/sym14061174Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics SchemeGuoqiang Deng0Niuniu Qi1Min Tang2Xuefeng Duan3School of Computer Science and Information Security, Guilin University of Electronic Technology, Guilin 541004, ChinaSchool of Mathematics and Computing Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin 541004, ChinaSchool of Mathematics and Computing Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin 541004, ChinaSchool of Mathematics and Computing Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, Guilin 541004, ChinaSolving polynomial equations inevitably faces many severe challenges, such as easily occupying storage space and demanding prohibitively expensive computation resources. There has been considerable interest in exploiting the sparsity to improve computation efficiency, since asymmetry phenomena are prevalent in scientific and engineering fields, especially as most of the systems in real applications have sparse representations. In this paper, we propose an efficient parallel hybrid algorithm for constructing a Dixon matrix. This approach takes advantage of the asymmetry (i.e., sparsity) in variables of the system and introduces a heuristics strategy. Our method supports parallel computation and has been implemented on a multi-core system. Through time-complexity analysis and extensive benchmarks, we show our new algorithm has significantly reduced computation and memory overhead. In addition, performance evaluation via the Fermat–Torricelli point problem demonstrates its effectiveness in combinatorial geometry optimizations.https://www.mdpi.com/2073-8994/14/6/1174sparsityhybrid algorithmsuccessive Sylvester resultant computationsfast recursive algorithmDixon matrix |
| spellingShingle | Guoqiang Deng Niuniu Qi Min Tang Xuefeng Duan Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics Scheme Symmetry sparsity hybrid algorithm successive Sylvester resultant computations fast recursive algorithm Dixon matrix |
| title | Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics Scheme |
| title_full | Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics Scheme |
| title_fullStr | Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics Scheme |
| title_full_unstemmed | Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics Scheme |
| title_short | Constructing Dixon Matrix for Sparse Polynomial Equations Based on Hybrid and Heuristics Scheme |
| title_sort | constructing dixon matrix for sparse polynomial equations based on hybrid and heuristics scheme |
| topic | sparsity hybrid algorithm successive Sylvester resultant computations fast recursive algorithm Dixon matrix |
| url | https://www.mdpi.com/2073-8994/14/6/1174 |
| work_keys_str_mv | AT guoqiangdeng constructingdixonmatrixforsparsepolynomialequationsbasedonhybridandheuristicsscheme AT niuniuqi constructingdixonmatrixforsparsepolynomialequationsbasedonhybridandheuristicsscheme AT mintang constructingdixonmatrixforsparsepolynomialequationsbasedonhybridandheuristicsscheme AT xuefengduan constructingdixonmatrixforsparsepolynomialequationsbasedonhybridandheuristicsscheme |