DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2023.42

Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization

Authors: Papri Dey, Ravi Kannan, Nick Ryder, and Nikhil Srivastava

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An Õ(n^{ω+3}a+n⁴a²+n^ωlog(1/ε)) time algorithm for finding an ε-approximation to the Jordan Normal form of an integer matrix with a-bit entries, where ω is the exponent of matrix multiplication. (2) An Õ(n⁶d⁶a+n⁴d⁴a²+n³d³log(1/ε)) time algorithm for ε-approximately computing the spectral factorization P(x) = Q^*(x)Q(x) of a given monic n× n rational matrix polynomial of degree 2d with rational a-bit coefficients having a-bit common denominators, which satisfies P(x)⪰0 for all real x. The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in n of degree at least twelve [Cai, 1994]. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.

Cite as

Papri Dey, Ravi Kannan, Nick Ryder, and Nikhil Srivastava. Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ITCS.2023.42,
  author =	{Dey, Papri and Kannan, Ravi and Ryder, Nick and Srivastava, Nikhil},
  title =	{{Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.42},
  URN =		{urn:nbn:de:0030-drops-175450},
  doi =		{10.4230/LIPIcs.ITCS.2023.42},
  annote =	{Keywords: Symbolic algorithms, numerical algorithms, linear algebra}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2017.5

Real Stability Testing

Authors: Prasad Raghavendra, Nick Ryder, and Nikhil Srivastava

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract

We give a strongly polynomial time algorithm which determines whether or not a bivariate polynomial is real stable. As a corollary, this implies an algorithm for testing whether a given linear transformation on univariate polynomials preserves real-rootedness. The proof exploits properties of hyperbolic polynomials to reduce real stability testing to testing nonnegativity of a finite number of polynomials on an interval.

Cite as

Prasad Raghavendra, Nick Ryder, and Nikhil Srivastava. Real Stability Testing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{raghavendra_et_al:LIPIcs.ITCS.2017.5,
  author =	{Raghavendra, Prasad and Ryder, Nick and Srivastava, Nikhil},
  title =	{{Real Stability Testing}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.5},
  URN =		{urn:nbn:de:0030-drops-81965},
  doi =		{10.4230/LIPIcs.ITCS.2017.5},
  annote =	{Keywords: real stable polynomials, hyperbolic polynomials, real rootedness, moment matrix, sturm sequence}
}

Search Results

Documents authored by Ryder, Nick

Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization

Abstract

Cite as

Real Stability Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message