论文标题
SparseJSR：通过稀疏SOS分解来计算关节光谱半径的快速算法
SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions
论文作者
论文摘要
本文着重于关节光谱（JSR）的计算，当相关矩阵稀疏时。我们提供了Parrilo和Jadbabaie提出的程序的稀疏变体，以通过平方（SOS）弛豫来计算JSR的上限。我们由此产生的迭代算法（称为SparseJSR）基于由Wang，Magron和Lasserre开发的术语Sparsity SOS（TSSOS）框架，产生了具有任意稀疏支持的多项式的SOS分解。 SparseJSR利用输入矩阵的稀疏性，可以显着减轻与JSR计算相关的计算负担。然后，我们的算法框架成功地应用于随机生成的基准测试以及由于可能的硬件和软件故障而引起的稳定性证明的问题，并在随机生成的基准和问题上计算上限。
This paper focuses on the computation of joint spectral radii (JSR), when the involved matrices are sparse. We provide a sparse variant of the procedure proposed by Parrilo and Jadbabaie, to compute upper bounds of the JSR by means of sum-of-squares (SOS) relaxations. Our resulting iterative algorithm, called SparseJSR, is based on the term sparsity SOS (TSSOS) framework, developed by Wang, Magron and Lasserre, yielding SOS decompositions of polynomials with arbitrary sparse support. SparseJSR exploits the sparsity of the input matrices to significantly reduce the computational burden associated with the JSR computation. Our algorithmic framework is then successfully applied to compute upper bounds for JSR, on randomly generated benchmarks as well as on problems arising from stability proofs of controllers, in relation with possible hardware and software faults.
