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].
311
questions
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
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
4
votes
1
answer
3k
views
Iteratively solving 3D Poisson equation in MATLAB
I have written a function that sets up a sparse matrix A and RHS b for the 3D Poisson equation in a relatively efficient way. The set-up is nothing fancy: I have extended the 2D 5-point stencil to an ...
- 143
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
4
votes
1
answer
392
views
Test matrices for large sparse overdetermined system of linear equations
I'm working on some c++ code to solve (conjugate gradient, least squares conjugate gradient, LSQR,..) large sparse overdetermined systems of linear equations. There is a twist to my matrices and the ...
- 143
1
vote
1
answer
270
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
...
- 113
1
vote
1
answer
240
views
How to complete sparse matrix?
I am trying to solve an equation by a meshfree method. Shape functions (and their derivatives) have a compact support domain. So, over a given integration cell used for numerical integration, only a ...
- 523
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 ...
1
vote
2
answers
249
views
How is the dense system usually dealt with in spectral method?
Unlike finite element (FEM) or finite difference methods (FDM), where the original PDE is transformed into a sparse linear system, spectral methods return a dense linear system. For a large system, it'...
- 649
1
vote
2
answers
755
views
Find a permutation matrix (using the Matlab's function $symrcm$) of a matrix $A(2:end, 2:end)$
I've the following Matlab code:
r = symrcm(A(2:end, 2:end));
prcm = [1 r + 1];
spy(A(prcm, prcm));
where A should be sparse ...
user9925
1
vote
2
answers
68
views
BLAS3 in Multifrontal Sparse Decomposition
I wonder how one manages to use BLAS level 3 operations in the multifrontal sparse decomposition algorithm. As far as I understand, the algorithm proceeds as follows:
For each row/column pair, ...
- 425
3
votes
2
answers
1k
views
Dirichlet boundary condition for sparse matrix - Solving Ax=b only for free nodes?
I am solving Biot equation with sparse matrix in MATLAB. I have no problem with global sparse matrices assembly, but when I assign Dirichlet boundary condition, it is so slow.
From this topic, How to ...
- 33
0
votes
1
answer
905
views
Use of scipy sparse in ode solver
I am trying to solve a differential equation system
$$x´=Ax\quad \text{with } x(0) = f(x)$$
in Python, where $A$ indeed is a complex sparse matrix.
For now i have been solving the system using the ...
14
votes
2
answers
6k
views
Compute all eigenvalues of a very big and very sparse adjacency matrix
I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse.
The hard part is I need all ...
- 243
2
votes
1
answer
646
views
Fast C++ implementation of sparse binary matrices
I am looking for the subject. The size of matrices will be around 1000x2000 elements with linear amount of ones (say, 6000 ones in the whole matrix).
The operations I will use the most:
iterating ...
- 133
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
7
votes
1
answer
649
views
Efficient algorithm for solving linear system with symmetric near-tridiagonal matrix?
I would like to solve the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$, with
$$\mathbf{A}=\mathbf{T}+\mathbf{C}$$
where $\mathbf{T}$ is a symmetric tridiagonal matrix and $\mathbf{C}$ is a corner-...
- 489
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$ ...
- 153
1
vote
0
answers
186
views
Updating factorization of Laplacian (add/remove edges)
For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges.
...
- 1,341
0
votes
2
answers
296
views
CHOLMOD implementation
I am working on a domain decomposition code in C that uses CHOLMOD to approximate grid values for a PDE in each sub-domain. The issue I have is that the methods use Matrix Market format, which is not ...
- 37
0
votes
1
answer
183
views
Multiplication of random sparse matrices
I am given 2 unstructured (i.e. do not posses any special sparsity pattern like banded/triangular/etc.) sparse matrices $A$ and $B$ of dimension ($n$ x $n$) and density $d$ each (thus each matrix ...
1
vote
1
answer
523
views
Linear solve using CHLOMOD in C
I am using the open-source CHLOMOD (as here http://faculty.cse.tamu.edu/davis/suitesparse.html) in order to solve a linear system Ax=b (performing A/b=x) in my domain decomposition code but I am ...
- 37
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
4
votes
1
answer
138
views
Solve for $C$ such that $C^{T}AC$ is banded of given width
Given a symmetric matrix $A$, the Lanczos algorithm outputs $C$ such that $C^{T}AC$ is tridiagonal. Is there a generalization of this such that $C^{T}AC$ is banded of specific width $w$? Note that $C$...
- 572
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
2
votes
1
answer
198
views
Probability of reconstructing a word using c substrings from a random sample
Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to ...
- 121
2
votes
2
answers
1k
views
Sparse Matrix Matrix multiplication terminology (SpGEMM or SpMM?)
I have seen sparse matrix-matrix multiplication commonly referred to as SpGEMM, which means general/generalised sparse matrix-matrix multiplication. I've seen it once or twice (forgot where) as SpMM.
...
- 87
1
vote
0
answers
275
views
Solving system of equations with zeros on diagonal [closed]
I am using finite elements, Newton Raphson technique and MUMPS direct solver, to solve for $P$ in this equation:
$$\frac{\delta K}{\delta x} \frac{\delta P}{\delta x}= \frac{\delta K B}{\delta x} + A$...
- 11
1
vote
0
answers
746
views
Implementation of a direct solver in Fortran 90?
My question may be elementary, but it is quite essential as I am getting confused.
Here I am supposed to solve the following equation:
$Ax=B$
From my understanding I have options of using either ...
2
votes
2
answers
664
views
Solve $AX=B$ where $A$ is a skyline matrix
Solve a matrix equation of the type $AX=B$, where $A$ is an $n \times n$ symmetric matrix stored in the form of symmetric skyline matrix.
With the solution given by Bill and some more research on ...
7
votes
3
answers
2k
views
How to compute the rank of a large sparse matrix in MATLAB
I am interested in computing the ranks of fairly large, the largest being of magnitude $10^6$ x $10^6$, sparse matrices whose entires are all 0, 1, or -1. I have been trying to use Matlab to ...
- 171
1
vote
1
answer
602
views
How efficient (compared to "normal" methods) is using a sparse finite difference matrix to solve differential equations?
Any differential operator can be written as a finite difference matrix acting on a vector of values. I recently used it to solve $\Delta A = j$ by writing the Laplacian as a finite difference ...
- 111
6
votes
1
answer
3k
views
Eigen - store sparse matrix as binary
I need to store large sparse matrices in Eigen. I cannot find anything in the library except the function below, in Eigen/Unsupported. The problem with saveMarket is, that it saves in text format. Due ...
- 399
2
votes
1
answer
270
views
Topics about the deal.II finite element library class "SparsityPattern"
When learning the deal.II FE library, I am a bit confused about the mechanism of its "SparsityPattern" class. Through reading the documentation, I only got to know that it uses the Compressed Row ...
- 649
3
votes
1
answer
158
views
Suggestions for an out-of-core sparse solver
I have a sparse $2\times10^5$ by $2\times10^5$ matrix with $3.2\times10^9$ non-zero elements.
I want a sparse solver with out-of-core functionality. I have attempted to use Intel's ...
- 233
5
votes
1
answer
160
views
Large scale triangular least squares
I have to solve the following least squares problem:
\begin{equation}
\| \left[ \begin{smallmatrix} \mathbf{L} \\ \mathbf{I} \end{smallmatrix} \right]\mathbf{x} - \mathbf{b} \|_2^2
\end{equation}
...
- 121
0
votes
1
answer
121
views
solver linear system equation
I need to solve to solve a "large" symmetric sparse linear systems, with matrix size 8000?
I heard about HSL, ITPACK, but I don't know how to use them, and I am working in C language.
9
votes
3
answers
4k
views
Calculating the log-determinant of a large sparse matrix
I need to calculate $\log(\det (\mathbf M_i))$ where the $\mathbf M_i$'s are large sparse matrices, which are real, symmetric and positive semi-definite. I hope to have between $10$ and $100$ of ...
- 257
1
vote
1
answer
745
views
On the fly/matrix free SVD of large sparse matrix
I am trying to apply SVD to large sparse matrices. I already compared the performances of Propack and irlba to those of the matlab svd and ...
- 13
10
votes
2
answers
6k
views
How to efficiently implement Dirichlet boundary conditions in global sparse finite element stiffnes matrices
I am wondering how Dirichlet boundary conditions in global sparse finite element matrices are actually implemented efficiently. For example lets say that our global finite element matrix was:
$$K =
\...
- 1,859
3
votes
1
answer
154
views
Sparse Matrix Reordering
Matrix reorderings are important for many direct solvers. Sometimes the objective is to reduce the bandwith or the generated fill in by LU Decomposition. I am interested in a reordering which reduces ...
- 168
2
votes
4
answers
733
views
Constructing sparsity pattern of the Jacobian of a FORTRAN subroutine
I need to calculate the Jacobian matrix of a subroutine F(U). Both F and U are of size N(=O($10^5$)). Using Tapenade, I differentiated the routine in tangent mode. I cannot calculate the full Jacobian ...
- 531
4
votes
1
answer
304
views
Choosing preconditioner for unsymmetric pressure-velocity coupled system
I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
- 41
2
votes
1
answer
696
views
How to convert MPIAIJ to SEQAIJ matrix in petsc/petsc4py?
I am curious, if there is a function to convert MPIAIJ (distributed matrices in AIJ format) to a SEQAIJ matrix that lie on a single processor. It is possible to do such an operation for PETSc vectors ...
- 245
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
1
vote
1
answer
223
views
solve linear system of equation of a large sparse symetric positive definite matrix
I want to invert large matrices ($10^4 \times 10^4$ to $10^6 \times 10^6$) but sparse (less than $100$ non-zero entries per line) on clusters with $16$ to $48$ processors per node.
I'm looking for an ...
- 262
2
votes
2
answers
253
views
High computational time in using backslash for soving sparse matrix
I built a sparse matrix A at each step as follows:
% 1 < DX < 120000
A = sparse(i,j,s,DX,DX,6*DX)
b = (1, DX)
The ...
- 21
1
vote
1
answer
152
views
Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition
I have the following quadratic form I need to evaluate:
$x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors.
Now assume that I am given for free both $A^{-1}$ ...
- 275
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
3
votes
1
answer
424
views
Sparse matrix vector product using PETSC
I am trying to do a simple parallel sparse matrix vector multiplications using PETSC. My sparse matrix is a simple tridiagonal laplacian matrix, which is distributed over multiple processors using ...
user16651