DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2022.33

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.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}
}

Search Results

Documents authored by Casacuberta, Sílvia

Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

Abstract

Cite as

Thanks for your feedback!

Could not send message