Fast multiplication of matrices over a finitely generated semiring

In this paper we show that n×n matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q²nω), where nω is the complexity for matrix multiplication over a ring (Strassen: ω<2.807, Coppersmith and Winograd: ω<2.376).We first present a combinatorial matrix multiplication algorithm for the case of semirings with q elements, with complexity , matching the best known methods in this class.Next we show how the ideas used can be combined with those of the fastest known boolean matrix multiplication algorithms to give an O(q²nω) algorithm for matrices of, not necessarily finite, semirings with q additive generators.For finite semirings our combinatorial algorithm is simple enough to be a practical algorithm and is expected to be faster than the O(q²nω) algorithm for matrices of practically relevant sizes.     

Rigidity of a simple extended lower triangular matrix

For the all-ones lower triangular matrices, the upper and lower bounds on rigidity are known to match [P. Pudlak, Z. Vavrin, Computation of rigidity of order n²/r for one simple matrix, Comment Math. Univ. Carolin. 32 (2) (1991) 213-218]. In this short note, we apply these techniques to the all-ones extended lower triangular matrices, to obtain upper and lower bounds with a small gap between the two; we show that the rigidity is .     

Query-Efficient Locally Decodable Codes of Subexponential Length

A k-query locally decodable code (LDC) C : Σ ⁿ → Γ ^N encodes each message x into a codeword C(x) such that each symbol of x can be probabilistically recovered by querying only k coordinates of C(x), even after a constant fraction of the coordinates has been corrupted. Yekhanin (in J ACM 55:1–16, 2008) constructed a 3-query LDC of subexponential length, N = exp(exp(O(log n/log log n))), under the assumption that there are infinitely many Mersenne primes. Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) constructed a 3-query LDC of length ${N_{2}={\rm exp}({\rm exp} (O(\sqrt{\log n\log\log n})))}$ with no assumption, and a 2 ^r -query LDC of length ${N_{r}={\rm exp}({\rm exp}(O(\sqrt[r]{\log n(\log \log n)^{r-1}})))}$ , for every integer r ≥ 2. Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010) gave a composition method in Efremenko’s framework and constructed a 3 · 2 ^r-2-query LDC of length N _r , for every integer r ≥ 4, which improved the query complexity of Efremenko’s LDC of the same length by a factor of 3/4. The main ingredient of Efremenko’s construction is the Grolmusz construction for super-polynomial size set-systems with restricted intersections, over ${\mathbb{Z}_m}$ , where m possesses a certain “good” algebraic property (related to the “algebraic niceness” property of Yekhanin in J ACM 55:1–16, 2008). Efremenko constructed a 3-query LDC based on m = 511 and left as an open problem to find other numbers that offer the same property for LDC constructions. In this paper, we develop the algebraic theory behind the constructions of Yekhanin (in J ACM 55:1–16, 2008) and Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009), in an attempt to understand the “algebraic niceness” phenomenon in ${\mathbb{Z}_m}$ . We show that every integer m =  pq = 2 ^t ?1, where p, q, and t are prime, possesses the same good algebraic property as m = 511 that allows savings in query complexity. We identify 50 numbers of this form by computer search, which together with 511, are then applied to gain improvements on query complexity via Itoh and Suzuki’s composition method. More precisely, we construct a ${3^{\lceil r/2\rceil}}$ -query LDC for every positive integer r < 104 and a ${\left\lfloor (3/4)^{51} \cdot 2^{r}\right\rfloor}$ -query LDC for every integer r ≥ 104, both of length N _r , improving the 2 ^r queries used by Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) and 3 · 2 ^r-2 queries used by Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010). We also obtain new efficient private information retrieval (PIR) schemes from the new query-efficient LDCs.     

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 ₁,j ₁),(i ₂,j ₂),…?, 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.     

A locally optimized reordering algorithm and its application to a parallel sparse linear system solver

A coarse-grain parallel solver for systems of linear algebraic equations with general sparse matrices by Gaussian elimination is discussed. Before the factorization two other steps are performed. A reordering algorithm is used during the first step in order to obtain a permuted matrix with as many zero elements under the main diagonal as possible. During the second step the reordered matrix is partitioned into blocks for asynchronous parallel processing (normally the number of blocks is equal to the number of processors). It is possible to obtain blocks with nearly the same number of rows, because there is no requirement to produce square diagonal blocks. The first step is much more important than the second one and has a significant influence on the performance of the solver. A straightforward implementation of the reordering algorithm will result inO(n ²) operations. By using binary trees this cost can be reduced toO(NZ logn), whereNZ is the number of non-zero elements in the matrix andn is its order (normallyNZ is much smaller thann ²). Some experiments on parallel computers with shared memory have been performed. The results show that a solver based on the proposed reordering performs better than another solver based on a cheaper (but at the same time rather crude) reordering whose cost is onlyO(NZ) operations.     

On the Complexity of Matrix Rank and Rigidity

We revisit a well studied linear algebraic problem, computing the rank and determinant of matrices, in order to obtain completeness results for small complexity classes. In particular, we prove that computing the rank of a class of diagonally dominant matrices is complete for L\textsf{L} . We show that computing the permanent and determinant of tridiagonal matrices over ℤ is in Gap NC¹\textsf {Gap} \textsf {NC}^{1} and is hard for NC¹\textsf {NC}^{1} . We also initiate the study of computing the rigidity of a matrix: the number of entries that needs to be changed in order to bring the rank of a matrix below a given value. We show that some restricted versions of the problem characterize small complexity classes. We also look at a variant of rigidity where there is a bound on the amount of change allowed. Using ideas from the linear interval equations literature, we show that this problem is NP\textsf {NP} -hard over ℚ and that a certain restricted version is NP\textsf {NP} -complete. Restricting the problem further, we obtain variations which can be computed in PL\textsf {PL} and are hard for C₌L\textsf {C}_{=}\textsf {L} .     

Graph Complexity and Slice Functions

Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, Rödl, and Savický [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(?) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of $\exp((\log \log n)^{\omega(1)})$ would give an explicit language outside the class Σ ₂ ^cc of the two-party communication complexity as defined by Babai, Frankl, and Simon [BFS]. Our lower bound proof is based on sign-representing polynomials for DNFs and lower bounds on ranks of ±1 matrices even after being subjected to sign-preserving changes to their entries. For the former, we use a result of Nisan and Szegedy [NS] and an idea from a recent result of Klivans and Servedio [KS]. For the latter, we use a recent remarkable lower bound due to Forster [F1].     

Moduli and canonical forms for linear dynamical systems II: The topological case

In this paper we study real linear dynamical systems \(\dot x = Fx + Gu,y = Hx,x \in R^n \) = state space,u ∈ R ^m = input space,y ∈ R ^p = output space, under the equivalence relation induced by base change in state space; or in other words we study triples of matrices with real coefficients (F, G, H) of sizesn × n, n × m, p × n respectively, under the action(F, G, H.) →(TFT ^?1,TG, HT ^?1) ofGL _n (R), the group of invertible realn × n matrices. One of the central questions studied is: “do there exist continuous canonical forms for this equivalence relation?”. After various trivial obstructions to the existence of such forms have been removed the answer is very roughly: no ifm ≥ 2, p ≥ 2, yes ifm = 1, orp = 1. For a precise statement cf. theorem 1.7. Existence or nonexistence of continuous canonical forms is related to the existence of a universal family of real linear dynamical systems. More precisely continuous canonical forms exist if such a universal family exists and if the underlying vector bundle of this family is the trivial vector bundle. In the case studied we show that a universal family in the appropriate sense does exist. The methods used are purely (differential) topological and in particular do not involve any algebraic geometry. There is a corresponding algebraic theory over any fieldk instead ofR which is the subject of part III of this series of papers.     

Better Size Estimation for Sparse Matrix Products

We consider the problem of doing fast and reliable estimation of the number z of non-zero entries in a sparse boolean matrix product. This problem has applications in databases and computer algebra. Let n denote the total number of non-zero entries in the input matrices. We show how to compute a 1±ε approximation of z (with small probability of error) in expected time for any $\varepsilon> 4/\sqrt[4]{z}$ . The previously best estimation algorithm, due to Cohen (J. Comput. Syst. Sci. 53(3):441–453, 1997), uses time . We also present a variant using I/Os in expectation in the cache-oblivious model. In contrast to these results, the currently best algorithms for computing a sparse boolean matrix product use time ω(n ^4/3) (resp. ω(n ^4/3/B) I/Os), even if the result matrix is restricted to nonzero entries. Our algorithm combines the size estimation technique of Bar-Yossef et al. (Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM ’02), pp. 1–10, 2002) with a particular class of pairwise independent hash functions that allows the sketch of a set of the form to be computed in expected time and I/Os. We then describe how sampling can be used to maintain (independent) sketches of matrices that allow estimation to be performed in time o(n) if z is sufficiently large. This gives a simpler alternative to the sketching technique of Ganguly et al. (Proceedings of the 24th ACM Symposium on Principles of Database Systems (PODS ’05), pp. 259–270, 2005), and matches a space lower bound shown in that paper. Finally, we present experiments on real-world data sets that show the accuracy of both our methods to be significantly better than the worst-case analysis predicts.     

Fast Computation of the Bezout and Dixon Resultant Matrices

Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon–Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas requireO (n³) additions and multiplications to compute all the entries of the Bezout resultant matrix. Here we present a new recursive algorithm for computing these entries that uses onlyO (n²) additions and multiplications. The improvement is even more dramatic in the bivariate setting. Established techniques based on explicit formulas requireO (m⁴n⁴) additions and multiplications to calculate all the entries of the Dixon–Cayley resultant matrix. In contrast, our recursive algorithm for computing these entries uses onlyO (m²n³) additions and multiplications.     

Algorithmic aspects of Suslin's proof of Serre's conjecture

LetF be a unimodularr×s matrix with entries beingn-variate polynomials over an infinite fieldK. Denote by deg(F) the maximum of the degrees of the entries ofF and letd=1+deg(F). We describe an algorithm which computes a unimodulars×s matrixM with deg(M)=(rd) ^O(n) such thatFM=[I _r ,O], where [I _r ,O] denotes ther×s matrix obtained by adding to ther×r unit matrixI _r s–r zero columns.We present the algorithm as an arithmetic network with inputs fromK, and we count field operations and comparisons as unit cost.The sequential complexity of our algorithm amounts to field operations and comparisons inK whereas its parallel complexity isO(n ⁴ r ⁴log²(srd)).The complexity bounds and the degree bound for deg(M) mentioned above are optimal in order. Our algorithm is inspired by Suslin's proof of Serre's Conjecture.     

A Case Where Choosing a Product Order Makes the Calculations of a Groebner Basis Much Faster

Let X and Y be generic n by n matrices of indeterminates. Let S = k[x₁,…, x_r , y₁,…, y_r] where k is a field of characteristic 0 and r = n² . Let I ⊂ S be the ideal generated by the entries of the matrix XY - YX. We will consider the ring S/I and show that it is Cohen-Macaulay for the case n = 4. In order to calculate its Groebner basis we use a product order with 3 blocks of variables and reverse lexicographic order in each block. This makes the computation much smaller and less time consuming.     

Fractal-like Matrices

We introduce special sparse n×n-matrices (n=2 ^k ) containing up to 3 ^k ≈n ^1.585 nonzero elements. Their structure is inherited from the famous Sierpinski triangle and is not sensitive to matrix multiplication and inversion. The arithmetical complexity of taking product or inverse of such matrices is proved to be O(n ²).     

On the recognition of permuted Supnick and incomplete Monge matrices

Incomplete Monge matrices are a generalization of standard Monge matrices: the values of some entries are not specified and the Monge property only must hold for all specified entries. We derive several combinatorial properties of incomplete Monge matrices and prove that the problem of recognizingpermuted incomplete Monge matrices is NP-complete. For the special case of permutedSupnick matrices, we derive a fast recognition algorithm and thereby identify a special case of then-vertex travelling salesman problem which can be solved inO(n ²logn) time.     

Negation-Limited Complexity of Parity and Inverters

In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. We give improved lower bounds for the size (the number of AND/OR/NOT) of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x ₁,…,x _n and outputs ¬ x ₁,…,¬ x _n . We show that: (a) for n=2 ^r ?1, circuits computing Parity with r?1 NOT gates have size at least 6n?log?₂(n+1)?O(1), and (b) for n=2 ^r ?1, inverters with r NOT gates have size at least 8n?log?₂(n+1)?O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x ₁≥???≥x _n . For an arbitrary r, we completely determine the minimum size. It is 2n?r?2 for odd n and 2n?r?1 for even n for ?log?₂(n+1)??1≤r≤n/2, and it is ?3n/2??1 for r≥n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n?3r for ?log?₂(n+1)?≤r≤n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments in a somewhat novel way.     

Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.     

Trimmed Moebius Inversion and Graphs of Bounded Degree

We study ways to expedite Yates’s algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an n-element universe U and a family ? of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of U with k sets from ? in time within a polynomial factor (in n) of the number of supersets of the members of ?. Relying on an projection theorem of Chung et al. (J. Comb. Theory Ser. A 43:23–37, 1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs with maximum degree Δ. In particular, we show how to compute the domatic number in time within a polynomial factor of (2^Δ+1?2) ^n/(Δ+1) and the chromatic number in time within a polynomial factor of (2^Δ+1?Δ?1) ^n/(Δ+1). For any constant Δ, these bounds are O((2?ε) ⁿ ) for ε>0 independent of the number of vertices n.     

On Minimum Witnesses for Boolean Matrix Multiplication

Minimum witnesses for Boolean matrix multiplication play an important role in several graph algorithms. For two Boolean matrices A and B of order n, with one of the matrices having at most m nonzero entries, the fastest known algorithms for computing the minimum witnesses of their product run in either O(n ^2.575) time or in O(n ²+mnlog(n ²/m)/log² n) time. We present a new algorithm for this problem. Our algorithm runs either in time $$\tilde{O}\bigl(n^{\frac{3}{4-\omega}}m^{1-\frac{1}{4-\omega }}\bigr) $$ where ω<2.376 is the matrix multiplication exponent, or, if fast rectangular matrix multiplication is used, in time $$O\bigl(n^{1.939}m^{0.318}\bigr). $$ In particular, if ω?1<α<2 where m=n ^α , the new algorithm is faster than both of the aforementioned algorithms.     

Explicit semi-direct methods based on approximate inverse matrix techniques for solving boundary-value problems on parallel processors

Generalized approximate inverse matrix techniques and sparse Gauss-Jordan elimination procedures based on the concept of sparse product form of the inverse are introduced for calculating explicitly approximate inverses of large sparse unsymmetric (n × n) matrices. Explicit first and second order semi-direct methods in conjunction with the derived approximate inverse matrix techniques are presented for solving Parabolic and Elliptic difference equations on parallel processors. Application of the new methods on a 2D-model problem is discussed and numerical results are given.     

Strong NP-completeness of a matrix similarity problem

Consider the following problem: given an upper triangular matrix A, with rational entries and distinct diagonal elements, and a tolerance τ ⩾ 1, decide whether there exists a nonsingular matrix G, with condition number bounded by τ, such that G⁻¹AG is 2 × 2 block diagonal. This problem, which we shall refer to as DICHOTOMY, is an important one in the theory of invariant subspaces. It has recently been proved that DICHOTOMY is NP-complete. In this note we make some progress proving that DICHOTOMY is actually NP-complete in the strong sense. This outlines the “purely combinatorial” nature of the difficulty, which might well arise even in case of well scaled matrices with entries of small magnitude.