Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sparse-matrix]

The tag has no usage guidance.

3
votes
1answer
94 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
1answer
139 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
0answers
96 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
0answers
28 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
0answers
48 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 ...
2
votes
0answers
117 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 ...
7
votes
1answer
214 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
4answers
765 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
0answers
294 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 ...
0
votes
0answers
95 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 ...
5
votes
1answer
601 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.
2
votes
1answer
354 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
0answers
69 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
0answers
124 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
0answers
1k 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 ...
7
votes
0answers
133 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
1answer
355 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
2answers
847 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 ...
12
votes
2answers
1k 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 ...
11
votes
1answer
409 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 ...