Questions tagged [sparse-matrix]
Questions related to storage, assembly, operations, and other aspects of dealing with sparse matrices, for which only non-zero elements are stored. Questions that do not with sparse matrices directly, but other means of using sparsity should be tagged with [sparse-operator].
339 questions
0
votes
1
answer
47
views
CVXPY - Convex difference of quadratic forms
I have a sparse optimization problem of the form:
$$\min_x c^T x + \| D x\|^2_2 + \| V x\|^2_2 - \| W x\|^2_2$$
$D$ is diagonal and $V$, $W$ are non-square matrices. I know that:
$$Q = D^2 + V V^T - ...
3
votes
1
answer
382
views
Efficiently Updating Matrix Multiplication Result When One Matrix Changes
Suppose you have two matrices $A \in Z_q^{m\times l}$ and $B \in Z_q^{l\times n}$, and the product $A\cdot B$ has already been computed. Now, matrix $B$ remains unchanged, but a few elements in matrix ...
- 33
1
vote
0
answers
48
views
ILU Preconditiner Implementation in Python
I have a question regarding the computational complexity of the ILU preconditioner in Python. I am trying to implement an ILU(0) preconditioner using the following code:
ILUfact = sla.spilu(...
- 21
3
votes
1
answer
134
views
Computing eigendecomposition of extremely large (though sparse band) matrix
I have a very large graph (about over a billion nodes) and I need to compute all the eigenvectors and eigenvalues of the graph (i.e., of the Laplacian of the adjacency matrix) for downstream analysis. ...
- 171
0
votes
0
answers
25
views
Formulating an MRF as a graph weights matrix
I have a binary Markov random field (MRF) of an image:
$$E \left( B \right) = \sum_{i, j} L_{i, j}^{0} + \sum_{i, j} L_{i, j}^{1} + \sum_{i, j} \sum_{m, n \in \mathcal{N} ( i, j )} C (B_{i, j} , B_{m, ...
- 101
0
votes
0
answers
68
views
Improving convergence rate of krylov schur iterations?
I am trying to implement krylov schur iterations. I am noticing that although my implementation converges, it does so really, really slowly. For a 40x40 matrix it is taking hundreds of iterations to ...
- 379
1
vote
4
answers
164
views
Solve Large Scale Underdetermined Linear Equation with per Element Equality Constraint
I have the following system on $\boldsymbol{x}$:
$$ \boldsymbol{A} \boldsymbol{x} = \boldsymbol{0}, \quad \text{subject to} \; {x}_{i} = {v}_{i} \; \forall i \in \mathcal{V} $$
Where $\boldsymbol{A} \...
- 563
2
votes
1
answer
2k
views
Fast algorithm to obtain an orthogonal vector to a set of vectors
When I ask this question I am usually suggested to do things like computing the SVD decomposition of the matrix formed by the vectors. SVD decompositions are very computationally expensive.
I am also ...
- 379
3
votes
2
answers
178
views
Finding ALL Eingenvalues of a Sparse Integer Matrix
I would like to find ALL Eingenvalues of a huge, very sparse integer matrix. This matrix has a lot of known properties, e.g. that it is symmetric and nearly tridiagonal, with very few (max. ca. 4 per ...
3
votes
0
answers
91
views
Eliminate variables from a large system of equations
I have a large system of equations $Ax=0$. For context, the equations are invariants of some model. $A$ is sparse and typically has more columns than rows ($m < n$). The $x$ vector can be divided ...
- 31
2
votes
0
answers
106
views
Iterative solvers for problems in solid and structural mechanics
I am looking for comprehensive literature (papers, books, reports etc..) on iterative solvers for solid and structural mechanics problems to understand the best iterative solvers and preconditioners ...
- 964
7
votes
3
answers
2k
views
How large is large for direct solvers?
Let us say I want to solve a large sparse linear system. It is said that iterative solvers should be better than direct solvers in this case. But how large is large? What is the exact threshold beyond ...
- 181
1
vote
1
answer
89
views
Fill-reducing ordering for computing the matrix product $A^T A$?
I have found many libraries for reducing filling when dong Cholesky factorisation on sparse matrices. However, I want to do fill-reduction for a different reason - given a $m\times n$ matrix $A,$ I ...
- 161
0
votes
1
answer
96
views
Eigenvalue problem and pseudoinverse of a product of sparse matrices
If I have some dense matrix that can be decomposed into a product of sparse matrices with known(but different) sparsity patterns. Can I somehow use this information to more efficiently compute its ...
- 113
0
votes
0
answers
64
views
using scipy.sparse.linalg.eigsh for degenerate states in Bose Hubbard model
I am currently writing a code for the Bose-Hubbard model, and I am calculating the ground states and single-particle density matrix for different values of U and J. As U=0, one would see how the ...
2
votes
1
answer
453
views
How to leverage the GPU for parallel 3-body problem computations
I have a 3-body simulation which must run millions of times.
As far as I know, the GPU shines when it gets to preform simple operations on huge matrices/arrays. Currently I'm debugging and running my ...
- 41
2
votes
1
answer
65
views
Solving $(I-Q)x={\bf 1}$ for sub-stochastic sparse $Q$ of dimension 5M $\times$ 5M
I have a (right) sub-stochastic CSC sparse matrix $Q$ of dimension 5 million, with 200 million nonzero entries, which is a nonzero percentage of 0.0008%, so it is indeed extremely sparse. It is not ...
- 513
3
votes
0
answers
140
views
Fast Fourier Transform on Meshes
I have a (closed, manifold, oriented) triangular mesh for which I build a matrix $L\in\mathbb{R}^{n\times n}$ discretising the negated Laplace-Beltrami operator. The matrix $L$ is symmetric positive ...
- 2,872
0
votes
1
answer
212
views
Problems on the algebraic theory of sparse matrices
I have finished testing basic large densely parallel matrix multiplication on 4 gpu's ,and have done work on TSLU and TSQR on cpu's based on mpi. I am going to continue working on the theory of ...
0
votes
0
answers
238
views
Right blocked linear equation solver on Dense Algebra and Sparse Algebra
I have implemented 1D mesh parallel QR decomposition and LU decomposition,I would like to ask if a linear equation Ax=b,b is a large matrix and I need to shard b or Shard A,b at the same time. Is ...
4
votes
1
answer
384
views
How to efficient solve $e^{-tA} x =b$, where A is a very sparse matrix
I am going to solve an equation containing an exponential matrix $e^{tA} x =b$, which can be obtained naturally through $x=e^{-tA} b$. A is a 1million $\times$ 1 million matrix with stores 7.15 ...
- 141
1
vote
2
answers
251
views
Are there good block sparse matrix solver libraries?
There are some great libraries with linear solvers for sparse matrices - SuiteSparse is the obvious one. The methods work on sparse matrices with scalar entries.
However, often in optimization ...
- 111
2
votes
0
answers
114
views
Diagonalization of large sparse matrix, computational programme recommendation and methods
According to this link, All eigenpairs of large sparse symmetric matrix. The guy @Baranas seems to have given a very confident answer about solving the whole Eigen spectrum. May I know if anyone has ...
- 21
2
votes
2
answers
317
views
Solving Poisson's equation without a Dirichlet boundary condition
Some context of what I am trying to do:
I am trying to implement a function that uses the heat method to calculate geodesic distances in a tetrahedral mesh, and I want to calculate the distances for ...
- 145
0
votes
0
answers
108
views
What is the difference between approximations of mixed derivative and how to implement it
currently I am solving 2D nonlinear second order differential equation containing mixed derivative. I started searching how to descretisize it and found two formulas for 4th order approximation. First ...
- 31
6
votes
1
answer
491
views
Accelerating the computation of scipy.sparse.linalg.expm_multiply
I have a tridiagonal antiHermitian matrix ($-i*Hami*t$) with nonzero elements only along the upper diagonal and lower diagonal, and the goal is to know the action of exponential of such matrix on a ...
- 63
0
votes
1
answer
261
views
How to efficiently fill in, in parallel, a PETSc matrix from a COO sparse matrix?
Considering the following COO sparse matrix format, with repeated indices:
...
- 294
1
vote
1
answer
522
views
Crank Nicolson Method with closed boundary conditions
I want to simulate 1D diffusion with a constant diffusion coefficient using the Crank-Nicolson method.
$$\frac{\partial u (x,t)}{\partial t} = D \frac{\partial^2 u(x,t)}{\partial x^2}.$$
I take an ...
- 111
1
vote
0
answers
56
views
Assembling a sparse matrix for the PaStiX solver
I've been searching the whole afternoon for some documentation or code sample showing how to assemble a sparse matrix of a problem to be solved with PaStiX, but couldn't find any. The relevant module ...
- 131
2
votes
1
answer
120
views
How to numerically solve differential equations involving sines, cosines and inverses of the unknown function?
I'm very new to finite difference method and I am just introduced to methods of solving differential equation using finite difference method via sparse matrix method.
I find that the main idea is to ...
- 35
1
vote
0
answers
270
views
Solving 2D Poisson equation with mixed boundary conditions in Python
I am trying to numerically solve the Poisson's equation
$$
u_{xx} + u_{yy} = - \cos(x) \quad \text{if} - \pi/2 \leq x \leq \pi/2 \quad \text{0 otherwise}
$$
The domain is the rectangle with vertices ...
- 169
2
votes
0
answers
106
views
Parameter choice rules for L1 regularization?
I am solving an L1 regularized least squares of the form like:
$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \...
- 121
0
votes
1
answer
242
views
Assign and print the results of CHOLMOD package
I am trying to solve a simple working example, a linear system $Ax=b$, where $A$ is sparse SPD and $b$ is dense, using CHOLMOD.
...
- 294
2
votes
0
answers
108
views
How to save multiplication computation time between a dense vector and a not that sparse matrix?
I am trying to compute $\mathbf{X}\mathbf{u}$ for many times in my algorithm, where $\mathbf{X}\in \mathbb{R}^{n\times m}$ and $\mathbf{u} \in \mathbb{R}^{m}$. The problem is that, during the ...
- 21
3
votes
2
answers
371
views
Recover sparse matrix from linear operator
For many linear operators, it is easy to express them as a function. For example, to blur an image, simply compute a weighted sum of neighboring pixels (or even easier, import ...
- 41
0
votes
1
answer
273
views
How to speed up sparse matrix index operation in Matlab?
I need to create spare matrices with variable elements. Unfortunately, sparse matrix index operations are very slow.
Is there any way to speed up the process? Maybe there are some tricks that I don't ...
- 21
1
vote
1
answer
89
views
Consider only triangular part of symmetric matrix for operations
It seems common practice to store only the upper or lower triangular part of a sparse symmetric matrix to save memory. Now I am wondering how, e.g. the SpMV kernel in CSR format is designed and how ...
- 840
2
votes
0
answers
68
views
Sparse generalized symmetric eigensystem solver
Can anyone recommend a good software for solving generalized symmetric eigenvalue problems of the form,
$$
A x = \lambda B x
$$
where $A,B$ are symmetric and sparse, and $B$ is positive definite?
I ...
- 1,078
2
votes
0
answers
67
views
Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R?
Is there a permutation used in sparse QR factorizations that better locates small elements on the diagonal of R to the end of the diagonal? As an example, consider the following snippet of MATLAB ...
- 767
5
votes
0
answers
45
views
Lowest eigenvalues of a matrix with divergent entries
In high energy physics we oftentimes encounter the following problem. For a given parametrized matrix $\{H_{ij}(\Lambda)\}$, we know that in the limit $\Lambda\to\infty$ some of its entries become ...
- 151
1
vote
1
answer
168
views
Efficiency of developing PDE solvers using sparse matrices versus loops
I am new to solving PDEs, but have been looking at different implementations of finite difference and finite volume schemes. One thing I have noticed in different implementations is that some ...
- 297
2
votes
0
answers
47
views
Iterative methods for underestimate of smallest eigenvalue for large sparse matrices
I recently read the paper "EUCLIDEAN-NORM ERROR BOUNDS FOR SYMMLQ AND CG" by Estrin et al. and there they use an underestimate (i.e. something in $(0,\lambda_{min}]$) of the smallest ...
- 2,872
2
votes
0
answers
106
views
How to find eigvals/eigvecs of huge symmetric tridiagonal matrix using multiple processes or threads?
In python, there is a function in scipy (scipy.linalg.eigh_tridiagonal) which is extremely efficient for an exact diagonalization of a symmetric tridiagonal matrix (...
- 21
3
votes
0
answers
267
views
solve Ax=b for outrigger A matrix python
I implement Crank-Nicolson 2D finite-difference method.
I get a matrix A which is banded with 1 band above and below the main diagonal, but also contains 2 additional bands , further apart from the ...
- 141
1
vote
1
answer
191
views
Sparse direct solver that works inside opened omp parellel region?
Does anyone know a library that implements sparse direct solver working in already open omp parallel region? The only library that I know that works with this requirement is Pardiso7.2 worth ~8K USD ...
7
votes
0
answers
146
views
Can we sparse solve a few eigenvalues specified by index range?
I need to solve a few eigenvalues of a large sparse matrix specified by their index range. These indices are according to the whole eigenspectrum sorted in algebraic (not absolute value) ascending ...
- 303
4
votes
2
answers
249
views
nnz-preserving sparse matrix multiplication
Let A and B be sparse matrices in $ \mathbb{R}^{m\times m}$ with (roughly) the same density $p$. I want to efficiently compute a matrix $C$ that in some sense is "closest" to $AB$ while ...
- 41
0
votes
2
answers
174
views
Where can I find matrices and it's preconditioner for testing?
I want to find some kinds of matrices for testing my code such as GMRES , MINRES and so on. But I can't find some testing matrices and corresponding preconditioner to verify my program.
I know some ...
- 3
4
votes
1
answer
117
views
Sparse least squares with a (black-box) ill-conditioned operator
It was suggested on math.stackexchange.com that I try to ask this question here.
Consider a bounded linear operator $A : U \to V$ where $U$ is finite dimensional and where $V$ is a separable Hilbert ...
- 149
3
votes
1
answer
586
views
A method for finding the number of eigenvectors with a given, known eigenvalue
Is there a method for finding the number of eigenvectors with a given eigenvalue? I do not need the eigenvectors themselves, and to find the eigenvectors seems quite tough, given the comments on the ...
- 133