Questions tagged [linear-algebra]
The linear-algebra tag has no usage guidance.
177
questions
22
votes
4answers
1k views
Automated optimization of 0-1 matrix vector multiplication
Question:
Is there established procedure or theory for generating code that efficiently applies a matrix-vector multiplication, when the matrix is dense and filled with only zeros and ones? Ideally, ...
13
votes
5answers
5k views
What parts of linear algebra are used in computer science?
I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For ...
12
votes
2answers
580 views
Matrix chain multiplication and exponentiation
If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}...
11
votes
1answer
4k views
Complexity of finding the pseudoinverse matrix
How many arithmetic operations are required to find a Moore–Penrose
pseudoinverse
matrix of a arbitrary field?
If the matrix is invertible and complex valued, then it's just the inverse. Finding ...
10
votes
1answer
4k views
Short and slick proof of the strong duality theorem for linear programming
Consider the linear programs
\begin{array}{|ccc|}
\hline
Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} &
\max \vec{c}^T\vec{x} \\
\hline
\end{array}
\begin{array}{|ccc|}
\hline
Dual: & \...
10
votes
0answers
1k views
Alternatives to SVD for rank factorization
I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \...
9
votes
1answer
366 views
What algorithms exist for solving natural number linear systems?
I'm looking at the following problem:
Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number ...
8
votes
3answers
4k views
Fastest way to solve a system of linear equations
I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is ...
8
votes
1answer
623 views
Minimal basis for set of binary vectors using XOR
I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \{0,1\}^n$. The problem is to ...
8
votes
2answers
788 views
Could a quantum computer perform linear algebra faster than a classical computer?
Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has ...
8
votes
1answer
1k views
Inverting a band matrix
I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following:
Here, the area under the blue stripes is the non-zero elements; everything else is ...
8
votes
1answer
274 views
Generate algorithmically all grid points inside a hypercube
$\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\|#1\|_\infty}$The problem comes directly from computational mathematics, and can be stated as follows:
Given a regular matrix $M\in\R^{d\times d}$, find ...
7
votes
1answer
1k views
Complexity of checking whether linear equations have a positive solution
Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check
whether it has a solution $...
7
votes
1answer
767 views
It is possible to implement a *greater than* function using only addition, substractions and multiplications?
All values are from a finite field $Z_t$.
I want to write a function greater than like this
$GT(x,y) = \begin{cases}
1, & \text{if } x > y, \\
0, & \text{otherwise}.
\end{cases}$
...
7
votes
1answer
334 views
Does spectral graph theory say anything about graph isomorphism
Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory?
Two known theorems of spectral graph theory are:
Two graphs are called isospectral or ...
7
votes
1answer
494 views
Probabilistic test of matrix multiplication with one-sided error
Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\...
6
votes
4answers
3k views
Solving system of linear inequalities
I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $
I know these inequalities can be solved using Bellman-Ford algorithm. ...
6
votes
1answer
8k views
Checking Feasibility of Linear Program in Polynomial Time
Given a linear system of the form:
$$\begin{array}{c}
x_r = a \quad x_j = b \\
c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\
x_1+x_2 + x_3 + \ldots + x_n = k\\
0 \le a,b,x_1,x_2,x_3...x_n \le 1\\
k \ge 0
\...
6
votes
2answers
154 views
Can this system of polynomial equations be solved in polynomial time?
I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
6
votes
1answer
222 views
Are there any non-naive parallel sparse matrix multiplication algorithms?
I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on ...
6
votes
1answer
123 views
How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?
Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the ...
6
votes
1answer
347 views
Testing whether a determinant polynomial is identically zero
Suppose we are given matrices $A_1, \ldots, A_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots ...
5
votes
2answers
379 views
solving large nonlinear systems in parallel
I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
5
votes
2answers
281 views
Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel
Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$). ...
5
votes
1answer
807 views
Computing Von Neumann Entropy Efficiently
The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as ...
5
votes
1answer
237 views
Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?
could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to ...
5
votes
2answers
118 views
Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero
Given a matrix $A \in \mathbb{R}^{n \times n}$ with no zero rows, what is the complexity of deterministically finding a vector $x \in \mathbb{R}^n$ such that every entry of $Ax$ is nonzero?
It is ...
5
votes
1answer
69 views
Efficient algorithms for dealing with linear algebra over the rationals
I'm an academic mathematician. While trying to verify a counterexample to something in my research, the following computational problem has arisen:
Fix a vector space $V = \mathbb{Q}^n$. Here $n$ ...
5
votes
1answer
286 views
Complexity of Pythagorean triples
We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$.
In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit ...
5
votes
1answer
718 views
Comparing sets of vectors
If $u,v \in \mathbb{R}^d$ are two $d$-dimensional vectors, say that $u\le v$ if $u_i \le v_i$ for all $i=1,\dots,d$. In other words, comparisons on vectors will be pointwise.
Let $S,T$ be two ...
5
votes
0answers
167 views
How to treat numerical errors in determinants of singular matrices when using LU decomposition
I want to calculate the determinant of a matrix. Currently I'm using LU decomposition.
To check my algorithm I wrote a unit test with random matrices. In one part I set one row to be equal to ...
5
votes
2answers
1k views
Proof of Strong Duality Via Farkas Lemma
I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
5
votes
0answers
74 views
Solution of a Toeplitz system of linear equations
I want to code a solver for nonsingular systems of $N$ linear equations in $N$ unknowns (say up to $N=100$) with an asymmetric Toeplitz matrix. I know that the Levinson algorithm can solve it in time $...
4
votes
2answers
9k views
What is the complexity of this matrix transposition?
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
4
votes
1answer
78 views
Unfeasible linear program becomes feasible if a variable is removed
Apologies, not a computer scientist by trade but I'm playing with linear programming these days.
Let $\{x_i\}$ be $N$ optimization variables with bounds
$$l_i \leq x_i \leq u_i$$
I'm interested in ...
4
votes
2answers
916 views
Time complexity of matrix multiplication in Big-Align
I am reading the following paper:
Big-Align: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. International Conference on Data Mining (ICDM 2013).
I'd like to ...
4
votes
1answer
804 views
Closed form solution for optimization problem
Consider the problem of finding the real-valued matrix $C$ so that
$$\|S-AC\|_F^2\qquad(1)$$
is minimal. ($S$ and $A$ are real valued matrices and $_F$ denotes the Frobenius norm). This problem has ...
4
votes
1answer
235 views
Solving systems of linear equations over semirings
So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm ...
4
votes
1answer
436 views
What are some applications of computing the permanent of a matrix?
What are some applications that require computing the permanent of a matrix?
One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a ...
4
votes
2answers
60 views
Among $k$ unit vectors, find odd set with sum length less than 1
I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no ...
4
votes
2answers
116 views
Can you complete a basis in polynomial time?
Here is the problem: we are given vectors $v_1, \ldots, v_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v_i$ are rational, with numerator and denominator taking $K$ ...
4
votes
1answer
264 views
Minimize the maximum Hamming weight of basis vectors spanning a binary subspace
In the course of my research, I stumbled upon a problem which can be recast as the following decision problem:
First some notation:
Let $\mathbb{F}=\{0,1\}$ be the binary field. For $x\in\mathbb{F}^...
4
votes
1answer
262 views
Number of solutions to linear system of equations over GF(2)
Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option.
Is there a ...
4
votes
1answer
121 views
How to compute a curious inverse
Let $M$ be a square matrix with entries that are $0$ or $1$ and let $v$ be a vector with values that are also $0$ or $1$. If we are given $M$ and $y = Mv$, we can computer $v$ if $M$ is non-singular. ...
4
votes
1answer
266 views
Minimize sum of squares of rows in matrix when sum of columns have some constraint
I'm looking for an algorithm that can find any matrix $a_{j,i}$ such that
$$
\sum_{i \in I} \left(\sum_{j\in J} a_{j,i}\right)^2
$$
is minimal, while also for each $j\in J$ satisfying the constraint
...
4
votes
1answer
165 views
Time - Complexity Convex Optimization and Eigen Decomposition
Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
4
votes
0answers
121 views
Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system
Problem
Solving a non-linear system of equations.
The number of variables is the same as the number of equations.
When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
4
votes
0answers
67 views
Is this a known question in matrix sketching?
Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m \ll D $ dimensional columns and ...
4
votes
0answers
167 views
Intuitive self-contained proof of Farkas' Lemma
I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states:
For any convex cone generated ...
3
votes
2answers
240 views
Transforming a byte with a subset of a small, fixed set of values and xor into any other value
If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, ...
