# Questions tagged [sparse-matrices]

The tag has no usage guidance.

54 questions
Filter by
Sorted by
Tagged with
52 views

### Volume and basis for integer lattice subject to sparse constraint

Let $k<n$ be integers. Let $A\in \mathbb{Z}^{k \times n}$ be a sparse matrix, meaning that the number of nonzero entries in every row and every column is at most $O(1)$. Further, assume that ...
58 views

### What is the big-O complexity of solving the sparse Laplace equation in the plane?

In MATLAB, you can get a 2d Laplacian via A = delsq(numgrid('S',N)); yielding a matrix $A$ that is $n \times n$ with $n = O(N^2)$, for a square domain discretized ...
208 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 ...
40 views

108 views

### Algorithm to find “islands” in sparse matrices

I am playing with a weird dataset of ternary images (+1,0,-1 values only) which happen to be very sparse (avg. > 90%). I would like to determine the most relevant "islands" (or should I call them ...
233 views

### Sparse, left-looking LU factorization

I'm trying to understand the left-looking LU factorization algorithm for sparse matrices, by reading T.A. Davis' book, and have trouble in one step (sorry for the specific question) about returning ...
106 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 ...
91 views

476 views

### sparse binary vector

I want to know if the following problem has been solved max_w w'Rw where the entries of the vector w are binary (w_i= {0,1} )
486 views

### $\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
Consider an $n\times n$ random binary matrix $M$ with i.i.d. entries $m_{ij} \sim {\rm Bernoulli}(p)$, where $p = n^{-\beta}$ with $\beta \in (1,2)$. I am interested in the behavior of the singular ...