Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [sparse-matrix]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
46 views

### Cuthill - Mckee Guarantees?

I'm interested in the following problem: given $M$, a $p \times p$ symmetric sparse matrix (the number of non-zero elements in each row is at most $s \ll p$), find a matrix $B = PMP^T$ where $P$ is a ...
• 131
46 views

• 1,453
146 views

### Graph sparsification and eigenspaces

I am currently trying to understand whether I can make some claims about the relation between eigenspaces of a sparsifier and the original matrix. In this context, let me first define a couple of ...
• 118
213 views

### Complexity of $\{0,\pm1\}$ determinant in sparse cases?

If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity? Assume that the matrix ...
• 12.9k
1 vote
118 views

### How to shrink a very large sparse matrix [closed]

Let $A$ be a matrix where $A \in \mathbb{F}^{n^s \times n^s}$ and $s>2$. Assume $A$ is a sparse matrix where its rank $\leq n$ and that there is only constant number of non-zero elements in each ...
• 271
1 vote
45 views

### Sparse coding and matching pursuit algorithms

Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
• 1,453
1 vote
72 views

### A well-known instance of overcomplete dictionaries

sparse representation is: A signal can be represented as a linear combination of basis functions where the set of basis functions is called dictionary and data samples are much more than their ...
• 141
269 views

### The connection between compressed sensing and sparse representation

If I understand correctly, Compressed Sensing as an application of Sparse Representation is defined as: To find linear ...
• 141
225 views

### Checking properties of matrices

Given a sparse matrix $A$ in $\mathbb{Z}^{n\times n}$, how easily could one check whether a coefficient $\alpha_k$ of the characteristic polynomial $P_A$ of $A$ is equal to $0$ (without the need to ...
• 73
1k views

### Finding the sparsest solution to a system of linear equations

How hard is it to find the sparsest solution to a system of linear equations? More formally, consider the following decision problem: Instance: A system of linear equations with integer coefficients ...
• 5,127
314 views

### Are there sparsifiers that approximate vertices rather than edges?

Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph ...
126 views

### LP solver for sparse, PSD and strictly diagonally dominant matrix

I have a linear problem with a sparse, psd and strictly diagonally dominant matrix. Can you please point me to some known best solvers (in terms of runtime, or easy to be practically optimized for ...
• 386
1k views

### Reducing the bandwidth of non-symmetric matrix

Is there an efficient algorithm to reduce the bandwidth of a directed graph's adjacency matrix? Something like the reverse Cuthill-McKee, but for non-symmetric matrices.
• 173
434 views

### Partitioning a matrix into equal-sized regions: finding the maximum

I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that: each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given, the sum of all ...
71 views

### Sparse matrix front reducing

There is a symmetric sparse matrix with large front. This matrix is created from graph. Element with position $(i,j)$ is not zero if nodes $i$ and $j$ are connected. What algorithms can be used for ...
129 views

### What's the state of the art for matrix nuclear/trace norm optimization

I am interested in simple matrix optimizations with nuclear/trace norm: $\min_X \left(f(X) + \|X\|_*\right)$ where $\|X\|_*$ stands for the trace norm of the matrix $X$, and $f$ is a convex smooth ...
• 71
2k views

### Complexity of finding the leading eigenvector of a graph Laplacian

Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$? Are there any families of Laplacians for which it takes ...
• 1,356
140 views

### What's new in sparse eigensystems solution

As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
• 171
397 views

### Functional Sparse-Matrix with good performance?

While writing a Petri Net program, I was faced with a choice about data structures to represent the graph. Adjacency lists (i.e. lists enumerating the arcs into and out of individual places or ...
1k views

### Finding a 5-cycle in a sparse graph efficiently.

(crossposted from MathOverflow) Hi, I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I want to find a 5-cycle in a graph. Actually, what I really ...
• 1,573
2k views

### Fast sparse boolean matrix product with possible preprocessing

What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)? Actually, I have the advantage that ...
• 8,951