Questions tagged [linear-algebra]
Linear algebra deals with vector spaces and linear transformations.
227
questions
13
votes
1
answer
332
views
Cases of nearly linear time solvable linear systems
Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$
Solving for ${\bf x}$ through standard Gaussian Elimination ...
- 1,346
7
votes
0
answers
207
views
Are the minimal quantum and classical span programs the same?
A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity.
A span program for a function $f: \{0,1\}^n \...
- 10.2k
10
votes
1
answer
494
views
Finding a cutting plane that splits a polyhedron evenly
Say we have a polyhedron in standard form:
\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}
Are there any known methods for ...
7
votes
0
answers
140
views
What's new in sparse eigensystems solution
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
- 171
19
votes
2
answers
2k
views
A data structure for minimum dot product queries
Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
- 1,559
3
votes
0
answers
330
views
Taking Square Roots of Matrices over Z/nZ
Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n? More specifically, suppose I generate a random matrix M, and square it. Can a ...
- 331
5
votes
0
answers
297
views
Hardness of finding eigenvalues?
Is there a setting in which finding eigenvalues/eigenvectors is computationally hard? Or at least, not known to be computationally easy?
For example, how computationally hard or easy is it to find ...
- 331
10
votes
2
answers
518
views
Restricting entries of unitary operators to real numbers and universal gate sets
In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-...
- 3,758
10
votes
1
answer
407
views
What is the largest gap between rank and approximate rank?
We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication ...
- 425
21
votes
1
answer
793
views
What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?
In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the ...
- 13.5k
2
votes
2
answers
424
views
LU factorization of a 0-1 matrix
I have a rather naive question on LU factorization which probably should be easy to answer. Say I have a matrix with entries only from $\{0,1\}$. When can we expect to get an LU factorization of such ...
- 12.8k
14
votes
0
answers
615
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 1,953
16
votes
2
answers
7k
views
What is the fastest algorithm to compute rank of a rectangular matrix?
Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?
I am aware it can be solved through linear matroid intersection, which ...
- 163
9
votes
2
answers
265
views
Polynomial algorithms for UPB (Unextendable Product Bases)
Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n ...
- 2,806
9
votes
0
answers
570
views
Finding SVD efficiently for $AB^T$
I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ and $B$ separately)
EDIT: (I have added the second question here since it was closed as a ...
user4292
62
votes
4
answers
4k
views
Evidence that matrix multiplication can be done in quadratic time?
It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:
What reasons do we have for believing that $\omega = 2$?
I'm ...
- 803
8
votes
1
answer
295
views
Transitive closure of an affine relation
I am looking for work on computing the transitive closure
of an affine relation in the following sense:
Let $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$
be the relation defined by a system of linear ...
- 233
97
votes
2
answers
40k
views
What is the actual time complexity of Gaussian elimination?
In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
- 23.1k
13
votes
1
answer
3k
views
Matrix multiplication in $O(n^2 \log n)$
I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read ...
- 3,440
11
votes
2
answers
4k
views
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
This is a specialized version of a previous question:
Complexity of Finding the Eigendecomposition of a Matrix .
For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
- 111
5
votes
3
answers
376
views
Calculating a fast matrix vector product between vector of reals and a 0-1 matrix
Given:
some vector $R=(r_1...r_l)$ - real numbers,
and a set of distinct vectors with $0$ or $1$ coordinates
$$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\
V_2=(c_{2,1} ... c_{2,l}),\\
.....\...
Alexander
20
votes
3
answers
1k
views
Survey on algorithms/complexity of linear algebra
I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with ...
- 21.5k
2
votes
1
answer
120
views
Determinants and bilinear forms
If one calculates the product of diagonal elements of the $U$ matrix in a $LUP$ factorization of a given matrix $A$, one can calculate the determinant of $A$. Also it is known that $LUP$ factorization ...
- 12.8k
46
votes
8
answers
21k
views
Complexity of Finding the Eigendecomposition of a Matrix
My question is simple:
What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix?
Does eigendecomposition reduce to matrix ...
- 11.9k
5
votes
0
answers
137
views
Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound
I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are ...
- 12.8k
18
votes
2
answers
870
views
A Boolean function that is not constant on affine subspaces of large enough dimension
I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension ...
15
votes
1
answer
808
views
Sparse Walsh-Hadamard Transform
The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is ...
- 32k