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$...
Yuval Filmus's user avatar
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.'s user avatar
  • 159k
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-...
chausies's user avatar
  • 532
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.'s user avatar
  • 159k
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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 159k
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 ...
Yuval Filmus's user avatar
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 ...
Craig Gidney's user avatar
  • 5,852
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. ...
Nicholas Mancuso's user avatar
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.'s user avatar
  • 159k
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.'s user avatar
  • 159k
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.'s user avatar
  • 159k
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. ...
gnasher729's user avatar
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\...
John L.'s user avatar
  • 39k
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 ...
Ariel's user avatar
  • 13.4k
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. ...
Yuval Filmus's user avatar
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.'s user avatar
  • 159k
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 ...
TilmannZ's user avatar
  • 764
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-...
Yuval Filmus's user avatar
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 ...
rphv's user avatar
  • 1,624
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, ...
Yuval Filmus's user avatar
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 &...
Lemming's user avatar
  • 131
3 votes

Alternatives to SVD for rank factorization

The proper search term in scientific journals is "Rank-Revealing Decomposition". If You want some theoretic guarantees on numeric accuracy/stability, the search term would be "Strong ...
DirkT's user avatar
  • 991
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 ...
matteyas's user avatar
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, ...
Ralph B.'s user avatar
  • 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 ...
orlp's user avatar
  • 13.4k
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.'s user avatar
  • 159k
3 votes

Could a quantum computer perform linear algebra faster than a classical computer?

Here are some pointers: Quantum algorithm for linear systems of equations by Harrow, Hassidim, and Lloyd. This paper shows how to solve sparse systems of linear equations very quickly. Quantum ...
Yuval Filmus's user avatar
3 votes

Fastest way to solve a system of linear equations

The best way to solve big linear equations is to use parallelisation or somehow to distribute computations among CPUs or so. See CUDA, OpenCL, OpenMP. A lot of people suggests ...
Oleg Kovalov's user avatar
3 votes
Accepted

Conditions for Linear Diophantine Equations to always have a solution

Short answer: No. Most likely, no useful constraint exists; and it can't be tested in polynomial time. Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP. In ...
D.W.'s user avatar
  • 159k

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