31
There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for it comes from Coppersmith's paper "Rapid multiplication of rectangular matrices", but the explanation for why it leads to $N^2 \operatorname{polylog}\left(N\...
20
The decision versions of many common problems in linear algebra over the integers (or rationals)
are in the class $\mathsf{DET}$, see the paper
Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)
$\mathsf{DET}$ is contained in $\mathsf{DSPACE}(...
17
De Groote (On Varieties of Optimal Algorithms for the Computation of Bilinear Mappings. II. Optimal Algorithms for 2x2-Matrix Multiplication. Theor. Comput. Sci. 7: 127-148, 1978) proves that there is only one algorithm to multiply $2 \times 2$-matrices with 7 multiplications up to equivalence. This might be a unique feature of $2 \times 2$-matrix ...
17
Your question is equivalent to whether $A_1, \dotsc, A_k$ generate a nilpotent algebra, which in turn is equivalent to each of the $A_i$ being nilpotent. Hence not only is it decidable, but in $\tilde O(n^{2 \omega})$ time where $\omega$ is the exponent of matrix multiplication.
Let $\mathcal{A}$ be the associative algebra generated by the $A_i$: that is, ...
16
The space usage is at most $O(n^2)$ for all Strassen-like algorithms (i.e. those based on upper bounding the rank of matrix multiplication algebraically). See Space complexity of Coppersmith–Winograd algorithm
However, I realized in my previous answer that I did not explain why the space usage is $O(n^2)$... so here goes something hand-wavy. Consider what a ...
14
The conjecture fails over $\mathbb{F}_2$. Look at $M(x, y) = \langle x, y \rangle \bmod 2$, and $x, y \in \{0, 1\}^n$. The communication complexity is $\Omega(n)$, but the rank of $M$ over $\mathbb{F}_2$ is $n$, by the linearity of inner product.
14
I think the answer to your first question is also $\widetilde O(n^3 \log( \|A\| + \|b\|))$ due to the following arguments: Edmonds' paper does not describe a variant of Gaussian elimination but it proves that any number computed in a step of the algorithm is a determinant of some submatrix of A. By Schrijver's book on Theory of Linear and Integer Programming ...
14
You ask why database aggregations have monoidal structure.
Say we want to combine data values $a$ and $b$, but want to keep things general -- these may be integers, strings, floating point numbers, vectors, matrices, probability distributions, sets, or anything else we want to store and manipulate. So we denote the "aggregation" of $a$ and $b$ by $a.b$.
...
13
Take a look at https://www.sciencedirect.com/science/article/pii/S0022000008001141 "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your questions:
(1) Open
(2) $\oplus L = L$
(3) Yes
13
Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of Coppersmith-Winograd) - would "simply" produce a family of algorithms $A_\epsilon$ running in time $O(n^{2+\epsilon})$. So to have a single algorithm which ran in $O(n^2 ...
12
There is some sort of explanation in the book Algebraic Complexity Theory by Bürgisser, Clausen and Shokrollahi (p. 11-12). The idea is to start with two bases $A_0,A_1,A_2,A_3$ and $B_0,B_1,B_2,B_3$ of the space of $2\times 2$ real matrices which satisfy the following property: $A_iB_j \in \{0,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3\}$. Furthermore, $A_0 = B_0$. To ...
12
The exponent of computing a basis of the kernel is the same
as the exponent of matrix multiplication, see the
book Algebraic Complexity Theory by Bürgisser, Clausen & Shokrollahi.
So it can be done in time $O(n^{2.38})$.
12
For matrices of sizes $k = 2,3$ the Matrix Powering Positivity Problem is in $\mathsf{P}$ (cf. this paper to appear in STACS 2015)
12
I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in the first-order theory of the rationals with addition and order. You have that $P_1$ is included in $P_2$ if and only if
\begin{align*}
\Phi :=
\forall \vec{x}....
12
Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$
Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn ...
12
There is a very neat randomized algorithm by Cheung, Kwok, and Lau, which computes the rank of an $n\times m$ matrix $A$, $n\le m$, in time $O(\mathrm{nnz}(A) + \min\{n^\omega, n\cdot\mathrm{nnz}(A)\})$. Here $\mathrm{nnz}(A)$ is the number of nonzero elements of $A$, and $\omega$ is the matrix multiplication exponent. Not quite what you are asking for, but ...
11
Matrices A and B whose elements are in a field F are similar (in F) if and only if they have the same Frobenius normal form. According to a quick search, it seems that the Frobenius normal form of an n×n matrix can be computed with O(n3) field operations [Sto98], and that this can be improved to something comparable to the complexity of matrix ...
11
This is a paper that seems to improve upon the result. https://arxiv.org/pdf/1209.3995.pdf
11
Josh Alman showed some cool lower bound results of MM, which won CCC 2019 best student paper award!
http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf
10
The fastest way to multiply dense matrices on a modern computer is to call BLAS.
10
The approach you're describing is the generating function approach. By solving systems of polynomial equations, one can calculate the number of words of given length (generated by any non-terminal), and through it the corresponding asymptotics.
For regular languages one can directly use linear algebra to estimate the number of words of given length. The ...
9
As others have said, there's no point in reinventing the wheel.
If you must implement it yourself for whatever reason, then you should either go for the naïve or Strassen algorithm. Naïve is faster for smaller matrices, but as matrix size increases to ~100 you will find that the Strassen algorithm starts to perform better as the impact of the larger ...
9
It is known that the number of arithmetic operations necessary to compute the determinant of an $n\times n$ matrix is $n^{\omega+o(1)}$, where $\omega$ is the matrix multiplication constant. See for example this table on Wikipedia, as well as its footnotes and references. Note that the asymptotic complexity of matrix inversion is also the same as matrix ...
8
You can do this in uniform NC, see:
G. Villard. Fast parallel algorithms for matrix reduction to canonical forms. AAECC 8:511-537, 1997. http://link.springer.com/article/10.1007%2Fs002000050089
8
No. Suppose all $a_i$'s are $0$ and all your $b_i$'s are equal; then the polytopes you can get by varying the $b_i$'s are essentially the hypersimplices. But the number of vertices of an $n$-dimensional hypersimplex can be any binomial coefficient $\binom{n}{k}$. In particular choosing $k=n/2$ gives an exponential number of extreme points.
8
No.
Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. Computing $AB^T$ from $A$, $B$ and $AB$ means computing $XY^T$ from $X$ and $Y$, since $AB = 0$
8
The paper by Raghavendra is now also published and available here under the title:
Correlation Decay and Tractability of CSPs, appeared in the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
A related article has appeared in the Electronic Colloquium on Computational Complexity, Report No. 7 (2015), available here.
8
The revised conjecture is true, even under relaxed constraints on $S$ and $t$—they may be arbitrary integer vectors (as long as the set $S$ is finite). Notice that if we arrange the vectors from $S$ into a matrix, the question simply asks about the solvability of the linear system
$$Sx=t$$
in the integers, hence I will formulate the problem as such below.
...
8
When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$).
Recently I and Ryan Williams have an (unpublic yet) work showing that when $d = O(\log n)$, OVP and a bichromatic version of Max-IP (given $A,B$, find $\max_{(a,b) \in A \...
7
EDIT: My original proof had a bug. I now believe that it is fixed.
We reduce the problem of EQUAL SUM SUBSETS to this problem. EQUAL SUM SUBSETS is the problem of: given a set of $m$ integers, find two disjoint subsets which have the same sum. EQUAL SUM SUBSETS is known to be NP-complete.
Suppose these bit strings were not vectors but representations of $n$...
Only top voted, non community-wiki answers of a minimum length are eligible
