Questions tagged [sparse-matrices]
The sparse-matrices tag has no summary.
35 questions
1
vote
1
answer
99
views
Will CSR format store the all 0 column?
In the matrix(3 rows and 7 columns) below with 4 all zero columns
0 4 0 0 0 0 0
2 1 0 0 0 0 0
0 0 3 0 0 0 0
The CSR format of storage is :
row_ptr: [0, 1, 3, 4]
col_ind: [0, 0, 1, 2]
values: [4, 2, ...
- 45
3
votes
1
answer
171
views
Mathematical operation for removing duplicate rows in a matrix
I am using the GraphBLAS C API (https://graphblas.org/) which provides an interface for performing mathematical operations on sparse matrices. Given an adjacency matrix $\mathbf{A}: \mathbb{R}^{n \...
- 302
1
vote
0
answers
142
views
What's the name of the genre of algorithms for efficiently collecting common factors?
I'm working with sparse vectors represented as index (array of unsigned integers) and coefficient (array of floats with the same ...
- 139
0
votes
1
answer
59
views
Classifying vectors that only contains 1001110101 numbers - Is Support Vector Machine the solution?
Assume that you are given a vector 0b1101001001011001 etc. And you are going to classify it.
One can use Support Vector Machine, but is that method good for ...
- 107
0
votes
1
answer
74
views
Combining chunks on an infinite grid into regions
I am working on an floorplan application where I save elements on an infinite grid in a sparse manner. Specifically, I have the following Python class representing a sparse grid (basically a ...
- 103
0
votes
1
answer
556
views
How sparsity term in loss function for sparse autoencoder is making hidden units inactive?
I am working on a Sparse Autoencoder but Andrew NG's notes are hard to understand.
My question is about the following equation: Loss Function.
In sparse autoencoder, the goal is to inactive some ...
1
vote
0
answers
267
views
Is there an alternative method to using Gaussian elimination in order to solve 3-XORSAT
I have a large system of $3$-$XORSAT$ constraints (i.e. up to $3$ variables per constraint) and this can be represented in matrix form as a linear algebra problem $Ax=b$ $mod$ $2$. Solvability (i.e. ...
- 11
1
vote
1
answer
164
views
Product of sparse polynomials with FFT
I need to compute the product of two polynomials $f(X)$ and $g(X)$ over a finite field. The degrees of these polynomials are $n^2$ for some integer $n$. However, we also know that the polynomials are ...
- 193
4
votes
0
answers
288
views
Low-rank matrix completion is NP-hard
In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
- 41
0
votes
3
answers
250
views
Data structure to efficiently add zero-rows to a sparse matrix
I would like to create a data structure representing a sparse matrix, where the number of non-zero values is $\mathcal{O}(n)$ (the matrix is $n\times n$).
The matrix should support the following ...
- 161
0
votes
2
answers
1k
views
Matrix-vector multiplication using only lower triangular of matrix
Suppose one has a large sparse symmetric positive definite matrix $A$ and wants to multiply it by a vector $x$. Only the lower triangular part of matrix A is stored/known. The multiplication $Ax$ ...
- 9
1
vote
0
answers
134
views
Sparse tables as prefix sum data structure
I am trying to understand how a sparse table can be used as a prefix sum data structure for a bit vector. In the screendump below 1 the article [2] very vaguely describes how to use a sparse table ...
- 121
2
votes
0
answers
185
views
Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph
As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
- 121
3
votes
0
answers
701
views
When are adjacency lists better than sparse matrices?
I saw several questions discussion the benefits of adjacency lists over matrices to represent a sparse undirected graph. On the other hand, none of them discuss sparse matrix representations such as <...
- 131
4
votes
2
answers
305
views
Max flow algorithm for floating-point weights and E~=10*V
Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. ...
- 165