11

Here is the pseudocode for an $O(\lg n)$ matrix exponentiation algorithm. Note that the * operator denotes ordinary matrix multiplication. MATHPOWER (M, n) if n == 1 then return M else P = MATHPOWER (M, floor(n/2)) if n mod 2 == 0 then return P * P else return P * P * M


11

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear algebra, which you probably know the solution for. (One option is Gaussian elimination.)


10

A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices. Therefore, you can find a solution to a system of $n$ linear equations in $n$ unknowns in $O(M(n))$ time. For instance, Strassen's algorithm achieves $M(n) = O(n^{2.8})$, which is faster than Gaussian elimination. ...


9

If you want to multiply two matrices $A$ and $B$ then observe that $$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}= \begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&&I_n\end{pmatrix}$$ which gives you $AB$ in the top-right block. It follows that inversion is at least hard as multiplication. EDIT: I had misread the ...


8

A partial answer to your question is the group-theoretic approach first developed by Cohn and Umans and further developed by Cohn, Kleinberg, Szegedy and Umans. It can "sort of" capture Strassen and Coppersmith-Winograd for matrix multiplication.


8

If I have understood your question correctly (an illustrative example would have been helpful), I would recommend either Gaussian blurring or linear interpolation depending on the behavior you are after. Both are simple and should perform relatively fast even on a handheld device. Linear interpolation (or rather bilinear interpolation) is simple but ...


8

This is related to an open research question, which is known as the "Online Boolean Matrix-Vector Multiplication (OMv) problem". This problem reads as follows (see [1]): Given a binary $n \times n$ matrix $M$ and $n$ binary column vectors $v_1, \dots, v_n$, we need to compute $M v_i$ before $v_{i+1}$ arrives. Notice that the problem from the question is ...


7

Matrix multiplication algorithms are analyzed in terms of arithmetic complexity. The computation model is straight-line programs with instructions of the form $a \gets b \circ c$, where $\circ \in \{ +,-,\times,\div \}$, $a$ is a variable, and $b,c$ could be either variables, inputs or constants. Additionally, certain variables are distinguished as outputs. ...


7

The short answer is no. No quick algorithm for this problem is known. A big open problem (for at least 50 years) in algebraic graph theory asks about the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a Moore graph. However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = ...


7

The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation matrices (0/1 matrices which contain precisely one 1 in each row and column). This immediately implies your result. If you don't want to assume this theorem, you ...


7

Multiple Dimensions For a recursive counterpart for matrices, we need dependent types. Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, matrices are two dimensional and so concatenation may be meaningless if the sizes do not match up. That is to say, all rows need to have the same number of ...


7

Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and list all relevant algorithms.


6

Multiplying by the $n * p$ matrix decreases the dimensionality of the data set. Think of this as projecting the highly dimensional space into a smaller dimensional space. For example, you could do principle component analysis and project it into a small space. This way things that are correlated together are projected into the same dimension and if one of ...


6

Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors are equally likely, $$ \Pr[Dr \neq 0] = \frac{G}{G+B} \geq \frac{1}{2}. $$ The last inequality is a bit of algebra I leave to you.


6

Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed by reducing set disjointness to your problem. Suppose that Alice holds a binary vector $x_1,\ldots,x_n$ and Bob holds a binary vector $y_1,\ldots,y_n$, and they ...


5

The dynamic programming solution computes a table that for each $i\le j$ has the optimal solution for $Ai$, ... $Aj$. The computation is done bottom-up, and (as one of the comments notes) many values are reused. Total complexity order $n^3$ as there is a quadratic number of $i,j$ each taking linear time to compute. A real brute force takes exponential time, ...


5

Since you just need to select $k$ rows, this becomes the same as choosing $k$ elements of a given set of $n$ elements, say $\{1,2,\dots,n\}$. You can generate $n \choose k$ combinations in lexicographic order (i.e. starting with $\{1,2,3, \dots, k\}$ and ending with $\{n-k+1, ..., n-1,n\}$), with the next one depending only on the previous one. The fact ...


5

If the matrices are stored in the usual way, that is as long vectors, then the complexity is $\Theta(n^2)$. The reason is that if all the off-diagonal entries in the matrix are different, you will need to change all of them, and there are $n^2-n$ of them.


5

There are two other algorithms which may or may not be relevant. The first algorithm diagonalizes your matrix (which is usually possible), writing it as $M = PDP^{-1}$, where $M,D$ in general may be complex-valued. You then compute $M=PD^nP^{-1}$. Note it's very easy to raise a diagonal matrix to the $n$th power. If $M$ is not diagonalizable, you find its ...


5

The classical framework is the one of bilinear algorithms and tensor rank decompositions; basically, you construct the 3-way tensor associated to the bilinear map $f(A,B) = A \cdot B$, in the basis of the coefficients, then look for a decomposition of it as a sum of rank-one tensors (i.e., those of the form $T_{i,j,k} = u_i v_j w_k$). You'll find this ...


5

There is a simple solution, but it requires a different 1D representation of your matrix $M$. You suppose it is stored in an arbitrarily long 1D array $A$, so that new elements can be added. Then the elements of the matrix $M$ are stored such that: $M[i,j]$ is stored in $A[k]$ with $k=(j-1)^2+i$ if $i\leq j$ and $k=i^2-j+1$ otherwise. Other similar ...


5

Simplifying the problem: Given a positive integer $r$ positive integers $m, n \geq 2$ a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry) determine whether it is possible to complete the given partial matrix $\mathrm A$ with values in $\{0,1\}$ such that the resulting completed matrix ...


5

If it is possible try to exploit banded tridiagonal nature of matrix. Otherwise if the matrix contains only a constant number of distinct values (which surely is being binary), you should try Mailman algorithm (by Edo Liberty, Steven W. Zucker In Yale university technical report #1402): optimized over finite dictionary Common Subexpression Elimination is ...


5

If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate: Stage 1: Calculate $M^2$ Stage 2: Calculate $M^3 = M^2 * M$ and $M^4 = M^2 * M^2$ Stage 3: Calculate $M^7 = M^4 * M^3$ and $M^8 = M^4 * M^4$ Stage 4: Calculate $M^{15} = M^8 * M^...


5

I'm assuming that items are always traded 1-for-1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?" If you are only looking for one long path, then you are looking for a Hamiltonian circuit if one exists, so the decision version of the problem is NP-complete. If ...


5

Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system of linear equations is optimal if one restricts oneself to operations upon rows and columns as a whole. The reference is to Klyuyev, V. V., and N. I. ...


4

If $AB=C$, then $A(Bx)=Cx$ for all vectors $x$. Generate vectors randomly and check. This known as Freivalds' algorithm. Wikipedia has details.


4

You have to interpolate the missing heat values. There's some mathematics that explains this pretty well (man, it's been a while) but, if I recall correctly, the correct physical way to do this (assuming no heat sources in the area being interpolated) is the following: For each pixel for which there wasn't original data, assign the value of the pixel to the ...


4

Here is an O(N3) algorithm (it is valid only for matrices of non-negative values). Compute prefix sums for each column: B[k][j] = Sum(A[0..k][j]). For each pair of row indices (p, q): Apply a two-pointers algorithm for implicit array of values B[q][j]-B[p][j]. Where a two-pointers algorithm advances first pointer while sum of values between pointers is ...


Only top voted, non community-wiki answers of a minimum length are eligible