A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients Article Swipe

PDF

Zhenbing Zeng , Huang Yong , Lu Yang , Yongsheng Rao ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2510.01568

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

Related Topics

The Alchemist (Novel)

The Stranger (Camus Novel)

Justine (De Sade Novel)

Haunted (Palahniuk Novel)

The Dutch House (Novel)

Less Than Zero (Novel)

Concepts

No concepts available.

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2510.01568
PDF: https://arxiv.org/pdf/2510.01568
OA Status: green
OpenAlex ID: https://openalex.org/W4414817604

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4414817604

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2510.01568

Digital Object Identifier
Title: A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-10-02

Full publication date if available
Authors: Zhenbing Zeng, Huang Yong, Lu Yang, Yongsheng Rao

List of authors in order
Landing page: https://arxiv.org/abs/2510.01568

Publisher landing page
PDF URL: https://arxiv.org/pdf/2510.01568

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2510.01568

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4414817604
doi	https://doi.org/10.48550/arxiv.2510.01568
ids.doi	https://doi.org/10.48550/arxiv.2510.01568
ids.openalex	https://openalex.org/W4414817604
fwci
type	preprint
title	A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10963
topics[0].field.id	https://openalex.org/fields/26
topics[0].field.display_name	Mathematics
topics[0].score	0.9399999976158142
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2612
topics[0].subfield.display_name	Numerical Analysis
topics[0].display_name	Advanced Optimization Algorithms Research
topics[1].id	https://openalex.org/T12661
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.9344000220298767
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2612
topics[1].subfield.display_name	Numerical Analysis
topics[1].display_name	Iterative Methods for Nonlinear Equations
is_xpac	False
apc_list
apc_paid
language	en
locations[0].id	pmh:oai:arXiv.org:2510.01568
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license	cc-by
locations[0].pdf_url	https://arxiv.org/pdf/2510.01568
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2510.01568
locations[1].id	doi:10.48550/arxiv.2510.01568
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2510.01568
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5058328411
authorships[0].author.orcid	https://orcid.org/0000-0002-9728-1114
authorships[0].author.display_name	Zhenbing Zeng
authorships[0].author_position	first
authorships[0].raw_author_name	Zeng, Zhenbing
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5015301060
authorships[1].author.orcid	https://orcid.org/0000-0001-8120-0757
authorships[1].author.display_name	Huang Yong
authorships[1].author_position	middle
authorships[1].raw_author_name	Huang, Yong
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5100454252
authorships[2].author.orcid	https://orcid.org/0000-0002-1282-9735
authorships[2].author.display_name	Lu Yang
authorships[2].author_position	middle
authorships[2].raw_author_name	Yang, Lu
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5003330124
authorships[3].author.orcid	https://orcid.org/0000-0001-9615-3658
authorships[3].author.display_name	Yongsheng Rao
authorships[3].author_position	last
authorships[3].raw_author_name	Rao, Yongsheng
authorships[3].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2510.01568
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	A Novel Algorithm for Representing Positive Semi-Definite Polynomials as Sums of Squares with Rational Coefficients
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10963
primary_topic.field.id	https://openalex.org/fields/26
primary_topic.field.display_name	Mathematics
primary_topic.score	0.9399999976158142
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2612
primary_topic.subfield.display_name	Numerical Analysis
primary_topic.display_name	Advanced Optimization Algorithms Research
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2510.01568
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://arxiv.org/pdf/2510.01568
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2510.01568
primary_location.id	pmh:oai:arXiv.org:2510.01568
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license	cc-by
primary_location.pdf_url	https://arxiv.org/pdf/2510.01568
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2510.01568
publication_date	2025-10-02
publication_year	2025
referenced_works_count	0
abstract_inverted_index.,	101, 104, 107
abstract_inverted_index.a	3, 8, 58, 64, 68
abstract_inverted_index.An	110
abstract_inverted_index.Lu	106
abstract_inverted_index.We	56
abstract_inverted_index.an	92
abstract_inverted_index.in	36, 45
abstract_inverted_index.is	42, 54, 91
abstract_inverted_index.of	70, 81, 94, 119, 122, 130
abstract_inverted_index.to	85, 112, 117
abstract_inverted_index.(in	127
abstract_inverted_index.RAO	108
abstract_inverted_index.SOS	25
abstract_inverted_index.Sum	118
abstract_inverted_index.all	34
abstract_inverted_index.and	48, 133
abstract_inverted_index.for	6, 12
abstract_inverted_index.our	30, 82
abstract_inverted_index.sum	69
abstract_inverted_index.the	37, 79, 95
abstract_inverted_index.This	0, 41, 89
abstract_inverted_index.YANG	105
abstract_inverted_index.Yong	100
abstract_inverted_index.ZENG	102
abstract_inverted_index.into	67
abstract_inverted_index.that	22, 33, 62
abstract_inverted_index.with	16, 27, 124
abstract_inverted_index.(SOS)	10
abstract_inverted_index.2024,	136
abstract_inverted_index.HUANG	99
abstract_inverted_index.exact	52
abstract_inverted_index.given	65
abstract_inverted_index.novel	4
abstract_inverted_index.paper	1
abstract_inverted_index.where	51
abstract_inverted_index.while	73
abstract_inverted_index.yield	24
abstract_inverted_index.44(5):	137
abstract_inverted_index.Unlike	19
abstract_inverted_index.formal	46
abstract_inverted_index.method	83
abstract_inverted_index.paper:	98
abstract_inverted_index.remain	39
abstract_inverted_index.useful	44
abstract_inverted_index.Journal	129
abstract_inverted_index.Science	132
abstract_inverted_index.Squares	121
abstract_inverted_index.Systems	131
abstract_inverted_index.artical	90
abstract_inverted_index.ensures	32
abstract_inverted_index.methods	21
abstract_inverted_index.results	77
abstract_inverted_index.squares	72
abstract_inverted_index.Chinnese	97
abstract_inverted_index.Positive	114
abstract_inverted_index.Rational	125
abstract_inverted_index.Zhenbing	103
abstract_inverted_index.approach	31
abstract_inverted_index.compared	84
abstract_inverted_index.existing	86
abstract_inverted_index.positive	13
abstract_inverted_index.presents	2
abstract_inverted_index.previous	20
abstract_inverted_index.rational	17
abstract_inverted_index.stepwise	59
abstract_inverted_index.symbolic	49
abstract_inverted_index.1241-1271	138
abstract_inverted_index.Algorithm	111
abstract_inverted_index.Chinese).	128
abstract_inverted_index.Represent	113
abstract_inverted_index.Sciences,	135
abstract_inverted_index.algorithm	5
abstract_inverted_index.extension	93
abstract_inverted_index.following	96
abstract_inverted_index.introduce	57
abstract_inverted_index.numerical	87
abstract_inverted_index.rational.	40
abstract_inverted_index.reduction	60
abstract_inverted_index.required.	55
abstract_inverted_index.technique	61
abstract_inverted_index.typically	23
abstract_inverted_index.Lader-Like	120
abstract_inverted_index.Yongsheng.	109
abstract_inverted_index.arithmetic	53
abstract_inverted_index.polynomial	66
abstract_inverted_index.preserving	74
abstract_inverted_index.transforms	63
abstract_inverted_index.Polynomials	116, 123
abstract_inverted_index.approaches.	88
abstract_inverted_index.demonstrate	78
abstract_inverted_index.ladder-like	71
abstract_inverted_index.polynomials	15
abstract_inverted_index.Coefficients	126
abstract_inverted_index.Experimental	76
abstract_inverted_index.Mathematical	134
abstract_inverted_index.coefficients	35
abstract_inverted_index.computation,	50
abstract_inverted_index.constructing	7
abstract_inverted_index.particularly	43
abstract_inverted_index.rationality.	75
abstract_inverted_index.verification	47
abstract_inverted_index.Semi-Definite	115
abstract_inverted_index.coefficients,	29
abstract_inverted_index.coefficients.	18
abstract_inverted_index.decomposition	11, 38
abstract_inverted_index.effectiveness	80
abstract_inverted_index.semi-definite	14
abstract_inverted_index.decompositions	26
abstract_inverted_index.floating-point	28
abstract_inverted_index.sum-of-squares	9
abstract_inverted_index.https://doi.org/10.12341/jssms23584CM	139
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile