13
votes
It is possible to implement a *greater than* function using only addition, substractions and multiplications?
Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$.
Indeed, as you mention, $1-x^{q-1} = [\![x=0]\!]$ is a polynomial that equals $1$...
- 275k
13
votes
Accepted
Fastest way to solve a system of linear equations
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$ ...
D.W.♦
- 154k
12
votes
Inverting a band matrix
Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did).
Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-...
- 512
12
votes
Accepted
Why is the probability of a false positive not 0 for Freivald's Algorithm?
Algorithms can't work over $\mathbb{R}^n$, as you can't represent real numbers in finite space. Also, you can't pick a number uniformly at random from $\mathbb{R}$. Instead, usually we work over a ...
D.W.♦
- 154k
11
votes
Accepted
Minimal basis for set of binary vectors using XOR
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 ...
- 275k
8
votes
Accepted
Solving systems of linear equations over semirings
I don't think there's any general algorithm that works for arbitrary semirings. The requirement to be a semiring doesn't give us a lot to work with.
However, if you have a closed semiring, then there ...
D.W.♦
- 154k
8
votes
Automated optimization of 0-1 matrix vector multiplication
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$ ...
- 156
7
votes
Suitable choice for moderate-size square matrix multiplication?
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 ...
- 275k
6
votes
Accepted
Unfeasible linear program becomes feasible if a variable is removed
There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a ...
- 13.1k
5
votes
Accepted
Closed form solution for optimization problem
There is a closed-form solution to your problem, but first it helps to know two facts to derive the minimizer. The first fact is that we can re-write the Frobenius norm squared as a trace operation. ...
- 3,857
5
votes
Proving complexity of computing product of matrices
I'm afraid you can't. As I mentioned in my response to your previous question:
The complexity of a problem is the running time of the fastest algorithm for that problem.
There exist algorithms ...
D.W.♦
- 154k
5
votes
Accepted
Computing Von Neumann Entropy Efficiently
A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating $x \lg x$ with a polynomial. Then you can use the trace of powers of the matrix ...
- 5,802
5
votes
Accepted
Automated optimization of 0-1 matrix vector multiplication
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 ...
- 9,385
5
votes
Accepted
Positive Definiteness Constraint
A matrix $A$ is positive semidefinite if and only if there exists a matrix $V$ such that $$A = V^\top V.$$
So, you can use the entries of $V$ as your unknowns, and express each entry of $A$ as a ...
D.W.♦
- 154k
5
votes
How to find subset of vectors whose sum has certain characteristics
The question has changed. I'll answer the updated question. Here are three candidate algorithms; the first is faster than $O(m^n)$ time, and the second might be faster as well for some parameter ...
D.W.♦
- 154k
5
votes
Fastest way to solve a system of linear equations
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. ...
- 27.8k
5
votes
Accepted
Transforming a byte with a subset of a small, fixed set of values and xor into any other value
You have recalled the correct category, "linear-algebra".
Let us see how we can interpret xor in the terms of linear-algebra. Here is the computation rules for xor.
$$0\oplus0=0$$
$$0\oplus1=1$$
$$1\...
- 38.5k
4
votes
Accepted
Inputting a superposition into a cNOT gate
This is more of a question on linear algebra rather than a question about quantum computation. You should probably have a firm grip on basic linear algebra (vector spaces, linear operators, inner ...
- 13.3k
4
votes
Accepted
Clarification regarding linear boolean functions!
A function satisfies $f(x \oplus y) = f(x) \oplus f(y)$ for all $x,y$ iff it is of the form
$$
f(x) = c_1 x_1 \oplus \cdots \oplus c_n x_n.
$$
Indeed, all functions of this form satisfy the identity. ...
- 275k
3
votes
Accepted
How to construct a running kd-tree?
How about a bitwise trie? For 3D, you would interleave the bits of your three values into a single bitstrings, which could be used as a binary key.
The maximum depth is determined by the number of ...
- 729
3
votes
Accepted
How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?
"Blocked matrix multiplication" is one way to optimize matrix multiplication for memory access.
From "Using Blocking to Increase Temporal Locality" by Bryant and O’Hallaron (2012):
Blocking a ...
- 1,604
3
votes
Linear equation solving with special sparse coefficient matrix
There are iterative methods in which each iteration takes time $O(nnz)$, where $nnz$ is the number of non-zero entries. See for example Chapter 4 of Saad's lecture notes. For the state-of-the-art, ...
- 275k
3
votes
Accepted
Rank of random binary matrix subset
The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-...
- 275k
3
votes
Partially diagonalizing a matrix
In general $U$ will only be unitary if your composed matrix is hermitian.
I will answer the more general problem that the matrix is partially diagonalizable:
$$U^{-1} \begin{pmatrix}A & B \\ C &...
- 131
3
votes
Accepted
Locality-sensitive hashing random projection
No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The ...
D.W.♦
- 154k
3
votes
Accepted
Matrix chain multiplication and exponentiation
Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided.
The problem reduces to finding the most efficient ordering when considering the square of ...
- 46
3
votes
Accepted
Time complexity of matrix multiplication in Big-Align
D.W. is absolutely right about the time complexity for $\bf X$. Meanwhile, I think the paper is vague on what they are saying and not exact on the complexity.
The paper is about network alignment, ...
- 239
3
votes
Gauss-Jordan using stacks and list
What you want is called indirection. Instead of physically moving the rows/columns, you move their names.
Let's say I call row 1 r[0], and row 3 ...
- 12.6k
3
votes
Accepted
Absorbing Markov Chains: An efficient algorithmic approach
There are several possible techniques.
Let $P^t$ denote the matrix $P$ raised to the $t$th power. Then $(P^t)_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start ...
D.W.♦
- 154k
Only top scored, non community-wiki answers of a minimum length are eligible