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].
60
questions with no upvoted or accepted answers
7
votes
0
answers
124
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
7
votes
1
answer
289
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
7
votes
0
answers
321
views
Compute sparsity pattern of $A^2$
Suppose we have a sparse matrix $A$. Is there any way to compute just the sparsity pattern of $A^2 = A \cdot A$ (I do not actually need to know what exactly the nonzero value are) faster than to ...
- 71
6
votes
0
answers
865
views
Sparse matrix format and sparse-matrix sparse-matrix multiplication
I'm having some performance problems with my code dealing with the multiplication of big sparse matrices (stiffness and aerodynamic influence coefficient matrices).
Mainly I have to multiply such ...
- 61
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
5
votes
0
answers
828
views
Symmetric sparse direct solvers in scipy
scipy.linalg.solve, in its newer versions, has a parameter assume_a that can be used to specify that the matrix $A$ is symmetric ...
- 10.1k
5
votes
0
answers
88
views
How to construct a eigensolver targeting a specific type of matrix
I need to diagonalize such kind of matrix during research: it's n-by-n, with it's upper-left (n-1)-by-(n-1) corner be diagonal while the nth row & column are dense. It's observed that the self ...
- 61
5
votes
0
answers
503
views
Optimisation of matrix exponential
I have a 7000x7000 sparse matrix (scipy), which I want to exponentiate. I've tried using scipy.sparse.linalg.expm, which works quite well for smaller matrices (takes a few seconds for a 1000x1000 ...
- 51
5
votes
0
answers
231
views
Preconditioning technique for large sparse non-hermitian matrix
I am attempting to solve a computational acoustics problem that involves solving an underlying sparse matrix. The size of the problem varies with grid size (3D) and fill-in's obviously make direct ...
5
votes
0
answers
237
views
Adaptive mesh data structure for Fast Marching Method to overcome RAM limit
On an uniform mesh of positions in space $\ (x_i,y_j,z_k)$:
$$\ x_i = x_0 + i\Delta x,\quad i=0,\ldots,n_x$$
$$\ y_j = y_0 + j\Delta y,\quad j=0,\ldots,n_y$$
$$\ z_k = z_0 + k\Delta z,\quad k=0,\...
- 193
3
votes
0
answers
129
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
3
votes
0
answers
96
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
0
answers
87
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
3
votes
0
answers
595
views
Compute Nullspace of Sparse Matrix
I am computing the nullspace of a sparse rectangular $m$ x $n$ matrix $A$, where $m$ << $n$. I do this by computing the QR decomposition of $A^T$ and extract the $n-m$ right-most columns of the ...
- 661
3
votes
0
answers
521
views
What is the algorithm to convert an adjacency matrix to a block diagonal structure?
I'm a little at loss as to what my supervisor meant by the "hierarchical block decomposition" of a matrix, but the goal is to put a sparse symmetric adjacency matrix into a block diagonal structure to ...
- 151
3
votes
0
answers
86
views
Numerical analysis, pivoting and incomplete LU decomposition
When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
- 31
3
votes
0
answers
115
views
Why the MIRACLE of Lanczos/CG-like?
Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy...
In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
- 57
3
votes
0
answers
328
views
Left eigenvectors using ARPACK
I'm trying to find both the dominant $k$ left and right eigenvectors, that is,
$$V_L\mathcal{A} = \Lambda V_L\\
\mathcal{A}V_R = V_R\Lambda\\
V_LV_R = I_{k\times k}$$
$V_L$ being the $k\times N$ ...
- 31
3
votes
0
answers
341
views
Efficient assembly of finite element matrix(coupled equations case)
I noticed this post, where spalloc and sparse are recommended for efficient assembly in Matlab. I personally use sparse ...
- 593
2
votes
0
answers
89
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
2
votes
0
answers
93
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
2
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
47
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
2
votes
0
answers
68
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
179
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
2
votes
0
answers
95
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
2
votes
0
answers
114
views
How to determine the finite difference coefficient matrix in 2D with periodic BC?
I'm solving a PDE in matlab using ode15s, and since the spatial dimension is 2, and number of variables grow large very quickly, I need to supply the structure of ...
- 217
2
votes
0
answers
121
views
What is the state-of-the-art in parallel sparse matrix and dense vector multiplication?
For sure, there has been many highly optimized library on this. But I am working on a matrix-free context since the problem size does not allow explicit storage of sparse matrix elements. I'd love ...
- 61
2
votes
0
answers
114
views
Acceleration of matrix geometric series
Suppose we want to find $x$ such that:
$$x=b+Ax$$
where $A$ is a large sparse square matrix with eigenvalues in the unit circle.
There are two representations of the solution:
1)
$$x=(I-A)^{-1}b,$$...
- 121
2
votes
0
answers
373
views
How to reuse permutation-orderings within scipy's SuperLU-wrapper?
i'm solving sparse linear equations within scipy 0.18 which internally resorts to SuperLU (after umfpack got removed due to license-issues).
Current, i'm doing a complete re-factorization in each ...
- 121
2
votes
0
answers
81
views
Fortran solver for the Sparse LSE problem
I was wondering if there is a Fortran library that contains a solver for the Sparse LSE(linear equality-constrained least squares) problem
$$
min_{x}\|Cx-d\|^2 \text{ subject to } Ax=b
$$
where $A$ ...
- 21
2
votes
0
answers
340
views
Sparse Linear Algebra vs Dense Linear Algebra
I am interested in a reference in the literature that discusses the performance of Dense Linear Algebra (blas routines) and dense linear algebra (sparse blas routines).
I am interested in knowing for ...
- 1,000
2
votes
0
answers
155
views
Solvers for stiff initial value ODEs with sparse Jacobian
What ODE solvers are optimized for solving stiff systems with sparse Jacobian? Such systems appear, for instance, when a parabolic PDE is discretized in space using typical finite difference or finite ...
- 281
2
votes
0
answers
1k
views
How to solve singular non symmetric poisson equation with Neumann boundary condtions?
I am trying to solve 2D Poisson equations with Neumann boundary conditions. When the mesh is uniform, Poisson equation is singular and symmetric, so the method listed in Null Space Projection for ...
- 21
2
votes
0
answers
110
views
Preconditioner for large size hermitian eigenvalue problems
Basically I try to compute several smallest eigenvalues of some sparse 50k*50k eigenvalue problems using matlab.
$$Ax = \lambda Bx$$
With matlab eigs, it's not as fast as I expected. So I tried some ...
- 593
1
vote
0
answers
62
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 ...
- 119
1
vote
0
answers
41
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
1
vote
0
answers
45
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(...
- 91
1
vote
0
answers
99
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
58
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
1
vote
0
answers
167
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
1
vote
0
answers
74
views
Numerical methods. MDF (ILU) implementation
I am trying to implement Minimum Discarded Fill (MDF) Ordering algorithm for incomplete matrix factorization. The algorithm description is here on page 60 Preconditioning Techniques for a Newton–...
- 21
1
vote
0
answers
124
views
understanding Domain Decomposition with example
I am new in Domain Decomposition method. I am started to solve $-\Delta u = f$ in $\Omega$ and $u = 0$ on $\partial\Omega$.
From that I get in $\Omega _1$
$$\begin{bmatrix}4&-1\\-1&4\end{...
- 41
1
vote
0
answers
173
views
Hybrid Ellpack-Itpack (ELL) + COO Sparse Matrix Representation decomposition threshold
Hybrid ELL-COO sparse matrix representation can be done as in the picture, I was looking intensively, however I couldn't find out what is the threshold of decomposing the original matrix into ELL part ...
- 113
1
vote
0
answers
61
views
How to use matlab **fft** function or other fast methods to solve a convection-diffusion system quickly?
for a convection-diffusion equation with Dirichlet boundary conditions as follows:
$$-u''+qu'=f$$
Using centered difference for $u''$ and $u'$, we get a linear system
$$Ax=b$$where matrix $A$ is ...
- 961
1
vote
0
answers
87
views
Fast calculation of $A^T B$
I need to compute a matrix-matrix product, $A^T B$, where $A$ is $n \times r$ sparse, and $B$ is $n \times q$ dense. The number of rows $n$ is far larger than both $r$ and $q$. In fact $n$ is so large ...
- 1,016
1
vote
0
answers
578
views
Pseudoinverse of a large sparse matrix in r
This question was moved from Cross-Validated: https://stats.stackexchange.com/questions/274042/pseudoinverse-of-large-sparse-matrix-in-r
I am trying to calculate the pseudoinverse of a large sparse ...
- 111
1
vote
0
answers
65
views
Reduce large sparse linear operators to memory efficient loops?
I'm dealing a lot with large sparse linear operators these days and I'm quite new to them. A lot of the matrices I deal with originate with only a few unique integers, however, there are lots of them. ...
- 163
1
vote
0
answers
297
views
How to reshape matrix into row-major order for MKL DSS?
I would like to use MKL to solve a sparse linear system. I chose the DSS (Direct Sparse Solver) interface, which implements the following steps:
...
- 71