1 Search Results for "Casacuberta, Sílvia"


Document
Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

Authors: Sílvia Casacuberta and Rasmus Kyng

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
We improve the current best running time value to invert sparse matrices over finite fields, lowering it to an expected O(n^{2.2131}) time for the current values of fast rectangular matrix multiplication. We achieve the same running time for the computation of the rank and nullspace of a sparse matrix over a finite field. This improvement relies on two key techniques. First, we adopt the decomposition of an arbitrary matrix into block Krylov and Hankel matrices from Eberly et al. (ISSAC 2007). Second, we show how to recover the explicit inverse of a block Hankel matrix using low displacement rank techniques for structured matrices and fast rectangular matrix multiplication algorithms. We generalize our inversion method to block structured matrices with other displacement operators and strengthen the best known upper bounds for explicit inversion of block Toeplitz-like and block Hankel-like matrices, as well as for explicit inversion of block Vandermonde-like matrices with structured blocks. As a further application, we improve the complexity of several algorithms in topological data analysis and in finite group theory.

Cite as

Sílvia Casacuberta and Rasmus Kyng. Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{casacuberta_et_al:LIPIcs.ITCS.2022.33,
  author =	{Casacuberta, S{\'\i}lvia and Kyng, Rasmus},
  title =	{{Faster Sparse Matrix Inversion and Rank Computation in Finite Fields}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{33:1--33:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.33},
  URN =		{urn:nbn:de:0030-drops-156290},
  doi =		{10.4230/LIPIcs.ITCS.2022.33},
  annote =	{Keywords: Matrix inversion, rank computation, displacement operators, numerical linear algebra}
}
  • Refine by Author
  • 1 Casacuberta, Sílvia
  • 1 Kyng, Rasmus

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Matrix inversion
  • 1 displacement operators
  • 1 numerical linear algebra
  • 1 rank computation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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