2 Search Results for "Pernet, Clément"

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 Õ(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.
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/DagSemProc.06271.3
Adaptive Triangular System Solving

Authors: Jean-Guillaume Dumas, Clément Pernet, and Jean-Louis Roch

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
Large-scale applications and software systems are getting increasingly complex. To deal with this complexity, those systems must manage themselves in accordance with high-level guidance from humans. Adaptive and hybrid algorithms enable this self-management of resources and structured inputs. In this talk, we first propose a classification of the different notions of adaptivity. For us, an algorithm is adaptive (or a poly-algorithm) when there is a choice at a high level between at least two distinct algorithms, each of which could solve the same problem. The choice is strategic, not tactical. It is motivated by an increase of the performance of the execution, depending on both input/output data and computing resources. Then we propose a new adaptive algorithm for the exact simultaneous resolution of several triangular systems over finite fields. The resolution of such systems is e.g. one of the two main operations in block Gaussian elimination. For solving triangular systems over finite fields, the block algorithm reduces to matrix multiplication and achieves the best known algebraic complexity. Exact matrix multiplication, together with matrix factorizations, over finite fields can now be performed at the speed of the highly optimized numerical BLAS routines. This has been established by the FFLAS and FFPACK libraries. In this talk we propose several practicable variants solving these systems: a pure recursive version, a reduction to the numerical dtrsm routine and a delaying of the modulus operation. Then a cascading scheme is proposed to merge these variants into an adaptive sequential algorithm. We then propose a parallelization of this resolution. The adaptive sequential algorithm is not the best parallel algorithm since its recursion induces a dependancy. A better parallel algorithm would be to first invert the matrix and then to multiply this inverse by the right hand side. Unfortunately the latter requires more total operations than the adaptive algorithm. We thus propose a coupling of the sequential algorithm and of the parallel one in order to get the best performances on any number of processors. The resulting cascading is then an adaptation to resources. This shows that the same process has been used both for adaptation to data and to resources. We thus propose a generic framework for the automatic adaptation of algorithms using recursive cascading.
Cite as

Jean-Guillaume Dumas, Clément Pernet, and Jean-Louis Roch. Adaptive Triangular System Solving. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{dumas_et_al:DagSemProc.06271.3,
  author =	{Dumas, Jean-Guillaume and Pernet, Cl\'{e}ment and Roch, Jean-Louis},
  title =	{{Adaptive Triangular System Solving}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.3},
  URN =		{urn:nbn:de:0030-drops-7704},
  doi =		{10.4230/DagSemProc.06271.3},
  annote =	{Keywords: Adaptive and hybrid algorithms; triangular system solving; parallel and sequential degenerations}
}
  • Refine by Author
  • 1 Dey, Papri
  • 1 Dumas, Jean-Guillaume
  • 1 Kannan, Ravi
  • 1 Pernet, Clément
  • 1 Roch, Jean-Louis
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Numerical analysis

  • Refine by Keyword
  • 1 Adaptive and hybrid algorithms; triangular system solving; parallel and sequential degenerations
  • 1 Symbolic algorithms
  • 1 linear algebra
  • 1 numerical algorithms

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2006
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact