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].
322
questions
0
votes
1
answer
179
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
131
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 ...
- 1,271
0
votes
0
answers
129
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
299
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,271
1
vote
0
answers
125
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 ...
- 8,602
1
vote
2
answers
122
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 ...
- 3,921
2
votes
2
answers
146
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,054
2
votes
0
answers
38
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
0
votes
0
answers
101
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
202
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 ...
- 933
0
votes
1
answer
148
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:
...
- 2,391
1
vote
1
answer
144
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 ...
- 366
7
votes
2
answers
391
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_{...
- 544
1
vote
0
answers
44
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
112
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,391
2
votes
0
answers
92
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
3
votes
2
answers
210
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
1
vote
1
answer
178
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 ...
- 211
0
votes
1
answer
156
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.
...
- 661
2
votes
0
answers
99
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 (...
- 1
2
votes
1
answer
301
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
...
- 2,116
0
votes
1
answer
149
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 ...
- 5,974
1
vote
1
answer
84
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 ...
- 54.1k
2
votes
0
answers
65
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 ...
- 11.1k
2
votes
0
answers
52
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 ...
- 757
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
122
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 ...
- 2,627
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 ...
- 849
2
votes
0
answers
43
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 ...
- 1,271
2
votes
0
answers
84
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
2
votes
0
answers
197
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 ...
- 131
1
vote
1
answer
130
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 ...
- 8,602
7
votes
0
answers
135
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
218
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 ...
- 54.1k
0
votes
2
answers
134
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 ...
- 10.9k
2
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} - \...
- 8,602
2
votes
1
answer
240
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 ...
- 8,602
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 ...
- 8,602
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, ...
- 8,602
6
votes
2
answers
449
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. ...
- 337
4
votes
1
answer
109
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
2
votes
1
answer
580
views
Robin Boundary Condition with Implicit Upwind - Finite Difference Method for 2D Convection-Diffusion Equation
I am trying to solve a problem with 2D Convection-Diffusion equation with U = Concentration ($mg/m^{2}$) using Implicit Upwind Finite Difference Method like this
$$
\frac{\partial U}{\partial t} + ...
CommunityBot
- 1
3
votes
1
answer
501
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
1
vote
1
answer
909
views
Givens rotation algorithm without matrix-matrix multiplication
I would like to implement a givenRotation algorithm without having matrix-matrix multiplication. Matrix-vector is fine or just for looping. I am to decompose a rectangular (m+1)xm Hessenberg matrix.
I ...
- 750
11
votes
1
answer
6k
views
How to compute Singular value decomposition of a large matrix with Python
Language: Python3
Problem: I have a matrix Q of shape [51200 rows x 51200 cols] stored in a binary file, each of the element in this matrix has a data type of complex64. To load the data into memory I ...
CommunityBot
- 1
3
votes
2
answers
3k
views
Applying the result of Cuthill-McKee in SciPy
I have applied SciPy's implementation of the Cuthill-McKee algorithm to a $48 \times 48$ sparse non-symmetric matrix in Compressed Sparse Row (CSR) format and the output is an array of length $48$ ...
- 8,602
1
vote
1
answer
157
views
What is the difference between Adittive Schwarz as a preprocessor and a solver?
As we all know, the Additive Schwarz approach can be used as either solver or preconditioner, however, my question is, what is the difference between the two? In other words, how to use AS as solver, ...
- 1,023
2
votes
1
answer
163
views
Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices
is anyone here aware of whether there exist bounds on the optimal bandwidths of 2D/3D FEM stiffness matrices?
Edit: more specifically, I would like to have bounds on the minimum bandwidth after ...
- 91
1
vote
1
answer
792
views
What is the conventional approach for sparse matrix multiplication?
When you're multiplying sparse matrices against other sparse matrices or dense matrices, what is the conventional approach for each? How are the sparse matrices stored? What does matrix multiplication ...
- 2,411