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

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].

Filter by
Sorted by
Tagged with
3 votes
0 answers
87 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 ...
2 votes
0 answers
92 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 ...
7 votes
3 answers
1k 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 ...
1 vote
1 answer
70 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 ...
2 votes
3 answers
2k views

Sparse Matrix Library for GPU

Does anyone know a good library that implements basic sparse matrix operations such as transpose, SpMV eigenvalues, etc. in GPU (cuda/OpenCL)?
0 votes
1 answer
65 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 ...
0 votes
0 answers
33 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
403 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 ...
2 votes
1 answer
62 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 ...
0 votes
1 answer
202 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 ...
3 votes
0 answers
135 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 ...
0 votes
0 answers
211 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
343 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 ...
1 vote
0 answers
188 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 ...
1 vote
2 answers
161 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 ...
2 votes
2 answers
240 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 ...
2 votes
0 answers
68 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 ...
0 votes
0 answers
104 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 ...
6 votes
1 answer
313 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 ...
0 votes
1 answer
207 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: ...
1 vote
1 answer
280 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 ...
7 votes
2 answers
436 views

Choice of iterative solver for a sparse asymmetric matrix with symmetric structure

I have a sparse $n\times n$ matrix $A$ with a pretty interesting structure. It has a block structure with a symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{...
1 vote
0 answers
54 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 ...
2 votes
1 answer
116 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 ...
2 votes
0 answers
100 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} \...
3 votes
2 answers
273 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 ...
1 vote
1 answer
179 views

Iterative single variable solutions in large linear systems

I have a system where $A$ is a large $n\times n$ marix with fast MVMs. It may have many nonzero entries (albeit in a structured way so as to allow fast MVMs), and is not necessarily diagonally ...
0 votes
1 answer
193 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. ...
2 votes
0 answers
101 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 ...
58 votes
4 answers
9k views

What guidelines should I follow when choosing a sparse linear system solver?

Sparse linear systems turn up with increasing frequency in applications. One has a lot of routines to choose from for solving these systems. At the highest level, there is a watershed between direct (...
2 votes
1 answer
340 views

All eigenpairs of large sparse symmetric matrix

In advance I am sorry for my noobish question. I am a physics PHD student and basically I use python for my math/physics problems. But now I have a problem which requires more computing capacity and ...
0 votes
1 answer
219 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 ...
1 vote
1 answer
86 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 ...
2 votes
0 answers
67 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 ...
2 votes
0 answers
57 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 ...
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 ...
1 vote
1 answer
141 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 ...
8 votes
2 answers
1k views

How does a Sparse Direct Solver know about dimensionality of a problem being solved?

It is claimed that the time and memory complexities of sparse direct solver are $O(N^2)$ and $O(N^{4/3})$ for 3D problems and $O(N^{1.5})$ and $O(N \log N)$ for 2D, respectively. But how does a ...
2 votes
0 answers
44 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 votes
0 answers
98 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 (...
2 votes
0 answers
231 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 ...
1 vote
1 answer
149 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
137 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 ...
4 votes
2 answers
232 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 ...
0 votes
2 answers
146 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 votes
2 answers
3k views

What sparse linear programming solver it is better to use?

I have the following LP problem: $$ \min \limits_{\varepsilon, x_{1}, \ldots, x_{n}}f(\varepsilon, x_{1}, \ldots, x_{n}) = \varepsilon \;\;\;\;\; \mathrm{s.t.} \;\;C x \geq 0, \;\; x_{i}^{0} - \...
2 votes
1 answer
244 views

Solving sparse linear equations with an iterative, out-of-core algorithm

Is there an iterative sparse parallel linear equation solver with out-of-core capabilities? I need to solve a very large system of equations. I have implemented direct sparse parallel solvers in-core ...
5 votes
3 answers
2k views

CPU benchmarks for numerical kernels

CPU benchmarks available online mostly focus on desktop apps/games and rarely on serial/parallel numerical kernels, specially sparse ones (e.g., MatMult). Some benchmarks like NAS/SciMark exists but ...
9 votes
2 answers
2k views

Solving Lx = b for big sparse Laplacian matrices

What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, ...
6 votes
2 answers
530 views

How can a CG solver solve a non positive definite sparse matrix

I am using the CUSP CG solver and I ran it on a couple of sparse matrices from the University of Florida sparse matrix collection. The solver was able to solve non positive definite sparse matrices. ...

1
2 3 4 5
7