Questions tagged [linear-algebra]
The linear-algebra tag has no usage guidance.
201
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, ...
15
votes
6answers
6k 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 ...
13
votes
1answer
5k 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 ...
13
votes
2answers
710 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}...
12
votes
4answers
6k 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 ...
11
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 \...
10
votes
1answer
2k 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 ...
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: & \...
9
votes
1answer
423 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
1answer
811 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
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. ...
8
votes
2answers
1k 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
339 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
792 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
404 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
10k 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
\...
7
votes
1answer
517 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
1answer
327 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 ...
6
votes
2answers
433 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 ...
6
votes
1answer
228 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
126 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 ...
5
votes
2answers
11k 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 ...
5
votes
1answer
306 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
513 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
290 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
2answers
172 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 ...
5
votes
1answer
1k 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
2answers
217 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
74 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
303 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
844 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
237 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
84 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
1answer
81 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
1k 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
1k 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
567 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
68 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
1answer
966 views
Absorbing Markov Chains: An efficient algorithmic approach
Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state. The procedure is as follows:
Given the ...
4
votes
2answers
119 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
34 views
Complexity of a decision problem: system of linear equations over finite field with restricted solutions
I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ ...
4
votes
1answer
354 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
413 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
122 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
3k views
how to represent Sparse Matrices [closed]
I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices.
Could you please suggest me some other way to store/represent sparse ...
4
votes
1answer
462 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
178 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
125 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{...