# Tag Info

### 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$...
• 277k
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$ ...
• 159k

### 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-...
• 532
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 ...
• 159k
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 ...
• 277k
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 ...
• 159k

### 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 ...
• 277k
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,852
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,877

### 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 ...
• 159k
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 ...
• 159k

### 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 ...
• 159k

### 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. ...
• 30k
Accepted

• 131

### 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 ...
• 991
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
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

### 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 ...
• 13.4k
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 ...
• 159k

### 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 ...
• 277k

### 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 ...
• 131