# Questions tagged [sparse-matrices]

The tag has no usage guidance.

60 questions
Filter by
Sorted by
Tagged with
1 vote
99 views

### How to numerically solve differential equations involving sines, cosines and inverses of the unknown function? [closed]

Crossposted at SciComp SE I'm very new to finite difference method and I am just introduced to methods of solving differential equation using finite difference method via sparse matrix method. I find ...
62 views

113 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 ...
127 views

### Random sparse and invertible matrices

Let $n\leq m$ and $0\leq k\leq (n\times m - \min\{n,m\})$ be in $\mathbb{N}$. Let $\mu$ be a probability measure dominated by the Lebesgue measure on $\mathbb{R}$ and generate a random $n\times m$ ...
1 vote
203 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 ...
140 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 ...
91 views

### Approximate inverse of large sparse matrix

Given a large sparse matrix $M$, how to determine the existence of a good preconditioner? In other words, does there exist a sparse matrix $X$ such that $X M$ is close to the identity with respect to ...
120 views

### Jordan Decomposition of Sparse matrix

Suppose we are given $n \times n$ rational matrix, $A$ with at most $k$ nonzero elements in each row and each column with $k \ll n$. What is the best algorithm to compute its Jordan decomposition? ...
540 views

1 vote
354 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 ...
127 views

### Spectrum of finite-band random matrices?

Let $X_n=(X_{ij})_{1 \leq i,j \leq n}$ such that : $$\begin{cases} &X_{ij} = 0 \quad \text{if}\quad \vert i - j \vert > k\\ & X_{ij} \sim P_X \quad \text{otherwise} \end{cases}$$ And ...
108 views

### Maximise singular value decay by sparse matrix approximation

I have a large matrix $A \in \mathbb{R}^{n \times m}$ and would like to subtract a sparse matrix $B \in \mathbb{R}^{n \times m}$ with less than $c (n+m)$ non-zero entries, where $c > 0$ is a ...
1 vote
320 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 ...
983 views

### Square root of a large sparse symmetric positive definite matrix

I am trying to calculate $$Y = A^{\frac 12} X$$ where $A$ is a very large and sparse positive definite matrix, say, $10^4 \times 10^4$. Matrix $X$ is known and, say, $10^4 \times 100$. Is there any ...
1 vote
377 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 ...
1 vote
130 views

91 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 ...
699 views

### Sparse matrix approximation using only a few dense columns (or rows)

Given a dense matrix $A \in \mathbb{R}^{n \times m}$, with $n < m$, I am interested in finding a good approximation by choosing $s$ rows and zeroing the rest. This leads me to the following ...
279 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 ...
277 views

### Finding high-dimensional correlation matrices that are both sparse and low-rank

Let $\boldsymbol{R}$ be the correlation matrix of $X_i,i=1,\dots,p$ with a large $p\gg q=\text{rank}(\boldsymbol{R})$. Is that reasonable to assume that $\boldsymbol{R}$ is both (approximately) sparse ...
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.
96 views

### Finding large bicliques in random bipartite graph

I want to find a $k$ by $r$ biclique hidden in an $M$ by $N$ random bipartite graph where edges are present with probability $p \in [0,1]$. I am specifically interested in $p \ll 1$, and large values ...
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 ...
1 vote
162 views

### Spectrum of a binary markov transition matrix

I would like to know if there are any special analytic expressions or fast numerical methods to get the spectrum for the transition matrix corresponding to a Markovian binary process (Bernoulli ...
957 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-...
415 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-...
241 views

### Decomposing large symmetric banded sparse matrices

I'm investigating 3D image deblurring and one of the approaches I'm interested in is applying spatial regularisation. To do this I have generated a matrix $A$ which encodes the 6-connectivity of each ...
1 vote
243 views

### Asymptotic eigenvalue analysis for a sparse random matrix

We have an asymptotic analysis problem for the eigenvalue performance of the following random matrix: $H=\{h_{ij}\}_{N_r\times N_t}$, where each entry $h_{ij}$ is with a probability $p$ to obey the ...
216 views

### Hamiltonicity criteria for sparse graphs

Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course). There are three main classes of criteria for Hamiltonicity that I am aware of: Dirac-...
1 vote
593 views

### Estimate the determinant of sparse 0-1 matrix

There is a matrix A where each entry is either 0 or 1. Each column has exactly a 1's and each row has at most b 1's. What's the upper bound of abs(|A|)? The condition is stronger than the Hadamard's ...
1 vote
115 views

### Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$. I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I ...
665 views

### Inverse of sparse matrix is not generally sparse [closed]

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices). I encountered several times the web pages which states that the ...
Suppose that there are $i< N$ linearly independent $N$-dimensional vectors $\mathbf{v}_1,\mathbf{v}_2,\ldots,\mathbf{v}_i$ over a finite field $\mathbb{F}_q$, whose elements are denoted as \$\{0,1,2,...