A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908574217666560 |
|---|---|
| author | Zeng, Zhenbing Huang, Yong Yang, Lu Rao, Yongsheng |
| author_facet | Zeng, Zhenbing Huang, Yong Yang, Lu Rao, Yongsheng |
| contents | This paper presents a novel algorithm for constructing a sum-of-squares (SOS) decomposition for positive semi-definite polynomials with rational coefficients. Unlike previous methods that typically yield SOS decompositions with floating-point coefficients, our approach ensures that all coefficients in the decomposition remain rational. This is particularly useful in formal verification and symbolic computation, where exact arithmetic is required. We introduce a stepwise reduction technique that transforms a given polynomial into a sum of ladder-like squares while preserving rationality. Experimental results demonstrate the effectiveness of our method compared to existing numerical approaches. This artical is an extension of the following Chinnese paper: HUANG Yong , ZENG Zhenbing , YANG Lu , RAO Yongsheng. An Algorithm to Represent Positive Semi-Definite Polynomials to Sum of Lader-Like Squares of Polynomials with Rational Coefficients (in Chinese). Journal of Systems Science and Mathematical Sciences, 2024, 44(5): 1241-1271 https://doi.org/10.12341/jssms23584CM |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01568 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients Zeng, Zhenbing Huang, Yong Yang, Lu Rao, Yongsheng Symbolic Computation Numerical Analysis Algebraic Geometry This paper presents a novel algorithm for constructing a sum-of-squares (SOS) decomposition for positive semi-definite polynomials with rational coefficients. Unlike previous methods that typically yield SOS decompositions with floating-point coefficients, our approach ensures that all coefficients in the decomposition remain rational. This is particularly useful in formal verification and symbolic computation, where exact arithmetic is required. We introduce a stepwise reduction technique that transforms a given polynomial into a sum of ladder-like squares while preserving rationality. Experimental results demonstrate the effectiveness of our method compared to existing numerical approaches. This artical is an extension of the following Chinnese paper: HUANG Yong , ZENG Zhenbing , YANG Lu , RAO Yongsheng. An Algorithm to Represent Positive Semi-Definite Polynomials to Sum of Lader-Like Squares of Polynomials with Rational Coefficients (in Chinese). Journal of Systems Science and Mathematical Sciences, 2024, 44(5): 1241-1271 https://doi.org/10.12341/jssms23584CM |
| title | A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients |
| topic | Symbolic Computation Numerical Analysis Algebraic Geometry |
| url | https://arxiv.org/abs/2510.01568 |