Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

SparseJSR: A fast algorithm to compute joint spectral radius via sparse SOS decompositions

Wang, Jie ; Maggio, Martina LU and Magron, Victor LU (2021) 2021 American Control Conference, ACC 2021 In Proceedings of the American Control Conference 2021-May. p.2254-2259
Abstract
This paper focuses on the computation of the joint spectral radius (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) programming. Our resulting iterative algorithm, called SparseJSR, is based on the term sparsity SOS (TSSOS) framework developed by Wang, Magron and Lasserre, which yields SOS decompositions of polynomials with arbitrary sparse supports. 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... (More)
This paper focuses on the computation of the joint spectral radius (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) programming. Our resulting iterative algorithm, called SparseJSR, is based on the term sparsity SOS (TSSOS) framework developed by Wang, Magron and Lasserre, which yields SOS decompositions of polynomials with arbitrary sparse supports. 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. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
2021 American Control Conference, ACC 2021
series title
Proceedings of the American Control Conference
volume
2021-May
article number
9483347
pages
6 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
2021 American Control Conference, ACC 2021
conference location
Virtual, New Orleans, United States
conference dates
2021-05-25 - 2021-05-28
external identifiers
  • scopus:85101645952
  • scopus:85101645952
ISSN
0743-1619
ISBN
9781665441971
DOI
10.23919/ACC50511.2021.9483347
language
English
LU publication?
yes
additional info
Publisher Copyright: © 2021 American Automatic Control Council.
id
2ab02df8-4c7d-4446-a405-a7f73fde6937
date added to LUP
2022-03-22 23:25:17
date last changed
2023-11-16 15:46:10
@inproceedings{2ab02df8-4c7d-4446-a405-a7f73fde6937,
  abstract     = {{This paper focuses on the computation of the joint spectral radius (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) programming. Our resulting iterative algorithm, called SparseJSR, is based on the term sparsity SOS (TSSOS) framework developed by Wang, Magron and Lasserre, which yields SOS decompositions of polynomials with arbitrary sparse supports. 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.}},
  author       = {{Wang, Jie and Maggio, Martina and Magron, Victor}},
  booktitle    = {{2021 American Control Conference, ACC 2021}},
  isbn         = {{9781665441971}},
  issn         = {{0743-1619}},
  language     = {{eng}},
  pages        = {{2254--2259}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{Proceedings of the American Control Conference}},
  title        = {{SparseJSR: A fast algorithm to compute joint spectral radius via sparse SOS decompositions}},
  url          = {{http://dx.doi.org/10.23919/ACC50511.2021.9483347}},
  doi          = {{10.23919/ACC50511.2021.9483347}},
  volume       = {{2021-May}},
  year         = {{2021}},
}