All Questions
Tagged with sparse-matrices linear-algebra
27 questions
6
votes
0
answers
111
views
Factorization to sparse matrices
$\newcommand{\lrank}{\operatorname{lrank}}$
$\newcommand{\rank}{\operatorname{rank}}$
Given a matrix $A$, we can define its Hamming weight, $w(A)$, as the number of non-zero elements in it.
Now, given ...
- 3,319
0
votes
0
answers
36
views
Conjugate gradient-like algorithm with multiple search directions
I am solving an $n*n$ system $Ax=b$ in CUDA where $A$ is a sparse matrix. Currently I am solving it using the conjugate gradient algorithm.
I have noticed that $Ax$ where $x$ is $n*1$ has roughly the ...
- 71
6
votes
0
answers
187
views
Expressing an invertible sparse matrix as a product of few elementary matrices
Let $M$ be an $n \times n$ matrix with integer entries. Suppose that $M$ is invertible (over the integers) and that $M$ has at most $An$ nonzero entries, each of which is less than $B$ in absolute ...
- 18.7k
0
votes
1
answer
80
views
Probability of accurate sparse recovery
Suppose $\mathbf{A}_{k\times n}$ ($k<n$) is a matrix whose entries are generated i.i.d. from Gaussian distribution and $\mathbf{s}_{n\times 1}$ is a sparse vector with $m$ sparsity (i.e., $\|\...
- 287
1
vote
1
answer
428
views
Covering number in the space of symmetric matrices
Let $S_n(\mathbb{R})$ be the set of symmetric matrices of size $n \times n$. Note $\|\Theta\|_{0}$ the number of nonzero elements of a matrix $\Theta$ and $\|\cdot\|_F$ the Froebenius norm. Consider ...
- 407
1
vote
0
answers
48
views
Size of PD matrices with sparse inverse
Let $S_{n}^{++}(\mathbb{R})$ be the set of strictly positive definite (PD) matrices on $\mathbb{R}$. We say that a matrix is $k$ sparse if it has at most $k$ nonzero elements.
Can we somehow ...
- 407
11
votes
2
answers
1k
views
Existence of sparse LU decomposition of sparse matrix
Let $A$ be a sparse matrix over some field. I would like to know about the existence of LU decompositions so that $L,U$ are both sparse.
More precisely, let $A$ be an $N$-by-$N$ matrix. Suppose each ...
- 547
5
votes
0
answers
155
views
"sparsifying" a binary (over the field F2) matrix
Assume I have a matrix $A \in GF(2)$, i.e., $A_{i,j} \in \{0, 1\}$ and the sum is modulo 2. Is there any known algorithms/methods to sparsify (reduce the number of non-zero entries) $A$ while keeping ...
- 183
1
vote
1
answer
308
views
Relation between the algebraic multiplicity of an eigenvalue and the subdiagonal elements of a symmetric tridiagonal matrix [closed]
Show that if $T$ is a symmetric tridiagonal matrix and an eigenvalue $\lambda$ has multiplicity $k$, then at least $k−1$ subdiagonal elements of $T$ are zero.
If we consider a submatrix $B$ that has ...
6
votes
0
answers
141
views
Algorithm to check a conjectural value for the rank of a large matrix
Feel free to suggest a different title, I'm not sure how to phrase this. I'm in the following somewhat specific situation:
I'm checking a conjecture which at the end of the day boils down to the ...
- 8,524
3
votes
0
answers
117
views
Sparsest similar matrix
Given a square matrix A (say with complex entries), which is the sparsest matrix which is similar to A?
I guess it has to be its Jordan normal form but I am not sure.
Remarks:
A matrix is sparser ...
1
vote
0
answers
391
views
Decomposition of a Matrix by Sparse Matrices
Let $\mathbb{F}$ is a field. Consider an $n \times n$ matrix $\bf A$ over $\mathbb{F}$.
$\bf A$ is called sparse matrix over $\mathbb{F}$ iff the number of non-zero entities of $\bf A$ be at most ...
- 211
1
vote
0
answers
349
views
Matrix Sparsity Pattern
Suppose I have a matrix $H^{+} = (H^T H)^{-1} H^T$ where $H$ is a sparse matrix. Consider the case where only the sparsity pattern i.e. the zero elements of $H^{+}$ matrix is known, then would it be ...
- 11
1
vote
1
answer
488
views
Upper bound on the number of non-zero entries of the product of sparse matrices
I have two sparse matrices: $A$ of dimension $m \times k$ and $B$ of dimension $k \times n$.
Is there a way to know how many non-zero entries there are in $C = A B$ without computing $A B$?
I can ...
- 121
3
votes
1
answer
307
views
Expected spectral radius for a sparse Erdős-Rényi binary matrix with a certain density
Let $A$ be an $n \times n$ sparse matrix generated via the Erdős-Rényi method. Here, "sparse" means that $\|A\|_F = O(n)$. I am interested in the relationship between the expectation $\mathbb E(\rho(A)...
- 159
2
votes
1
answer
282
views
Decomposition of rectangular matrices into a product of a sparse and a small matrices
I would like to construct a rectangular matrix which doesn't have a decomposition into a product of a sparse and a small matrices. It is easy to see that a random matrix doesn't have such a ...
- 211
5
votes
1
answer
1k
views
In a large sparse matrix, how many eigenvalues/eigenvectors are “spurious”?
In a large (possibly above $5000\times 5000$) matrix, the problem of finding all the eigenvalues and eigenvectors can be solved using iterative methods (Arnoldi, Lanczos etc.). However, there seems to ...
user116085
6
votes
0
answers
289
views
Upper bound for $\|\textbf{D}^{-1}\|$, where $\textbf{D}$ is a matrix with specific sparse pattern
Consider the block matrix given by
$$\textbf{D} = \left[
\begin{array}{ccc}
\left[
\begin{array}{ccc}
D & \ldots & D\\
\vdots & \ddots & \vdots\\
D &...
- 143
2
votes
0
answers
95
views
Maximal "all zeros" submatrix of a sparse binary matrix
Let $A\in\left\{ 0,1\right\} ^{M\times N}$, where each row of $A$ has at most $d$ components equal to $1$, and $d\leq M\ll N\ll Md$.
Question: $\forall n\leq N$, what is $m\left(n\right)$, the ...
- 968
2
votes
2
answers
335
views
Solving linear system when one eigenvalue is known
I have a huge sparse linear system $Ax = b$ where I know that an eigenvalue/eigenvector pair is $1$ and a vector of all $1$'s. Can this knowledge help me in solving the linear system at all? It seems ...
- 123
5
votes
2
answers
2k
views
Decomposing a matrix into a product of sparse matrices
How to study the decomposition of a square matrix into a product of sparse matrices?
There are no restrictions on the number of matrices in the product, but the fewer the better.
- 451
12
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
- 723
8
votes
1
answer
1k
views
Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?
How can I efficiently compute
$\mathrm{trace}(A(B^{-1}))$
where $A$ and $B$ are both sparse symmetric PSD $n \times n$ matrices, both with $O(n)$ non-zero entries? If it helps, the pattern of non-...
- 500
7
votes
1
answer
449
views
Can I find the gap between the two least eigenvalues of this special matrix A(t)?
I am interested in finding the gap between the two least eigenvalues of $A(t)$, a Hermitian $N\times N$ sparse matrix whose diagonal elements are $a_it+b_i\,(1\leq i\leq N)$, and all off-diagonal non-...
- 103
6
votes
5
answers
2k
views
Computer algebra system for calculation of characteristic polynomial of sparse matrix
I have a $n \times n$ matrix, for which i need to calculate the characteristic polynomial. The matrix is over $GF(2)$, and $n \approx 10^4$. However the matrix is very sparse, with around $ n $ non ...
- 61
0
votes
2
answers
2k
views
How to accelerate/avoid multiplication for large matrices in Matlab? [closed]
The setting is here.
X: 6000x8000 non-sparse matrix
B: 8000x1 sparse vector with only tens of non-zeros
d: positive number
M: is sparsified X'X, i.e. thresholding the elements smaller than d ...
- 21
15
votes
9
answers
9k
views
Exponential of large matrices
I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...
- 151