Dynamic matrix rank
type: Item
instance of: scholarly article
title: Dynamic matrix rank
zbMATH Open document ID: 1176.65052
author: Gudmund S. Frandsen
author: Peter Frands Frandsen
published in: Theoretical Computer Science
publication date: 2009-09-29T00:00:00Z
review text: The authors consider the problem for maintaining information about the rank of a matrix under changes of the entries. For \(n \times n\) matrices, an upper bound of \(O(n^{1.575})\) arithmetic operations and a lower bound of \(O(n)\) arithmetic operations per element change are derived. It is shown that the upper bound is valid when changing up to \(O(n^{0.575})\) entries in a single column of the matrix. An algorithm is presented that maintains the rank using \(O(n^{2})\) arithmetic operations per rank one update. The upper bounds are valid for arbitrary fields, whereas the lower bound is valid for arbitrary closed fields. The upper bound for element updates uses a fast rectangular matrix multiplication, and the lower bound involves a further development of an earlier technique for proving lower bounds for dynamic computation of rational functions.
reviewed by: Petko Hr. Petkov
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A03
zbMATH DE Number: 5608805
zbMATH Keywords: matrix rank
zbMATH Keywords: dynamic algorithms
zbMATH Keywords: lower bounds
zbMATH Keywords: upper bound
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.06.012
OpenAlex ID: W1998812252
cites work: Q5185900
cites work: Unitäre Transformationen großer Matrizen
cites work: Fast algorithms for the characteristic polynomial
cites work: Q4331740
cites work: Matrix multiplication via arithmetic progressions
cites work: Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
cites work: Lower bounds for dynamic algebraic problems
cites work: Q2934589
cites work: Dynamic matrix rank with partial lookahead
cites work: Dynamic Normal Forms and Dynamic Characteristic Polynomial
cites work: Algebraic Graph Algorithms
cites work: Maximum rank matrix completion
cites work: Deterministic network coding by matrix completion
cites work: Fast rectangular matrix multiplication and applications
cites work: The design of dynamic data structures
DOI: 10.1016/J.TCS.2009.06.012
description: scientific article; zbMATH DE number 5608805