Abstract
Let A in {0,1}^{n x n} be a matrix with z zeroes and u ones and x be an ndimensional vector of formal variables over a semigroup (S, o). How many semigroup operations are required to compute the linear operator Ax?
As we observe in this paper, this problem contains as a special case the wellknown range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute Ax using O(u) semigroup operations. The main question studied in this paper is: can Ax be computed using O(z) semigroup operations? We prove that in general this is not possible: there exists a matrix A in {0,1}^{n x n} with exactly two zeroes in every row (hence z=2n) whose complexity is Theta(n alpha(n)) where alpha(n) is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an O(z) upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory.
As a simple application of the presented linearsize construction, we show how to multiply two n x n matrices over an arbitrary semiring in O(n^2) time if one of these matrices is a 0/1matrix with O(n) zeroes (i.e., a complement of a sparse matrix).
BibTeX  Entry
@InProceedings{kulikov_et_al:LIPIcs:2019:11513,
author = {Alexander S. Kulikov and Ivan Mikhailin and Andrey Mokhov and Vladimir Podolskii},
title = {{Complexity of Linear Operators}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {17:117:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11513},
URN = {urn:nbn:de:0030drops115137},
doi = {10.4230/LIPIcs.ISAAC.2019.17},
annote = {Keywords: algorithms, linear operators, commutativity, range queries, circuit complexity, lower bounds, upper bounds}
}
Keywords: 

algorithms, linear operators, commutativity, range queries, circuit complexity, lower bounds, upper bounds 
Collection: 

30th International Symposium on Algorithms and Computation (ISAAC 2019) 
Issue Date: 

2019 
Date of publication: 

28.11.2019 