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].
309
questions
0
votes
0
answers
44
views
Solving 2D Poisson Eq with mixed BC's 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 ...
- 109
2
votes
0
answers
86
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} \...
- 21
0
votes
1
answer
116
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
91
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
165
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
68
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
76
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 ...
- 830
3
votes
0
answers
62
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,016
2
votes
0
answers
43
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 ...
- 717
5
votes
0
answers
43
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
101
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 ...
- 255
1
vote
0
answers
40
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 ...
- 621
2
votes
0
answers
61
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
173
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
107
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
122
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
192
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
112
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
105
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
421
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
696
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 ...
- 201
1
vote
1
answer
139
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, ...
- 13
1
vote
1
answer
342
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 ...
- 281
2
votes
1
answer
130
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
6
votes
1
answer
216
views
Algorithm for solving systems which are nearly symmetric/adjoint?
I am familiar with Cholesky decomposition and LU factorization for solving systems of linear equations.
I have a problem where I have large sparse matrices (say, 1000x1000 or larger) where only one or ...
- 173
0
votes
1
answer
114
views
Best search algorithm for optimal weight factor in SOR method
I had written an algorithm that searches for the optimal weight parameter to be implemented in the successive-over relaxation (SOR) method which worked cleanly by vectorizing the interval and for ...
- 297
1
vote
1
answer
434
views
Efficiency of scipy.sparse.linalg.expm_multiply with sparse vs unsparse vectors
From the package scipy.sparse.linalg in Python, calling expm_multiply(X, v) allows you to compute the vector ...
- 185
3
votes
0
answers
119
views
Invert a huge sparse operator;
please help me with this question, I want to invert a huge sparse (non-circulant) this below in a $Ax=y$ equation:
$$(\lambda I+ \beta D+ \sigma C)x=y$$
where
I is an Identity Matrix,D is a Diagonal ...
- 31
1
vote
0
answers
39
views
Tolerance is not satisfied in eigsh function
I am diagonalizing a sparse matrix of size $153600\times 153600$ via eigsh function. I did not set the tolerance to specific value, so it would be the default value ...
- 171
1
vote
0
answers
57
views
Viable algorithms for efficiently solving a block matrix system with non-uniform sparsity structure
I am trying to use Newton's method to get a stationary solution for a system of equations of the following form:
$$
\begin{Bmatrix}
\frac{\partial x}{\partial t} \\
0
\end{Bmatrix} = \begin{Bmatrix}
f(...
- 81
3
votes
1
answer
260
views
How can I extract the banded or block diagonal part of a sparse matrix in MATLAB?
Given a large sparse (square) matrix in MATLAB, how can I extract the banded or the block-diagonal parts (of fixed size) of it efficiently?
These are useful operations when prototyping and testing ...
- 2,321
3
votes
0
answers
92
views
Solving PDEs: What is the best way to deal with non-banded/dense jacobians?
I have a system of PDEs describing atmospheric chemistry and transport. I use finite-differences to make my system of PDEs into a system of ~10,000 ODEs. I then integrate the ODEs forward in time with ...
- 297
3
votes
1
answer
174
views
`eigsh` (Lanczos algorithm) slows down for degenerate eigenvalues
I have a complex Hermitian matrix of size about $70000\times 70000$. I want about 100 eigenvalues near 0. However, I know that every eigenvalues are two-fold degenerate. I found out that the running ...
- 171
1
vote
1
answer
107
views
RCM better than Nested dissection? (For FEM discretizations in 2D and 3D)
I realize this might be a too general question but here goes nothing:
I am trying different re-ordering strategies and checking the fill-in of $A=LU$.
I have 2D ($p=1$, $h=1/40$ on $\Omega = [-1,1]^2$)...
- 91
3
votes
0
answers
82
views
Does shift-invert method has invertibility issue?
Please note that I have nearly zero background on numerical methods.
I understand the shift invert method as described in SciPy Tutorial
The main argument of the above link is as follows. Suppose we ...
- 171
2
votes
0
answers
80
views
Software for solving large systems of linear equations over gf(2)
What available solvers are there for linear equation solver over GF(2) (Boolean), capable of dealing with large sparse systems (in the 10k - 100k variables range)?
- 21
0
votes
3
answers
490
views
How to apply the boundary condition when global stiffness matrix is stored in csr format? [duplicate]
I am solving the poisson equation and I constructed the global stiffness matrix in compressed row storage format. Then I wrote the preconditioned conjugate gradient solver for solving the system of ...
- 29
1
vote
0
answers
94
views
C.S.R method in finite element matrix assembly
I have solved the 2D Poisson equation using finite element method with simplex triangular element in MATLAB.
First, I generated the triangular mesh using pdetool in ...
- 29
1
vote
0
answers
56
views
Nonsymmetric permutations for LU factorisation of symmetric matrix
Let $A$ be a symmetric matrix. It is then well known that computing the LU factorisation of $PAP^T$ instead of $A$ for a suitably chosen permutation matrix $P$ can greatly reduce fill-in. My question ...
- 425
3
votes
1
answer
253
views
Nonlinear root solving libraries which accept a Jacobian in band-storage
I'm in search for a library for solving large systems of non-linear equations, similar to MINPACK, but unlike MINPACK, can accept a Jacobian in band-storage.
My Jacobian is sometimes not invertible, ...
- 297
1
vote
2
answers
141
views
Solving a specific sparse linear system without dense materialization
I need to (computationally) solve a system of equations, for the purposes of an interior point method, of the form
$$
\left[\begin{array}{cc}B & A^T \\ A & 0\end{array}\right] \left[\begin{...
- 113
11
votes
1
answer
5k
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 ...
- 111
6
votes
1
answer
433
views
Efficiently computing $e^{tX}$ for many different values of $t$
Given an anti-Hermitian and sparse matrix $X$, I am using Python (NumPy and SciPy) to compute the matrix exponential $f(t) := e^{tX}$ for many values of $t$. The method I am currently using is to ...
- 185
1
vote
1
answer
135
views
Complexity of solving an image differential linear system
Define an "image differential linear system" as a linear system $A\mathbf{x}=\mathbf{b}$ wherein $\mathbf{x}$ contains the ($\mathbb{R}$) pixels of an image and each row of $A$ constrains ...
- 255
6
votes
1
answer
972
views
Parallelize Scipy iterative methods for linear equation systems(bicgstab) in Python
I need to solve linear equations system Ax = b, where A is a sparse CSR matrix with size 500 000 x 500 000. I'am using scipy.bicgstab and it takes almost 10min to solve this system on my PC and I need ...
- 61
1
vote
0
answers
155
views
performance comparison between PETSc and SLATE
We want to start a new project to solve a large-scale inverse problem (O(10^6) number of parameters) to invert for subsurface wave speeds. We will use FEM to solve forward and adjoint PDEs. In our ...
- 19
0
votes
0
answers
155
views
How to make a directed graph symmetric?
Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...
- 342
2
votes
1
answer
42
views
In Eigen, can a sparse matrix contain vectors/objects instead of simple scalar values?
I need to have a sparse matrix whose elements are not simple numbers, but objects, e.g. a couple of floating point values and a bunch of integer indices.
I am wondering if Eigen has something similar, ...
- 171
7
votes
1
answer
277
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_{...
- 2,059
2
votes
3
answers
189
views
Create a sparse matrix
I am writing a FE program which calculates the displacements under a uniform load. I want to store the stiffness matrix in sparse form(COO) without using an external library.Assume an upper-bound for ...
- 471