Dynamic Matrix Rank with Partial Lookahead

摘要

We consider the problem of maintaining information about the rank of a matrix M under changes to its entries. For an n×n matrix M, we show an amortized upper bound of O(n~(ω-1)) arithmetic operations per change for this problem, where ω＜2.373 is the exponent for matrix multiplication, under the assumption that there is a lookahead of up to Θ(n) locations. That is, we know up to the next Θ(n) locations (i_1, j_1 ),(i_2, j_2), ..., 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. The dynamic matrix rank problem was first studied by Frandsen and Frandsen who showed an upper bound of O(n~(1.575)) and a lower bound of Ω(n) for this problem and later Sankowski showed an upper bound of O(n~(1.495)) for this problem when allowing randomization and a small probability of error. These algorithms do not assume any lookahead. For the dynamic matrix rank problem with lookahead, Sankowski and Mucha showed a randomized algorithm (with a small probability of error) that is more efficient than these algorithms.