RECORD
A New Sparse SOS Decomposition Algorithm Based on Term Sparsity
Optimization and Control · Submitted 28 Sep 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Moreover, it is proved that the SOS decomposition obtained by the new sparsity pattern is always a refinement of the block-diagonalization obtained by the sign-symmetry method. %Because the new sparsity pattern covers more sparse polynomials than correlative sparsity pattern, Various experiments show that the new algorithm dramatically saves the computational cost compared to existing tools and can handle some really huge polynomials.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
A new sparse SOS decomposition algorithm is proposed based on a new sparsity pattern, called cross sparsity patterns. The new sparsity pattern focuses on the sparsity of terms and thus is different from the well-known correlative sparsity pattern which focuses on the sparsity of variables though the sparse SOS decomposition algorithms based on these two sparsity patterns both take use of chordal extensions/chordal decompositions. Moreover, it is proved that the SOS decomposition obtained by the new sparsity pattern is always a refinement of the block-diagonalization obtained by the sign-symmetry method. %Because the new sparsity pattern covers more sparse polynomials than correlative sparsity pattern, Various experiments show that the new algorithm dramatically saves the computational cost compared to existing tools and can handle some really huge polynomials.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A new sparse SOS decomposition algorithm is proposed based on a new sparsity pattern, called cross sparsity patterns. | contribution 1.00 | 0.92 | 0.30 | asserted 1.00 |
| s1 | The new sparsity pattern focuses on the sparsity of terms and thus is different from the well-known correlative sparsity pattern which focuses on the sparsity of variables though the sparse SOS decomposition algorithms based on these two sparsity patterns both take use of chordal extensions/chordal decompositions. | contribution 0.62 | 0.32 | 0.08 | asserted 1.00 |
| s2 | Moreover, it is proved that the SOS decomposition obtained by the new sparsity pattern is always a refinement of the block-diagonalization obtained by the sign-symmetry method. %Because the new sparsity pattern covers more sparse polynomials than correlative sparsity pattern, Various experiments show that the new algorithm dramatically saves the computational cost compared to existing tools and can handle some really huge polynomials. | result 0.96 | 0.91 | 0.39 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
A new sparse SOS decomposition algorithm is proposed based on a new sparsity pattern, called cross sparsity patterns. The new sparsity pattern focuses on the sparsity of terms and thus is different from the well-known correlative sparsity pattern which focuses on the sparsity of variables though the sparse SOS decomposition algorithms based on these two sparsity patterns both take use of chordal extensions/chordal decompositions. Moreover, it is proved that the SOS decomposition obtained by the new sparsity pattern is always a refinement of the block-diagonalization obtained by the sign-symmetry method. %Because the new sparsity pattern covers more sparse polynomials than correlative sparsity pattern, Various experiments show that the new algorithm dramatically saves the computational cost compared to existing tools and can handle some really huge polynomials.
Human review
How the literature uses it
2 arXiv papers cite this in 2 sentences
Papers citing it
Uses its method or tool 1 paper
-
In fact, the monomial basis $^n_d$ in ([ref]) can be replaced by [ref] [equation] Second, the block-diagonal structure in the Gram matrix $Q$ can be exploited, namely cross sparsity patterns, which was introduced by the second author [ref] and will prove critical to achieving our main result.
On Radically Expanding the Landscape of Potential Applications for Automated Proof Methods · Certifying nonnegativity of sparse polynomials · 0.85
Cites it as background 1 paper
-
For the latter, structured sparsity arising from polynomial optimization problems is studied and utilized by using the chordal structures, resulting in sparse algorithms for sums-of-squares decomposition of multivariate polynomials [ref] .
Chordal Graphs in Triangular Decomposition in Top-Down Style · Introduction · 0.92
What it cites
Cites as background 1 paper
-
An interpretation of correlative sparsity patterns in terms of the sparsity of Gram matrices was recently given in [ref] .
Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials · Comparison with correlative sparsity patterns · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.