# A New Sparse SOS Decomposition Algorithm Based on Term Sparsity

arXiv: https://arxiv.org/abs/1809.10848 · HTML: https://mlsanity.com/paper/1809.10848/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2018.

## Built on by (most cited first, 1 of 1)

- [Sparse Polynomial Optimization: Theory and Practice](https://mlsanity.com/paper/2208.11158/) (2022)

## Abstract (arXiv)

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.