2026-07-23T13:09:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1759 2024-03-06T10:33:05Z ddc:004 open_access

Dynamic matrix rank with partial lookahead Kavitha, Telikepalli Matrix rank dynamic algorithm fast matrix multiplication We consider the problem of maintaining information about the rank of a matrix $M$ under changes to its entries. For an $n \times n$ matrix $M$, we show an amortized upper bound of $O(n^{\omega-1})$ arithmetic operations per change for this problem, where $\omega < 2.376$ is the exponent for matrix multiplication, under the assumption that there is a {\em lookahead} of up to $\Theta(n)$ locations. That is, we know up to the next $\Theta(n)$ locations $(i_1,j_1),(i_2,j_2),\ldots,$ whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Telikepalli Kavitha 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1759 urn:nbn:de:0030-drops-17594 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1759 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode