Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [sparse-matrix]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
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 ...
2 votes
1 answer
46 views

Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

There seems to be a slight difference in terminology among a couple of different traditions within theoretical computer science. To have a quantum computer simulate the Hamiltonian evolution of $\exp(...
1 vote
0 answers
25 views

Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG

I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over ...
3 votes
0 answers
81 views

Is there an algorithm for reducing the average row width of a sparse matrix?

Suppose I have a sparse $M \times N$ matrix $A$ and I define the "width" of each row $i$ to be: $$w_i \equiv r(A_i) - l(A_i),$$ where $r(A_i)$ is the index of the rightmost nonzero element ...
2 votes
0 answers
63 views

computational complexity of sparse matrix powers

Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I ...
4 votes
0 answers
69 views

Precise rank of a sparse integer matrix

Consider a large sparse rectangular integer matrix. Is there a way to compute its exact rank that is better in terms of speed and/or memory usage compared to a dense matrix?
3 votes
1 answer
71 views

Problem conditions to use Laplacian solvers

I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense. Suppose that we want to solve Ax=b, ...
5 votes
1 answer
369 views

When is it hard to invert a sparse matrix?

Are cases where numeric inversion of a sparse matrix is known to be harder than sparse matrix multiplication? In practice, sparse matrix inversion is done with methods like Jacobi or Gauss-Seidel, ...
3 votes
1 answer
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 ...
1 vote
0 answers
47 views

Stable recovery of signals by $\ell_1$ optimization

Suppose the received vector $y$ is generated from a vector $x^*$ as $y = { D}x^* + z$ for some ``dictionary" matrix ${D}$ and noise vector $z$ s.t for some $\epsilon >0$ we have, $\Vert z \Vert_2 \...
13 votes
1 answer
549 views

Fast sparse boolean matrix chain product

So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually ...
2 votes
1 answer
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 ...
2 votes
1 answer
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 ...
1 vote
0 answers
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 ...
1 vote
0 answers
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 vote
0 answers
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 ...
6 votes
1 answer
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 ...
13 votes
4 answers
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 ...
8 votes
0 answers
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 ...
6 votes
1 answer
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.
0 votes
0 answers
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 ...
2 votes
1 answer
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 ...
0 votes
0 answers
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 ...
7 votes
0 answers
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 ...
11 votes
0 answers
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 ...
13 votes
2 answers
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 ...
7 votes
0 answers
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 ...
8 votes
1 answer
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 ...
21 votes
2 answers
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 ...