Document Open Access Logo

Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.42.pdf
  • Filesize: 0.71 MB
  • 18 pages

Document Identifiers

Author Details

Papri Dey
  • Georgia Tech, Atlanta, GA, USA
Ravi Kannan
  • Microsoft Research, Bangalore, India
Nick Ryder
  • OpenAI, San Francisco, CA, USA
Nikhil Srivastava
  • UC Berkeley, CA, USA

Funding

  • Srivastava, Nikhil: Supported by NSF Grant CCF-2009011.

Acknowledgements

We thank the anonymous referees of a previous version of this paper, whose thoughtful comments greatly improved the presentation. We thank Bill Helton, Clément Pernet, Pablo Parrilo, Mario Kummer, Rafael Oliveira, and Rainer Sinn for helpful discussions, as well as the Simons Institute for the Theory of Computing, where a large part of this work was carried out during the "Geometry of Polynomials" program.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ITCS.2023.42

Abstract

We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An Õ(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 Õ(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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Numerical analysis
Keywords
  • Symbolic algorithms
  • numerical algorithms
  • linear algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sigal Ar and Jin-Yi Cai. Reliable benchmarks using numerical instability. In SODA, pages 34-43, 1994. Google Scholar
  2. Erin M Aylward, Sleiman M Itani, and Pablo A Parrilo. Explicit sos decompositions of univariate polynomial matrices and the kalman-yakubovich-popov lemma. In 2007 46th IEEE Conference on Decision and Control, pages 5660-5665. IEEE, 2007. Google Scholar
  3. Mihály Bakonyi and Hugo J Woerdeman. Matrix completions, moments, and sums of Hermitian squares, volume 37. Princeton University Press, 2011. Google Scholar
  4. Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava. Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 529-540. IEEE, 2020. Google Scholar
  5. Dmitry Batenkov. On the norm of inverses of confluent vandermonde matrices. arXiv preprint, 2012. URL: http://arxiv.org/abs/1212.0172.
  6. Grigoriy Blekherman, Daniel Plaumann, Rainer Sinn, and Cynthia Vinzant. Low-rank sum-of-squares representations on varieties of minimal degree. International Mathematics Research Notices, 2019(1):33-54, 2019. Google Scholar
  7. Louis Brand. The companion matrix and its properties. The American Mathematical Monthly, 71(6):629-634, 1964. Google Scholar
  8. Jin-yi Cai. Computing jordan normal forms exactly for commuting matrices in polynomial time. International Journal of Foundations of Computer Science, 5(03n04):293-302, 1994. Google Scholar
  9. Man-Duen Choi, Tsit Yuen Lam, and Bruce Reznick. Sums of squares of real polynomials. In Proceedings of Symposia in Pure mathematics, volume 58, pages 103-126. American Mathematical Society, 1995. Google Scholar
  10. Michael A Dritschel and James Rovnyak. The operator fejér-riesz theorem. In A glimpse at Hilbert space operators, pages 223-254. Springer, 2010. Google Scholar
  11. Lasha Ephremidze. An elementary proof of the polynomial matrix spectral factorization theorem. Proceedings. Section A, Mathematics-The Royal Society of Edinburgh, 144(4):747, 2014. Google Scholar
  12. Lasha Ephremidze, Gigla Janashia, and Edem Lagvilava. A simple proof of the matrix-valued fejér-riesz theorem. Journal of Fourier Analysis and Applications, 15(1):124-127, 2009. Google Scholar
  13. Lasha Ephremidze, Faisal Saied, and Ilya Matvey Spitkovsky. On the algorithmization of janashia-lagvilava matrix spectral factorization method. IEEE Transactions on Information Theory, 64(2):728-737, 2017. Google Scholar
  14. Walter Gautschi. On inverses of vandermonde and confluent vandermonde matrices. Numerische Mathematik, 4(1):117-123, 1962. Google Scholar
  15. Mark Giesbrecht. Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, 24(5):948-969, 1995. Google Scholar
  16. Mark Giesbrecht and Arne Storjohann. Computing rational forms of integer matrices. Journal of Symbolic Computation, 34(3):157-172, 2002. Google Scholar
  17. Isabelle Gil. Computation of the jordan canonical form of a square matrix (using the axiom programming language). In Papers from the international symposium on Symbolic and algebraic computation, pages 138-145, 1992. Google Scholar
  18. Israel Gohberg, Peter Lancaster, and Leiba Rodman. Spectral analysis of selfadjoint matrix polynomials. Annals of Mathematics, 112(1):33-71, 1980. Google Scholar
  19. Israel Gohberg, Peter Lancaster, and Leiba Rodman. Matrix polynomials. Springer, 2005. Google Scholar
  20. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012. Google Scholar
  21. Somit Gupta and Arne Storjohann. Computing hermite forms of polynomial matrices. In Proceedings of the 36th international symposium on Symbolic and algebraic computation, pages 155-162, 2011. Google Scholar
  22. Christoph Hanselka and Rainer Sinn. Positive semidefinite univariate matrix polynomials. Mathematische Zeitschrift, 292(1-2):83-101, 2019. Google Scholar
  23. Douglas P Hardin, Thomas A Hogan, and Qiyu Sun. The matrix-valued riesz lemma and local orthonormal bases in shift-invariant spaces. Advances in Computational Mathematics, 20(4):367-384, 2004. Google Scholar
  24. Henry Helson and David Lowdenslager. Prediction theory and fourier series in several variables. Acta mathematica, 99(1):165-202, 1958. Google Scholar
  25. G Janashia, E Lagvilava, and L Ephremidze. Matrix spectral factorization and wavelets. Journal of Mathematical Sciences, 195(4):445-454, 2013. Google Scholar
  26. Gigla Janashia, Edem Lagvilava, and Lasha Ephremidze. A new method of matrix spectral factorization. IEEE Transactions on information theory, 57(4):2318-2326, 2011. Google Scholar
  27. Erich Kaltofen, M Krishnamoorthy, and B David Saunders. Fast parallel algorithms for similarity of matrices. In Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, pages 65-70, 1986. Google Scholar
  28. Erich L Kaltofen and Arne Storjohann. The complexity of computational problems in exact linear algebra, 2015. Google Scholar
  29. Ravindran Kannan. Solving systems of linear equations over polynomials. Theoretical Computer Science, 39:69-88, 1985. Google Scholar
  30. Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix. siam Journal on Computing, 8(4):499-507, 1979. Google Scholar
  31. Heinz Langer. Factorization of operator pencils. Acta Sci. Math.(Szeged), 38(1-2):83-96, 1976. Google Scholar
  32. TY Li, Zhinan Zhang, and Tianjun Wang. Determining the structure of the jordan normal form of a matrix by symbolic computation. Linear algebra and its applications, 252(1-3):221-259, 1997. Google Scholar
  33. Kurt Mahler et al. An inequality for the discriminant of a polynomial. Michigan Mathematical Journal, 11(3):257-262, 1964. Google Scholar
  34. Patrick Ozello. Calcul exact des formes de jordan et de frobenius d'une matrice, 1987. Google Scholar
  35. Victor Y Pan. Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. Journal of Symbolic Computation, 33(5):701-733, 2002. Google Scholar
  36. Victor Y Pan and Zhao Q Chen. The complexity of the matrix eigenproblem. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 507-516, 1999. Google Scholar
  37. Jean-Louis Roch and Gilles Villard. Fast parallel computation of the jordan normal form of matrices. Parallel processing letters, 6(02):203-212, 1996. Google Scholar
  38. Murray Rosenblatt. A multi-dimensional prediction problem. Arkiv för matematik, 3(5):407-424, 1958. Google Scholar
  39. Marvin Rosenblum and James Rovnyak. The factorization problem for nonnegative operator valued functions. Bulletin of the American Mathematical Society, 77(3):287-318, 1971. Google Scholar
  40. Ali H Sayed and Thomas Kailath. A survey of spectral factorization methods. Numerical linear algebra with applications, 8(6-7):467-496, 2001. Google Scholar
  41. Arne Storjohann. An o (n 3) algorithm for the frobenius normal form. In Proceedings of the 1998 international symposium on Symbolic and algebraic computation, pages 101-105, 1998. Google Scholar
  42. Arne Storjohann. Deterministic computation of the frobenius form. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 368-377. IEEE, 2001. Google Scholar
  43. Arne Storjohann. On the complexity of inverting integer and polynomial matrices. computational complexity, 24(4):777-821, 2015. Google Scholar
  44. Arne Storjohann and George Labahn. A fast las vegas algorithm for computing the smith normal form of a polynomial matrix. Linear Algebra and its Applications, 253(1-3):155-173, 1997. Google Scholar
  45. Vladimir Andreevich Yakubovich. Factorization of symmetric matrix polynomials. In Soviet Math. Dokl., volume 11(5), pages 1261-1264, 1970. Google Scholar
  46. Wei Zhou, George Labahn, and Arne Storjohann. A deterministic algorithm for inverting a polynomial matrix. Journal of Complexity, 31(2):162-173, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact