25

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random vectors. This method reduces the time complexity from $O(n^{2.3729}$) (regular matrix multiplication) to $O(n^2)$ with high probability. In your case, the matrices $...


17

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 ...


13

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. ...


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.)


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

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. ...


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 ...


8

tl;dr: You can make a rough probabilistic judgement in $O(1)$ time Let's assume you are willing to settle on a test which differentiates "good" matrices $A,B$ from "pretty bad" $A,B$, in the following sense: If $A \times B = I$, the test will accept with high probability. If $A \times B$ is far* from $I$ , the test will reject with high ...


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

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 ...


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 ...


6

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. ...


6

Hint #1: Hint #2:


6

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem: While the proof of theorem (1.1.13) is somewhat involved, the ...


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

Valiant proved that the permanent is $\# P$-complete, which means that an efficient algorithm for computing the permanent can be used to solve any problem in $\# P$, such as counting the number of satisfying assignment to a CNF, the number of Hamiltonian circuits, the number of $k$-colorings and so on. In particular, it could be used to solve NP-complete ...


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

It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings". Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M) = M \cdot M^\dagger$. Consider that: $\mathfrak{F}(A + B) = (A+B) \cdot (A+B)^\dagger = AA^\dagger + BB^\dagger + A B^\dagger + B A^\dagger$ $\mathfrak{F}(A ...


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

There is what you want to achieve, and there is reality, and sometimes they are in conflict. First you check if your problem is a special case that can be solved quicker, for example a sparse matrix. Then you look for faster algorithms; LU decomposition will end up a bit faster. Then you investigate what Strassen can do for you (which is not very much; it ...


5

First of all, it is correct and important to know that optimal solutions need not necessarily be unique! However, this doesn't mean we cannot have optimal substructure. Recall what optimal substructure means: the structure is such that if we know to make an 'optimal' decision on some 'local' criterion, we can get the actual 'global' optimum by making such ...


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 ...


4

You can generate parameters for the PRNG using the provided program tinymt32dc. You should generate these parameters once and for all for each application. Each time you call the PRNG, you use the same parameters but a different seed. The reason that you don't want to vary the parameters is that generating them is (apparently) time consuming, while ...


4

I think you have a misconception. SVM does not necessarily give the latter 58 features a weight of 58/59. Rather, SVM learns what weights to use for each feature, based upon what helps it build the best classifier. So, just use those features and train with them. Don't try to find a way to manually provide different weights for the features; SVM training ...


4

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 ...


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