Questions tagged [linear-algebra]
The linear-algebra tag has no summary.
266 questions
1 vote
0 answers
28 views
Good algorithm to solve a system of "cyclic" banded linear equations
I would like to solve the equation $Ax=b$ where $A$ is an $N\times N$ "cyclic" banded matrix (there might be a better term, but I wasn't able to find it), i.e. a matrix that look like $$\...
- 111
1 vote
0 answers
28 views
Hardness of approximation for max-LINSAT mentioned in DQI paper
I went through Def 2.1 of this paper, where the approximation version of max-LINSAT is defined as follows. Let $\mathbb{F}_p$ be a finite field. Input: For each $i=1,\cdots,m$, let $F_i\subset \...
- 209
1 vote
0 answers
59 views
Transforming a set of fundamental cycles of non-weighted undirected graph into simplest basic cycles using XOR
How to transform a set of fundamental cycles of non-weighted undirected graph into minimum basic cycles using XOR? Definitions: Fundamental cycle include in fundamental cycle basis, that can be formed ...
- 111
4 votes
2 answers
131 views
Theory behind scaled floating-point summation algorithm
In the "jacobi.c" code implementing Jacobi's method for computing eigenvalues and eigenvectors of a given matrix, from the gsl-2.8 library, one of the functions is for summing the squares of ...
- 350
2 votes
0 answers
49 views
Special case of rank minimization
The problem takes as input an $m \times 2n$ matrix $A$ over $\mathbb{F}_2$. Optimization version: find a subset of exactly $n$ columns so that the corresponding submatrix (taking only selected columns)...
1 vote
0 answers
53 views
Optimal cycle for minimizing distance between vectors
I faced this problem recently, and am looking for an efficient solution. We are given $X = (x_1,...,x_n)$ and $Y = (y_1,...,y_n)$ two vectors with ascending coordinates. Considering a cycle $\sigma = (...
- 11
1 vote
0 answers
56 views
For a matrix in a row-echelon form, what's a good algorithm to find the free variables?
Suppose I have a reduced row echelon form of a matrix for linear equations. The pivots from the corresponding Gaussian elimination are available. For example, in $$ \begin{pmatrix} 1 & 0 & 0 \\...
- 111
2 votes
1 answer
124 views
Straight forward algorithm for obtaining a sub matrix
Ok so I just started writing a linear algebra toolbox in C++ for some other projects I have / plan on starting in the future. So I define a matrix as the fundamental building block and vectors, ...
- 21
1 vote
0 answers
46 views
Find a basis of a vector space minimizing the numbers of nonzero coordinates for a bunch of vectors
I've got a (to be a bit specific) 84-dimensional rational vector space, and as many as 1197 vectors in it. In the basis of the space that I've got, numbers of nonzero coordinates for these vectors ...
- 111
1 vote
0 answers
56 views
Kronecker Decomposition Algorithm
I am looking for an algorithm that decomposes a $2^n$ square matrix into a Kronecker product $\otimes$ of $n$ number of $2 \times 2$ matrices. Does anyone know if there is an implementation out there ...
- 111
0 votes
1 answer
93 views
Fit data to a lookup table
I have been looking for methods to fit 1-D data to a lookup table. In other words, there's no known function that is used as a model. For example in the plots below, the measured data (blue) is fit to ...
- 1
2 votes
1 answer
57 views
Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank
Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M $ such that the rank of the matrix $$A = \sum_{m \in N}m $$ is minimal. I am wondering if anyone have seen ...
- 225
1 vote
1 answer
43 views
Algorithm for solving linear equations if interested only in the first component
If I want to solve $\mathbf A \mathbf x = \mathbf b$, but I am only interested in the value of $x_1$, what algorithm should I use, and will it always be strictly more efficient than solving for all of ...
- 13
5 votes
1 answer
96 views
Given a set of points $S$ which is a subset of a vector space $V$, find the smallest subspace which intersect $S$ in at least $k$ points
Given a set of points $S$ which is a subset of a vector space $V$ I want to want the smallest subspace of $A$ of $V$ such that $|A \cap S| \geq k $. I suspect some variant of this problem would have ...
- 225
3 votes
1 answer
150 views
How does numpy.linalg.inv calculate the inverse of a matrix?
What is the algorithm behind this routine and is there documentation available for it?
- 31